Потоки в транспортных сетях

Двухполюсные графы
Определение: Двухполюсная сеть S = (V,E,s,t) есть ориентированный граф G = (V,E) с двумя выделенными вершинами (полюсами) s – входная вершина (Исток) t – выходная вершина (Сток).

Определение: Внутренние вершины сети есть вершины, отличные от полюсов. Полюсная дуга сети инцидентна одному из полюсов. Пусть S = (V,E,s,t) — есть сеть и вершина v∈V. Введем следующие обозначения: D+(v) – множество дуг сети, исходящих из v. D(v) множество дуг сети, входящих в v. D(v) – множество дуг сети, инцидентных вершине v.

Очевидно, что D(v) = D+(v)∪D(v). Пусть A ⊆ V есть некоторое множество вершин сети S. Положим D(А) = ∪v∈AD(v),
D+(А) = ∪v∈AD+(v),
D(А) = ∪v∈AD(v).

Определение: е =(u,v) есть граничная дуга для A⊆V ↔ (u∈A & v∉A) ∨ (u∉A & v∈A). e=(u,v) есть внутренняя дуга для A⊆V↔ u∈A & v∈A.
ВН(D(A))– множество внутренних дуг из D(A).
ГР(D(A)) – множество граничных дуг из D(A).
ВН(D+(A)) – множество внутренних дуг из D+(A).
ГР(D+(A)) – множество граничных дуг из D+(A).
ВН(D(A)) – множество внутренних дуг из D(A).
ГР(D(A)) – множество граничных дуг из D(A).

Верны следующие равенства:
D(A) = ВН(D(A)) ∪ ГР(D(A))
D+(A) = ВН(D+(A)) ∪ ГР(D+(A))
D-(A) = ВН(D-(A)) ∪ ГР(D(A))
Заметим, что ВН(D(A)) = ВН(D+(A)) = ВН(D(A)), ибо для дуг e=(u,v) имеем соотношение:
e∈ ВН(D+(A)) по вершине u
e∈ ВН(D(A)) по вершине v
e∈ ВН(D(A)) по вершинам u,v
где 3 множества составлены из одних и тех же дуг.

Дивергенция
Пусть S = (V,E,s,t) есть сеть. Зададим функцию f: E →R+ (неотрицательные вещественные числа). Пусть V’ = V – {S,T} есть множество внутренних вершин сети S.

Определение: Дивергенция функции f во (внутренней вершине) v∈V’ есть величина (число) divf(v) =∑e∈D+(v)f(e) — ∑e∈D-(v)f(e). Дивергенция функции f на множестве внутренних вершин A⊆V’ есть число divf(A) = ∑v∈Adivf(v). В истоке и стоке дивергенция равна div(s) = ∑e∈D+(v)f(e) и div(t) = ∑e∈D-(v)f(e).

Утверждение (Основное свойство).
Для A⊆V’ divf(A) =∑e∈D+(v)f(e) — ∑e∈D-(v)f(e).

Доказательство: divf(v) = ∑v∈Adivf(v) = ∑v∈A(∑e∈D+(v)f(e) — ∑e∈D-(v)f(e)) = ∑v∈Ae∈D+(v)f(e) — ∑v∈Ae∈D-(v)f(e)) = ∑e∈D+(v)f(e) — ∑e∈D-(v)f(e).

Поток в сетях
Определение: Транспортная сеть S = (V,E,s,t,c) есть сеть (V,E,s,t), в которой D(s) = ∅ и D+(t)= ∅ и для которой определена функция c:E→R+(неотрицательные вещественные числа) – пропускная способность дуг. Вершина s – исток, t – сток.

Определение: Поток в сети S = (V,E,s,t,c) есть функция f:E →R+, удовлетворяющая следующим условиям:
1) 0 ≤ f(e) ≤ c(e)
2) для любой внутренней вершины v сети S divf(v) = 0 (сколько в вершину пришло столько и ушло).

