Двухполюсные графы
Определение: Двухполюсная сеть 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’ есть число div_f(A) = ∑_v∈Adiv_f(v). В истоке и стоке дивергенция равна div(s) = ∑_e∈D+(v)f(e) и div(t) = ∑_e∈D-(v)f(e).

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

Доказательство: div_f(v) = ∑_v∈Adiv_f(v) = ∑_v∈A(∑_e∈D+(v)f(e) — ∑_e∈D-(v)f(e)) = ∑_v∈A∑_e∈D+(v)f(e) — ∑_v∈A∑_e∈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 div_f(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’’div_f(v) = 0. Если A ⊆ V’, то div_f(A) = 0
2) div_f(S) = div_f(t)

В самом деле, ввиду D⁺(V’) = ВН(D⁺(V’)) ∪ ГР(D⁺(V’)) получаем, что
0 = div_f(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) = div_f(t) — div_f(s) ⇒ div_f(s) = div_f(t)

Определение: Величина потока f в сети S = (V,E,s,t,c,f) есть величина (число) M_f = div_f(s) = ∑_e∈D+(s)f(e) = div_f(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. Величина потока M_f = ∑_e∈Wпрf(e) — ∑_e∈Wобf(e)

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

Пусть VS – есть множество вершин компоненты KS, тогда величина потока M_f = div_f(S) = {прибавим равную 0 дивергенцию по внутренним вершинам сети из V_s–{S}, ибо div_f(V_s–{S}) = 0 по осн. свойству дивергенции} = ∑_e∈D+(Vs)f(e) — ∑_e∈D-(Vs)f(e) = {т.к. D⁺(V_s)=ВН(D⁺(V_s))∪ГР(D⁺(V_s))=ВН(D⁺(V_s)) ∪ W_пр и т.к.
D^—(V_s)=ВН(D^—(V_s))∪ГР(D^—(V_s))=ВН(D^—(V_s)) ∪ 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 есть пропускная способность сети, т.е. пропускная способность с(W_min) минимального простого сечения Wmin, то величина потока M_f ≤ с_min.

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

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

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

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

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

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

Доказательство: δ = min_c∈μ(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 величина η = min_e∈V f(e), ε=min(δ, η) Если ε>0, то увеличиваем на ε поток для каждой прямой дуги ε∈ν и уменьшаем поток на ε для каждой обратной дуги e∈V. В результате получим новый поток f ’ = f + ε.

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

Доказательство: Удалим из сети 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’ не связаны. Пусть K_S и K_t есть компоненты связности в S’, содержащие полюса s и t соответственно. V_s есть множество вершин компоненты K_s. Тогда множество дуг ГР(D⁺(V_s)) есть множество прямых дуг W_пр в простом минимальном сечении W в сети S с с(W)=c_min. Все прямые дуги этого простого сечения насыщенные и для всех обратных дуг f(e) = 0, тогда величина потока M_f = ∑_e∈Wпр f(e) — ∑_e∈Wобр f(e) = ∑_e∈Wпр с(e) -0 = с_min .

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