Пусть S = (V,E,s,t,c,f) есть транспортная сеть с пропускной способностью дуг c:E→R+ и потоком f:E→R+

Свойства дивергенции потока:
Пусть V’ = V – {s,t} есть множество внутренних вершин сети S.
1) divf(V’) = ∑v∈V’’divf(v) = 0. Если A ⊆ V’, то divf(A) = 0
2) divf(S) = divf(t)

В самом деле, ввиду D+(V’) = ВН(D+(V’)) ∪ ГР(D+(V’)) получаем, что
0 = divf(V’) = ∑e∈D+(V’)f(e) — ∑e∈D+(V’)f(e) = ∑e∈ГР(D+(V’))f(e) + ∑e∈ВН(D+(V’))f(e) – ∑e∈ВН(D-(V’))f(e) + ∑e∈ГР(D-(V’))f(e) = divf(t) — divf(s) ⇒ divf(s) = divf(t)

Определение: Величина потока f в сети S = (V,E,s,t,c,f) есть величина (число) Mf = divf(s) = ∑e∈D+(s)f(e) = divf(t)= ∑e∈D-(t)f(e)

Сечение в сетях

Определение: Сечение (разрез) в сети S = (V,E,s,t) есть множество W ⊆ E дуг, при удалении которых получившаяся сеть S – W становится несвязной. Причем полюсы s и t попадают в разные компоненты связности. Сечение W простое, если при возвращении в сеть S-W любой дуги е из W сеть (S-W)+e становится связной по этой дуге.
Сечение W в сети S можно построить, разделив множество вершин в S на два подмножества A и B, причем s∈A, t∈B, и взяв в качестве W все дуги с началом в A и с концом в B, а также все дуги с концом в А и началом в В. При неориентированной связности будем говорить о связности орграфа по ребрам, не обращая внимания на их направление.

Определение: Дуга е простого сечения называется прямой дугой, если в цепи [s,t], проходящей через дугу е, она ориентированна от s к t; и обратной дугой, если она ориентирована от t к s в цепи [s,t]

Направление дуги зависит от выбора простого сечения. В фиксированном простом сечении W ориентация дуги не зависит от выбора цепи: дуга либо прямая, либо обратная для всех возможных цепей. Для каждой дуги e из простого сечения W можно укать цепь [s,t], которая проходит через дугу е и не проходит через остальные дуги сечения W.

Определение: Пусть W есть простое сечение в сети S. Пусть Wпр – множество прямых дуг в сечении W и Wоб – множество обратных дуг в сечении W. Тогда пропускная способность простого сечения W c(W) = ∑e∈Wпрс(e). Простое сечение W минимально, если W имеет минимальную пропускную способность . Пропускная способность сети, есть пропускная способность минимального простого сечения

Величина потока и пропускная способность сети
Пусть S = (V,E,s,t,c,f) – транспортная сеть c:E→N и f:E→N есть целочисленные функции пропускных способностей дуг и потока в сети S. N = {0,1,2,….}. Пусть W – есть простое сечение сети S. Пусть Wпр и Wоб – есть множества прямых и обратных дуг в сечении W соответственно.

Утверждение 1. Величина потока Mf = ∑e∈Wпрf(e) — ∑e∈Wобf(e)

Доказательство: Пусть KS – есть компонента связности в сети S-W, содержащая исток s.

Пусть VS – есть множество вершин компоненты KS, тогда величина потока Mf = divf(S) = {прибавим равную 0 дивергенцию по внутренним вершинам сети из Vs–{S}, ибо divf(Vs–{S}) = 0 по осн. свойству дивергенции} = ∑e∈D+(Vs)f(e) — ∑e∈D-(Vs)f(e) = {т.к. D+(Vs)=ВН(D+(Vs))∪ГР(D+(Vs))=ВН(D+(Vs)) ∪ Wпр и т.к.
D(Vs)=ВН(D(Vs))∪ГР(D(Vs))=ВН(D(Vs)) ∪ Wоб } = ∑e∈Wпрf(e) + ∑e∈ВН(D+(Vs))f(e) — ∑e∈ВН(D-(Vs))f(e) — ∑e∈Wобf(e) = ∑e∈Wпрf(e) — ∑e∈Wобf(e)

Утверждение 2. Если сmin есть пропускная способность сети, т.е. пропускная способность с(Wmin) минимального простого сечения Wmin, то величина потока Mf ≤ сmin.

Доказательство: Величина потока Mf = ∑e∈Wпрf(e) — ∑e∈Wобf(e) ≤ ∑ e∈Wпрf(e) ≤ ∑e∈Wпрс(e) = с(Wmin) = сmin

Замечание: Если Wmin есть минимальное простое сечение в сети S с пропускной способностью c(Wmin) = сmin и если поток f в сети S имеет максимально возможную величину Mf = сmin = с(Wmin) = ∑e∈Wпрс(e), то при этом Mf = ∑e∈Wпрf(e) — ∑e∈Wобf(e) = ∑e∈Wпрс(e) возможно лишь тогда, когда на дугах е из Wпр поток f(e) = c(e), а на дугах е из Wоб поток f(e) = 0. Максимальный возможный поток равен Mf = сmin нагружает прямые дуги в минимальном сечении до их пропускной способности, а обратные дуги не нагружает совсем.

Максимальный поток

Пусть S = (V,E,s,t,c,f) есть транспортная сеть с пропускной способностью дуг c:E→N и потоком f:E→N. cmin есть максимально возможный поток Mf.

Определение: Дуга e∈E в сети S насыщена, если f(e) = c(e).

Теорема 1: Пусть μ=[s,t] есть путь от s до t. Если все дуги этого пути ненасыщены, то поток f можно увеличить так, что одна из дуг пути μ=[s,t] окажется насыщенной.

Доказательство: δ = minc∈μ(c(e) – f(e)). Увеличиваем на δ поток f в каждой дуге e из μ, придем к потоку f’ = f+δ. Дуга е, на которой c(e) – f(e) = δ оказывается насыщенной.

Дуга е2 – насыщена.

Определение: Поток f в сети S полный, если всякий ориентированный путь от s к t имеет насыщенную дугу.

Теорема 2: Пусть ν=[s,t] есть ненаправленная цепь между s и t в сети S с полным потоком f. Пусть e есть прямая дуга в цепи ν и e — обратная дуга в цепи ν. Для дуги e∈V положим значение δ(e) = c(e) — f(e), δ = min e∈V(δ(e)). Для обратной дуги e∈V величина η = mine∈V f(e), ε=min(δ, η) Если ε>0, то увеличиваем на ε поток для каждой прямой дуги ε∈ν и уменьшаем поток на ε для каждой обратной дуги e∈V. В результате получим новый поток f ’ = f + ε.

Теорема 3: Если сеть S не имеет цепей ν=[s,t] от s к t с ε > 0, то поток f максимальный и его величина Mf = cmin.

Доказательство: Удалим из сети S все дуги e∈E, для которых f(e) = c(e) или f(e) = 0. Получившаяся сеть S’ имеет разобщенные полюса s и t, ибо в противном случае, т.е. если s и t связанные, то S’ имеет ν от s к t, для которой f(e) < c(e) для ∀e∈ν или f(e) > 0 для ∀e∈ν, тогда в S для цепи ν число ε>0. Противоречие с условием. Полюса s и t в S’ не связаны. Пусть KS и Kt есть компоненты связности в S’, содержащие полюса s и t соответственно. Vs есть множество вершин компоненты Ks. Тогда множество дуг ГР(D+(Vs)) есть множество прямых дуг Wпр в простом минимальном сечении W в сети S с с(W)=cmin. Все прямые дуги этого простого сечения насыщенные и для всех обратных дуг f(e) = 0, тогда величина потока Mf = ∑e∈Wпр f(e) — ∑e∈Wобр f(e) = ∑e∈Wпр с(e) -0 = сmin .


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru