Метод проталкивания предпотока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Идея)
м (rollbackEdits.php mass rollback)
 
(не показано 137 промежуточных версий 15 участников)
Строка 1: Строка 1:
'''Метод проталкивая предпотока''' {{---}} обобщенный алгоритм нахождения максимального потока в транспортной сети. В отличии от [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] и [[Схема алгоритма Диница|алгоритма Диница]] не является частным случаем [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|метода Форда-Фалкерсона]].
+
'''Метод проталкивания предпотока''' {{---}} обобщенный алгоритм нахождения максимального [[Определение сети, потока#Определение потока|потока]] в [[Определение сети, потока#Определение сети|сети]]. В отличие от [[Алоритм Эдмондса-Карпа|алгоритма Эдмондса-Карпа]] и [[Схема алгоритма Диница|алгоритма Диница]] не является частным случаем [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|метода Форда-Фалкерсона]].
  
 
== Определения ==
 
== Определения ==
 +
<!--------oxxx------------------[[Файл:OrGraphAlgoPreflow.png|500px|thumb|Пример]] <!-----скорее всего, надо переместить, ибо тут надо показать переполненные вершины, высоту, все дела...----->
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Предпотоком''' ('''preflow''') будем называть функцию <tex> f: V \times V \rightarrow \mathbb{R} </tex>, удовлетворяющую следующим свойствам:
+
'''Предпотоком''' (англ. ''preflow'') будем называть функцию <tex> f: V \times V \rightarrow \mathbb{R} </tex>, удовлетворяющую следующим свойствам:
 
1) <tex> f(u, v) = -f(v, u) </tex> (антисимметричность)
 
1) <tex> f(u, v) = -f(v, u) </tex> (антисимметричность)
  
Строка 11: Строка 12:
 
3) <tex>\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(v, u) \geqslant 0 </tex> (ослабленное условие сохранения потока)
 
3) <tex>\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(v, u) \geqslant 0 </tex> (ослабленное условие сохранения потока)
 
}}
 
}}
Как можно заметить, по своим свойствам предпоток очень похож на [[Определение сети, потока#Определение потока|поток]] и отличается лишь тем, что для него не выполняется закон сохранения потока.
+
Как можно заметить, по своим свойствам предпоток очень похож на поток и отличается лишь тем, что для него не выполняется закон сохранения потока.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Избыточным потоком''' ('''excess flow'''), входящим в вершину <tex> u </tex>, назовем величину <tex> e(u) = \sum \limits_{v \in V} f(v, u) </tex>.<br>
+
'''Избыточным потоком''' (англ. ''excess flow''), входящим в вершину <tex> u </tex>, назовем величину <tex> e(u) = \sum \limits_{v \in V} f(v, u) </tex>.<br>
Тогда вершина <tex> u \in V \setminus \{s, t\} </tex> будет называться '''переполненной'''('''overflowing'''), если <tex> e(u) > 0 </tex>.
+
Тогда вершина <tex> u \in V \setminus \{s, t\} </tex> будет называться '''переполненной''' (англ. ''overflowing''), если <tex> e(u) > 0 </tex>.
 
}}
 
}}
 +
[[Файл:OrGraphExample.png|left|thumb|Пример сети с истоком A и стоком D. Вершина B является переполненной.]]
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Функция <tex> h: V \rightarrow \mathbb{Z}_+</tex> называется '''высотой вершины'''('''vertex label'''), если она удовлетворяет условиям:
+
Функция <tex> h: V \rightarrow \mathbb{Z}_+</tex> называется '''высотой вершины''' (англ. ''vertex label''), если она удовлетворяет условиям:
 
1) <tex> h(s) = \left\vert V \right\vert </tex>
 
1) <tex> h(s) = \left\vert V \right\vert </tex>
  
Строка 26: Строка 28:
 
3) <tex> \forall (u, v)  \in E_f \quad h(u) \leqslant h(v) + 1</tex>
 
3) <tex> \forall (u, v)  \in E_f \quad h(u) \leqslant h(v) + 1</tex>
 
}}
 
}}
 +
 +
== Описание ==
 +
Пусть дан граф <tex>G</tex>, в котором выделены две вершины: исток <tex>S</tex> и сток <tex>T</tex>, а у каждого ребра определена пропускная способность <tex>C(u,v)</tex>. Поток <tex>F</tex> можно представить как поток вещества, которое могло бы пройти по сети от истока к стоку, если рассматривать граф как сеть труб с некоторыми пропускными способностями. То есть поток {{---}} функция <tex>F(u,v)</tex>, определённая на множестве рёбер графа.
 +
Задача заключается в нахождении максимального потока.
  
 
== Идея ==
 
== Идея ==
Для понимания идеи алгоритма представим, что наша сеть {{---}} система из резервуаров, находящихся на определенной высоте, и соединяющих их труб с заданными пропускными способностями, соответствующих вершинам и ребрам в исходной сети. Сам алгоритм можно представить как процесс поочередного "переливания" жидкости (операция проталкивания) из одного резервуара в другие, находящиеся на меньшей высоте, до тех пор пока будет существовать резервуар, соответствующей переполненной вершине. Может случиться ситуация, что все трубы, выходящие из переполненной вершины <tex> u </tex>, ведут к вершинам, находящимся на такой же высоте что и <tex> u </tex> или выше ее. В таком случае поднимем резервуар (операция подъема), соответствующий данной вершине, таким образом, чтобы его высота стала на единицу больше, чем высота самого низкого из смежных резервуаров. После подъема будет существовать по крайней мере одна труба, по которой можно попустить жидкость.
+
Для понимания идеи алгоритма представим, что наша сеть {{---}} система из резервуаров, находящихся на определенной высоте, и соединяющих их труб с заданными пропускными способностями, соответствующих вершинам и рёбрам в исходной сети. Сам алгоритм можно представить как процесс поочередного "переливания" жидкости (операция проталкивания) из одного резервуара в другие, находящиеся на меньшей высоте, до тех пор пока не перестанет существовать резервуар, соответствующий переполненной вершине. Может случиться ситуация, что все трубы, выходящие из переполненной вершины <tex> u </tex>, ведут к вершинам, находящимся на такой же высоте что и <tex> u </tex> или выше её. В таком случае поднимем резервуар (операция подъёма), соответствующий данной вершине, таким образом, чтобы его высота стала на единицу больше, чем высота самого низкого из смежных резервуаров. После подъёма будет существовать по крайней мере одна труба, по которой можно пропустить жидкость.
 +
 
 +
В итоге, у нас не останется ни одной переполненной вершины, та часть потока, которая могла пройти к стоку, окажется там, остальная же вернется в исток. В такой ситуации предпоток превращается в обычный поток, так как для каждой вершины выполняется условие сохранения потока. Как будет показано далее, предпоток становится не только обычным, но и максимальным потоком.
  
В итоге, у нас не останется ни одной переполненной вершины, та часть потока, которая могла пройти к стоку, окажется там, остальная же вернется в сток. В такой ситуации предпоток превращается в обычный поток, так как для каждой вершины выполняется условие сохранения потока. Как будет показано далее, предпоток становится не только обычным, но и максимальным потоком.
+
<!-----[[Файл:OrGraphAlgoPreflow.png|550px|thumb|left|Пример]][[Файл:OrGraphAlgoPreflow.png|550px|thumb|left|something poxozhee]]---->
  
 
== Операции ==
 
== Операции ==
 +
Как упоминалось ранее, в алгоритме выполняются две основные операции: проталкивание из переполненной вершины избытка потока в смежные вершины, высота которых меньше, чем у переполненной, и подъём вершины.
 +
=== Проталкивание (push) ===
 +
Операция проталкивания из вершины <tex> u </tex> в вершину <tex> v </tex> может применяться тогда, когда <tex> e(u) > 0 </tex>, то есть вершина <tex> u </tex> является переполненной, <tex> c_f(u, v) > 0 </tex> и <tex> h(u) = h(v) + 1 </tex>.
 +
 +
Данная операция работает следующим образом: по ребру <tex> (u, v) </tex> пропускается максимально возможный поток, то есть минимум из избытка вершины <tex> u </tex> и остаточной пропускной способности ребра <tex> (u, v) </tex>, вследствие чего избыток вершины <tex> u </tex>, остаточная пропускная способность ребра <tex> (u, v) </tex> и поток по обратному ребру <tex> (v, u) </tex> уменьшаются на величину потока, а избыток вершины <tex> v </tex>, поток по ребру <tex> (u, v) </tex> и остаточная пропускная способность обратного ребра <tex> (v, u) </tex> увеличиваются на эту же величину.
 +
 +
'''function''' push('''Node''' u, '''Node''' v)
 +
    d = min(e(u), c(u, v) - f(u, v))
 +
    f(u, v) += d
 +
    f(v, u) = -f(u, v)
 +
    e(u) -= d
 +
    e(v) += d
 +
 +
По своему результату все проталкивания можно разделить на <tex>2</tex> группы. Будем называть проталкивание из вершины <tex> u </tex> в вершину <tex> v </tex> '''насыщающим''', если после него остаточная пропускная способность ребра <tex> (u, v) </tex> стала равна нулю. Все остальные проталкивания будем называть '''ненасыщающими'''. Подобная классификация проталкиваний понадобится нам при оценке их количества.
 +
 +
=== Подъём (relabel) ===
 +
Операция подъёма применима для вершины <tex> u </tex>, если <tex> e(u) > 0 </tex> и <tex> \forall (u, v) \in E_f \quad h(u) \leqslant h(v) </tex>.
 +
 +
То есть, для переполненной вершины <tex> u </tex> применима операция подъёма, если все вершины, для которых в остаточной сети есть рёбра из <tex> u </tex>, расположены не ниже <tex> u </tex>. Следовательно, операцию проталкивания для вершины <tex> u </tex> произвести нельзя.
 +
 +
В результате подъёма высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.
 +
 +
'''function''' relabel('''Node''' u)
 +
    h(u) = min{h(v): f(u, v) - c(u, v) < 0} + 1
 +
 
== Схема алгоритма ==
 
== Схема алгоритма ==
 +
Для начала проинициализируем предпоток. Пропустим максимально возможный поток по рёбрам, инцидентным истоку, увеличив избыточный поток для каждой смежной с истоком вершиной на соответствующую величину. Все остальные потока не несут, следовательно, для вершин не смежных с истоком избыточный поток изначально будет нулевым. Также для всех вершин, кроме, естественно, истока, установим высоту, равную нулю.
 +
 +
Более формально это можно записать так:
 +
 +
<tex> f(u, v) =
 +
\begin{cases}
 +
    c(u, v), & u = s \\
 +
    -c(u, v), & v = s \\
 +
    0, & u \neq s \text{ and } v \neq s
 +
\end{cases}
 +
</tex>
 +
 +
 +
<tex> h(u) =
 +
\begin{cases}
 +
    \left\vert V \right\vert, & u = s \\
 +
    0, & u \neq s
 +
\end{cases}
 +
</tex>
 +
 +
 +
'''function''' initializePreflow('''Node''' s)
 +
    '''for''' u <tex> \in </tex> V
 +
        h(u) = 0
 +
        e(u) = 0
 +
    '''for''' (u, v) <tex>\in</tex> E
 +
        f(u, v) = 0
 +
        f(v, u) = 0
 +
    '''for''' u: (s, u) <tex>\in </tex> E
 +
        f(s, u) = c(s, u)
 +
        f(u, s) = -c(s, u)
 +
        e(u) = c(s, u)
 +
        e(s) -= c(s, u)
 +
    h(s) = |V|
 +
 +
После инициализации будем выполнять операции проталкивания и подъёма в произвольном порядке. Утверждается, что количество данных операций конечно, и после завершения работы алгоритма наш предпоток является максимальным потоком.
 +
 +
'''function''' pushRelabelMaxFlow('''Node''' s, '''Node''' t)
 +
    initializePreflow(s)
 +
    '''while''' e(u) > 0 '''and''' (h(u) = h(v) + 1 '''or''' <tex> \forall </tex> (u, v) <tex>\in  E_f </tex> h(u) <tex> \leqslant</tex> h(v))
 +
        '''if''' e(u) > 0 '''and''' h(u) = h(v) + 1
 +
          push(u, v)
 +
        '''if''' e(u) > 0 '''and''' <tex> \forall </tex> (u, v) <tex>\in  E_f </tex> h(u) <tex> \leqslant</tex> h(v)
 +
          relabel(u)
 +
[[Файл:OrGraphPush0.png|545px|left|Пример сети.]] [[Файл:OrGraphPush1.png|545px|right|Сеть после запуска потока, остаточная сеть, применение операции <tex>\mathrm{relabel}</tex>.]][[Файл:OrGraphPush2.png|545px|left|Применение операции <tex>\mathrm{push}</tex>.]]
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 
== Корректность алгоритма ==
 
== Корректность алгоритма ==
 +
Для доказательства корректности алгоритма докажем несколько вспомогательных лемм.
 +
 +
{{Лемма
 +
|about = <tex>1</tex>
 +
|id = Лемма1
 +
|statement =
 +
Во время выполнения алгоритма <tex> \mathrm{pushRelabelMaxFlow} </tex> никакие свойства высоты не нарушаются.
 +
|proof =
 +
Доказательство проведем по числу выполненных операций проталкивания и подъёма.
 +
 +
Для начала покажем, что после выполнения операции <tex> \mathrm{initializePreflow} </tex>  <tex> h </tex> является функцией высоты. Для всех рёбер, не инцидентных <tex> s </tex>, высота обоих концов равна нулю, что удовлетворяет условиям. Единственными рёбрами <tex> (u, v) </tex>, для которых не выполняются условия, налагаемые на функцию высоты, то есть для которых <tex> h(u) > h(v) + 1 </tex>, являются рёбра, у которых <tex> u = s </tex>. Но после операции <tex> \mathrm{initializePreflow} </tex> рёбра являются насыщенными и не принадлежат остаточной сети.
 +
 +
Это будет базой нашей индукции.
 +
 +
Теперь докажем переход: если перед выполнением операции проталкивания или подъёма <tex> h </tex> является функцией высоты, то и после выполнения операции она останется функцией высоты. Для этого рассмотрим проталкивание и подъём отдельно.
 +
 +
Покажем, что после окончания операции проталкивания утверждение верно. После выполнения операции <tex> \mathrm{push}</tex><tex>(u, v)</tex> в <tex> E_f </tex> может появиться ребро <tex> (v, u) </tex>, если до операции по ребру <tex> (u, v) </tex> протекал нулевой поток, или же ребро <tex> (u, v) </tex> может насытиться, и тогда оно перестанет принадлежать остаточной сети. В первом случае <tex> h(v) = h(u) - 1 < h(u) + 1 </tex>, и, следовательно, <tex> h </tex> остается функцией высоты. Во втором же случае при удалении ребра <tex> (u, v) </tex> из остаточной сети происходит лишь удаление соответствующих ограничений на высоты <tex> u </tex> и <tex> v </tex>, так что <tex> h </tex> остается функцией высоты.
 +
 +
Теперь рассмотрим операцию подъёма вершины <tex> u </tex>. По определению данной операции гарантируется, что после её выполнения для любого ребра <tex> (u, v) \in E_f </tex> выполняется условие <tex> h(u) \leqslant h(v) + 1 </tex>, то есть все выходящие рёбра удовлетворяют условиям, накладываемым на функцию высоты. Рассмотрим какое-то входящее ребро <tex> (w, u) </tex>. Так как до операции <tex> h </tex> являлась функцией высоты, то справедливо <tex> h(w) \leqslant h(u) + 1 </tex>. После подъёма высота вершины <tex> u </tex> увеличивается как минимум на единицу, следовательно, после выполнения данной операции <tex> h(w) < h(u) + 1 </tex>. Таким образом, <tex> h </tex> и после выполнения операции <tex> \mathrm{relabel}</tex><tex>(u) </tex> остается функций высоты.
 +
}}
 +
 +
 +
{{Лемма
 +
|about = <tex>2</tex>
 +
|id = Лемма2
 +
|statement =
 +
Пусть <tex> f </tex> {{---}} предпоток в сети <tex> G </tex>. Тогда для любой переполненной вершины можно выполнить операцию проталкивания либо операцию подъёма.
 +
|proof =
 +
Рассмотрим вершину <tex> u </tex>, для которой <tex> e(u) > 0 </tex>. Для любого ребра <tex> (u, v) \in E_f </tex> справедливо <tex> h(u) \leqslant h(v) + 1 </tex> по свойствам функции высоты. Если к вершине <tex> u </tex> применима операция проталкивания, то лемма доказана. Иначе, для всех рёбер <tex> (u, v) \in E_f </tex> выполняется соотношение <tex> h(u) < h(v) + 1 </tex>. Следовательно, <tex> h(u) \leqslant h(v) </tex>. Но тогда данная вершина удовлетворяет условиям операции подъёма, следовательно, к вершине <tex> u </tex> можно применить эту операцию.
 +
}}
 +
 +
 +
{{Лемма
 +
|about = <tex>3</tex>
 +
|id = Лемма3
 +
|statement =
 +
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. <tex> f </tex> и <tex> h </tex> {{---}} предпоток и функция высоты соответственно. Тогда в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>.
 +
|proof =
 +
Докажем от противного.
 +
 +
Предположим, что в <tex> G_f </tex> существует путь из <tex> s </tex> в <tex> t </tex>. Из [[Теорема о существовании простого пути в случае существования пути#Теорема о существовании простого пути в случае существования пути|теоремы о существовании простого пути]] следует, что в <tex> G_f </tex> также существует и простой путь из <tex> s </tex> в <tex> t </tex>. Тогда пусть <tex> p = \left \langle v_0, v_1, \dots, v_k \right \rangle </tex> {{---}} простой путь, где <tex> v_0 = s </tex> и <tex> v_k = t </tex>. А раз <tex> p </tex> простой, то <tex> k < \left\vert V \right\vert </tex>. Поскольку <tex> h </tex> {{---}} функция высоты, то <tex> \forall i \in \{0, 1, \dots, k - 1 \} </tex> справедливо <tex> h(v_i) \leqslant h(v_{i+1}) + 1 </tex>. Следовательно, <tex> h(s) \leqslant h(t) + k </tex>. А так как по определению функции высоты <tex> h(t) = 0 </tex>, то <tex> h(s) \leqslant k < \left\vert V \right\vert </tex>, что противоречит условию, что <tex> h(s) = \left\vert V \right\vert </tex>.
 +
}}
 +
 +
 +
{{Теорема
 +
|statement =
 +
Если алгоритм <tex> \mathrm{pushRelabelMaxFlow}</tex> завершается, то вычисленный им предпоток <tex> f </tex> является максимальным потоком.
 +
|proof =
 +
Для доказательства покажем, что перед каждой проверкой условия в цикле while <tex> f </tex> является предпотоком.
 +
 +
Перед началом цикла, после завершения операции <tex> \mathrm{initializePreflow}</tex>, <tex> f </tex> является предпотоком.
 +
 +
Внутри цикла выполняются лишь операции проталкивания и подъёма. Операция подъёма не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъёма не зависит, будет ли <tex> f </tex> предпотоком. Операция <tex> \mathrm{push}</tex><tex>(u, v)</tex> применяется, если <tex> e(u) > 0 </tex>, увеличивая поток через ребро <tex> (u, v) </tex> на величину, не превышающую избыточный поток вершины <tex> u </tex> и остаточную пропускную способность ребра <tex> (u, v) </tex>. Следовательно, если перед выполнением операции проталкивания <tex> f </tex> являлся предпотоком, то и после выполнения проталкивания <tex> f </tex> останется предпотоком.
 +
 +
После завершения алгоритма для каждой вершины <tex> u \in V \setminus \{s, t\} </tex> справедливо, что <tex> e(u) = 0 </tex>, что следует непосредственно из [[#Лемма1|леммы (<tex>1</tex>)]], [[#Лемма2|леммы (<tex>2</tex>)]] и того, что перед выполнением операций проталкивания или подъёма <tex> f </tex> является предпотоком. Но тогда <tex> f </tex> удовлетворяет условию сохранения потока, то есть сам является потоком.
 +
 +
Поскольку из [[#Лемма1|леммы (<tex>1</tex>)]] следует, что <tex> h </tex> является функцией высоты и после завершения алгоритма, то по [[#Лемма3|лемме (<tex>3</tex>)]] в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>. Но тогда по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] <tex> f </tex> {{---}} максимальный поток.
 +
}}
 +
 
== Оценка быстродействия ==
 
== Оценка быстродействия ==
 +
Чтобы показать, что алгоритм завершает свою работу, найдём максимальное количество операций проталкивания и подъёма. Для этого докажем несколько вспомогательных лемм.
 +
 +
{{Лемма
 +
|about = <tex>4</tex>
 +
|id = Лемма4
 +
|statement =
 +
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>, и <tex> f </tex> {{---}} предпоток в <tex> G </tex>. Тогда из любой переполненной вершины <tex> u </tex> существует путь в <tex> s </tex> в остаточной сети <tex> G_f </tex>.
 +
|proof =
 +
Докажем лемму методом от противного.
 +
 +
Пусть для вершины <tex> u </tex> верно, что <tex> e(u) > 0 </tex>. Пусть также <tex> U = \{v: u \leadsto v </tex> в <tex> G_f \} </tex> и <tex> \bar{U} = V \setminus U </tex>. Предположим, что <tex> s \in \bar{U} </tex>.
 +
 +
Покажем, что для любой пары вершин <tex> v \in U </tex> и <tex> w \in \bar{U} </tex> верно, что <tex> f(w, v) \leqslant 0 </tex>. Если <tex> f(w, v) > 0 </tex>, то <tex> f(v, w) < 0 </tex>. Но тогда из этого утверждения следует, что <tex> c_f(v, w) = c(v, w) - f(v, w) > 0 </tex>, что не может быть верным, так как в таком случае существует путь <tex> u \leadsto v \to w </tex> в остаточной сети <tex> G_f </tex>, что противоречит выбору вершины <tex> w </tex>. Следовательно, для каждой пары вершин <tex> v \in U </tex> и <tex> w \in \bar{U} </tex> верно, что <tex> f(w, v) \leqslant 0 </tex>. Тогда верно и <tex> f(\bar{U}, U) \leqslant 0 </tex>. Следовательно <tex> e(U) = f(V, U) = f(U, U) + f(\bar{U}, U) = f(\bar{U}, U) \leqslant 0 </tex>.
 +
 +
Но по определению избыток потока неотрицателен, из чего следует, что для любой вершины <tex> v \in U </tex> <tex> e(v) = 0 </tex>, в том числе <tex> e(u) = 0 </tex>, что противоречит условию переполненности вершины <tex> u </tex>.
 +
}}
 +
 +
 +
{{Лемма
 +
|about = <tex>5</tex>
 +
|id = Лемма5
 +
|statement =
 +
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. Тогда во время выполнения алгоритма <tex> \mathrm{pushRelabelMaxFlow}</tex> для любой вершины <tex> u </tex> в сети <tex> G </tex> верно, что <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>
 +
|proof =
 +
По определению функции высоты <tex> h(s) = \left\vert V \right\vert </tex> и <tex> h(t) = 0 </tex>, следовательно для истока и стока утверждение леммы выполнено.
 +
 +
Рассмотрим вершину <tex> u </tex> отличную от истока и стока. Изначально <tex> h(u) = 0 \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. Покажем, что после любой операции подъёма <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. Для того, чтобы мы имели право произвести операцию <tex> \mathrm{relabel}</tex><tex>(u) </tex>, вершина <tex> u </tex> должна быть переполнена. Тогда по [[#Лемма4|лемме <tex>4</tex>]] существует простой путь <tex> p </tex> из <tex> u </tex> в <tex> s </tex> в остаточной сети <tex> G_f </tex>. Рассмотрим этот путь. Пусть <tex> p = \left\langle v_0, v_1, \dots, v_k \right\rangle </tex>, где <tex> v_0 = u </tex> и <tex> v_k = s </tex>. Так как путь <tex> p </tex> простой, то <tex> k \leqslant \left\vert V \right\vert - 1 </tex>. По определению функции высоты имеем, что <tex> \forall i \in \{0, 1, \dots, k - 1\} </tex> <tex> h(v_i) \leqslant h(v_{i+1}) + 1</tex>. Но тогда для вершин <tex> u </tex> и <tex> v </tex> верно, что <tex> h(u) \leqslant h(s) + \left\vert V \right\vert - 1 = 2 \cdot \left\vert V \right\vert - 1 </tex>
 +
}}
 +
 +
 +
На основании предыдущей леммы покажем верхнюю границу числа подъёмов.
 +
 +
{{Лемма
 +
|about = <tex>6</tex>
 +
|id = Лемма6
 +
|statement =
 +
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. Тогда во время выполнения алгоритма <tex> \mathrm{pushRelabelMaxFlow}</tex> общее число подъёмов не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 </tex>
 +
|proof =
 +
Так как высоты истока и стока не изменяются в процессе работы алгоритма, то только <tex> \left\vert V \right\vert - 2 </tex> вершин могут быть подняты. Пусть <tex> u \in V \setminus \{s, t\}</tex>. Изначально <tex> h(u) = 0 </tex>, и по [[#Лемма5|лемме (<tex>5</tex>)]] известно, что <tex> h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 </tex>. А так как при выполнении операции <tex> \mathrm{relabel}</tex><tex>(u) </tex> высота вершины увеличивается как минимум на единицу, то максимальное количество подъёмов вершины <tex> u </tex> также не превышает <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. Тогда суммарно число подъёмов не превышает <tex> (\left\vert V \right\vert - 2 ) \cdot (2 \cdot \left\vert V \right\vert - 1) \leqslant 2 \cdot \left\vert V \right\vert ^2 </tex>.
 +
}}
 +
 +
 +
{{Лемма
 +
|about = <tex>7</tex>
 +
|id = Лемма7
 +
|statement =
 +
После ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> вершина <tex> u </tex> перестает быть переполненной.
 +
|proof =
 +
Поскольку проталкивание ненасыщающее, то величина потока, проталкиваемого через ребро <tex> (u, v) </tex> должна быть равна <tex> e(u) </tex>. После выполнения проталкивания избыточный поток вершины должен уменьшится на величину проталкиваемого потока, следовательно, после ненасыщающего проталкивания из <tex> u </tex> в <tex> v </tex> величина <tex> e(u) = 0 </tex>.
 +
}}
 +
 +
 +
Следующие две леммы показывают верхнюю границу количества проталкиваний.
 +
{{Лемма
 +
|about = <tex>8</tex>
 +
|id = Лемма8
 +
|statement =
 +
Количество насыщающих проталкиваний при выполнение алгоритма <tex> \mathrm{pushRelabelMaxFlow}</tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>
 +
|proof =
 +
Возьмем произвольную пару вершин <tex> u </tex> и <tex> v </tex> и рассмотрим насыщающие проталкивания по рёбрам <tex> (u, v) </tex> и <tex> (v, u) </tex>. Предположим, что произошло насыщающее проталкивание по ребру <tex> (u, v) </tex>. Тогда во время проталкивания <tex> h(v) = h(u) - 1 </tex>. Для того, чтобы могло произойти еще одно насыщающее проталкивание по ребру <tex> (u, v) </tex>, мы должны для начала протолкнуть поток из <tex> v </tex> в <tex> u </tex>, чтобы ребро <tex> (u, v) </tex> снова появилось в остаточной сети. Но для этого должно выполняться условие <tex> h(v) = h(u) + 1 </tex>, то есть высота вершины <tex> u </tex> должна увеличится как минимум на <tex>2</tex>. По [[#Лемма5|лемме (<tex>5</tex>)]] высота вершины не превышает <tex> 2 \cdot\left\vert V \right\vert - 1 </tex>, следовательно, количество раз, когда высота вершины может увеличится на <tex>2</tex>, меньше <tex> \left\vert V \right\vert </tex>. Поскольку между двумя насыщающими проталкиваниями высота одной из вершин должна увеличится по меньшей мере на <tex>2</tex>, то между вершинами <tex> u </tex> и <tex> v </tex> их будет не более <tex> 2 \cdot\left\vert V \right\vert </tex>. Тогда суммарно по всем рёбрам во время работы алгоритма произойдут не более <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex> насыщающих проталкиваний.
 +
}}
 +
 +
 +
{{Лемма
 +
|about = <tex>9</tex>
 +
|id = Лемма9
 +
|statement =
 +
Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> \mathrm{pushRelabelMaxFlow}</tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>
 +
|proof =
 +
Пусть <tex> \Phi = \sum \limits_{u: e(u) > 0} h(u)</tex>. Так как после завершения алгоритма ни одна из вершин не является переполненной, то и величина <tex> \Phi </tex> после выполнения алгоритма должна равняться нулю.
 +
 +
Для начала рассмотрим, каким образом может увеличиваться величина <tex> \Phi </tex>.
 +
Первое, что может увеличить <tex> \Phi </tex>, это подъём, поскольку, осуществляя данную операцию, мы не изменяем избыточный поток ни у одной вершины, а лишь увеличиваем высоту одной из них. При каждой операции подъёма <tex> \Phi </tex> увеличивается менее чем на <tex> 2 \cdot \left\vert V \right\vert </tex>, так как подъём не может увеличить высоту вершины больше, чем её максимальная высота, которая согласно [[#Лемма5|лемме (<tex>5</tex>)]] может быть не более <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. А поскольку из [[#Лемма6|леммы (<tex>6</tex>)]] известно, что число подъёмов не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 </tex>, то суммарно подъёмы всех вершин могут увеличить <tex> \Phi </tex> не более чем на <tex> 4 \cdot \left\vert V \right\vert^3 </tex>.
 +
 +
Во-вторых, величина <tex> \Phi </tex> может увеличится при насыщающем проталкивании из <tex> u </tex> в <tex> v </tex>, потому что <tex> e(u) > 0 </tex> и после насыщающего проталкивания, а вершина <tex> v </tex> может стать переполненной. Увеличение меньше <tex> 2 \cdot \left\vert V \right\vert </tex>, так как изменения высот не происходит, а высота вершины <tex> v </tex> не превосходит <tex> 2 \cdot \left\vert V \right\vert - 1 </tex>. Но по [[#Лемма8|лемме (8)]] известно, что количество насыщающих проталкиваний за все время выполнения алгоритма не превосходит <tex> 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert </tex>, следовательно, за счет насыщающих проталкиваний <tex> \Phi </tex> увеличится не более чем на <tex> 4 \cdot \left\vert V \right\vert^2 \cdot \left\vert E \right\vert </tex>.
 +
 +
Итого, получаем, что величина <tex> \Phi </tex> не может быть больше <tex> 4 \cdot \left\vert V \right\vert ^2 \cdot (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
 +
 +
Теперь покажем, что ненасыщающее проталкивание уменьшает <tex> \Phi </tex> как минимум на единицу. Пусть произошло ненасыщающее проталкивание из вершины <tex> u </tex> в <tex> v </tex>. Согласно [[#Лемма7|лемме <tex>7</tex>]] после ненасыщающего проталкивания вершина <tex> u </tex> перестает быть переполненной, следовательно, <tex> \Phi </tex> уменьшается на величину её высоты. После проталкивания вершина <tex> v </tex> является переполненной, и поэтому <tex> \Phi </tex> могла увеличится на <tex> h(v) </tex>. Поскольку <tex> h(u) = h(v) - 1 </tex>, то при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается по меньшей мере на единицу.
 +
 +
Зная верхнюю границу величины <tex> \Phi </tex>, её значение после выполнения алгоритма и то, что при каждом ненасыщающем проталкивании <tex> \Phi </tex> уменьшается минимум на единицу, то можно сделать вывод, что количество ненасыщающих проталкиваний не больше чем <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>.
 +
}}
 +
 +
 +
{{Теорема
 +
|statement =
 +
Пусть <tex> G </tex> {{---}} сеть. Тогда любая реализация метода <tex> \mathrm{pushRelabelMaxFlow}</tex> для <tex> G </tex> завершает свою работу, и число основных операций составляет <tex> O(V^2E) </tex>
 +
|proof =
 +
Из [[#Лемма6|леммы <tex>6</tex>]], [[#Лемма8|леммы <tex>8</tex>]] и [[#Лемма9|леммы <tex>9</tex>]] следует, что число операций подъёма и проталкиваний не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 + 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert + 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) = O(V^2E) </tex>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
 +
}}
 +
 +
==См. также==
 +
* [[Определение сети, потока]]
 +
* [[Схема алгоритма Диница|Алгоритм Диница]]
 +
* [[Алгоритм Эдмондса-Карпа]]
 +
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]
 +
 
== Источники ==
 
== Источники ==
 +
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2011. — С. 762—773.
 +
* [http://ru.wikipedia.org/wiki/Алгоритм_проталкивания_предпотока Алгоритм проталкивания предпотока — Википедия]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о максимальном потоке]]

Текущая версия на 19:35, 4 сентября 2022

Метод проталкивания предпотока — обобщенный алгоритм нахождения максимального потока в сети. В отличие от алгоритма Эдмондса-Карпа и алгоритма Диница не является частным случаем метода Форда-Фалкерсона.

Определения

Определение:
Предпотоком (англ. preflow) будем называть функцию [math] f: V \times V \rightarrow \mathbb{R} [/math], удовлетворяющую следующим свойствам:

1) [math] f(u, v) = -f(v, u) [/math] (антисимметричность)

2) [math] f(u, v) \leqslant c(u, v) [/math] (ограничение пропускной способностью)

3) [math]\forall u \in V \setminus \{s, t\} \quad \sum\limits_{v \in V} f(v, u) \geqslant 0 [/math] (ослабленное условие сохранения потока)

Как можно заметить, по своим свойствам предпоток очень похож на поток и отличается лишь тем, что для него не выполняется закон сохранения потока.


Определение:
Избыточным потоком (англ. excess flow), входящим в вершину [math] u [/math], назовем величину [math] e(u) = \sum \limits_{v \in V} f(v, u) [/math].
Тогда вершина [math] u \in V \setminus \{s, t\} [/math] будет называться переполненной (англ. overflowing), если [math] e(u) \gt 0 [/math].
Пример сети с истоком A и стоком D. Вершина B является переполненной.
Определение:
Функция [math] h: V \rightarrow \mathbb{Z}_+[/math] называется высотой вершины (англ. vertex label), если она удовлетворяет условиям:

1) [math] h(s) = \left\vert V \right\vert [/math]

2) [math] h(t) = 0 [/math]

3) [math] \forall (u, v) \in E_f \quad h(u) \leqslant h(v) + 1[/math]


Описание

Пусть дан граф [math]G[/math], в котором выделены две вершины: исток [math]S[/math] и сток [math]T[/math], а у каждого ребра определена пропускная способность [math]C(u,v)[/math]. Поток [math]F[/math] можно представить как поток вещества, которое могло бы пройти по сети от истока к стоку, если рассматривать граф как сеть труб с некоторыми пропускными способностями. То есть поток — функция [math]F(u,v)[/math], определённая на множестве рёбер графа. Задача заключается в нахождении максимального потока.

Идея

Для понимания идеи алгоритма представим, что наша сеть — система из резервуаров, находящихся на определенной высоте, и соединяющих их труб с заданными пропускными способностями, соответствующих вершинам и рёбрам в исходной сети. Сам алгоритм можно представить как процесс поочередного "переливания" жидкости (операция проталкивания) из одного резервуара в другие, находящиеся на меньшей высоте, до тех пор пока не перестанет существовать резервуар, соответствующий переполненной вершине. Может случиться ситуация, что все трубы, выходящие из переполненной вершины [math] u [/math], ведут к вершинам, находящимся на такой же высоте что и [math] u [/math] или выше её. В таком случае поднимем резервуар (операция подъёма), соответствующий данной вершине, таким образом, чтобы его высота стала на единицу больше, чем высота самого низкого из смежных резервуаров. После подъёма будет существовать по крайней мере одна труба, по которой можно пропустить жидкость.

В итоге, у нас не останется ни одной переполненной вершины, та часть потока, которая могла пройти к стоку, окажется там, остальная же вернется в исток. В такой ситуации предпоток превращается в обычный поток, так как для каждой вершины выполняется условие сохранения потока. Как будет показано далее, предпоток становится не только обычным, но и максимальным потоком.


Операции

Как упоминалось ранее, в алгоритме выполняются две основные операции: проталкивание из переполненной вершины избытка потока в смежные вершины, высота которых меньше, чем у переполненной, и подъём вершины.

Проталкивание (push)

Операция проталкивания из вершины [math] u [/math] в вершину [math] v [/math] может применяться тогда, когда [math] e(u) \gt 0 [/math], то есть вершина [math] u [/math] является переполненной, [math] c_f(u, v) \gt 0 [/math] и [math] h(u) = h(v) + 1 [/math].

Данная операция работает следующим образом: по ребру [math] (u, v) [/math] пропускается максимально возможный поток, то есть минимум из избытка вершины [math] u [/math] и остаточной пропускной способности ребра [math] (u, v) [/math], вследствие чего избыток вершины [math] u [/math], остаточная пропускная способность ребра [math] (u, v) [/math] и поток по обратному ребру [math] (v, u) [/math] уменьшаются на величину потока, а избыток вершины [math] v [/math], поток по ребру [math] (u, v) [/math] и остаточная пропускная способность обратного ребра [math] (v, u) [/math] увеличиваются на эту же величину.

function push(Node u, Node v)
    d = min(e(u), c(u, v) - f(u, v))
    f(u, v) += d
    f(v, u) = -f(u, v)
    e(u) -= d
    e(v) += d

По своему результату все проталкивания можно разделить на [math]2[/math] группы. Будем называть проталкивание из вершины [math] u [/math] в вершину [math] v [/math] насыщающим, если после него остаточная пропускная способность ребра [math] (u, v) [/math] стала равна нулю. Все остальные проталкивания будем называть ненасыщающими. Подобная классификация проталкиваний понадобится нам при оценке их количества.

Подъём (relabel)

Операция подъёма применима для вершины [math] u [/math], если [math] e(u) \gt 0 [/math] и [math] \forall (u, v) \in E_f \quad h(u) \leqslant h(v) [/math].

То есть, для переполненной вершины [math] u [/math] применима операция подъёма, если все вершины, для которых в остаточной сети есть рёбра из [math] u [/math], расположены не ниже [math] u [/math]. Следовательно, операцию проталкивания для вершины [math] u [/math] произвести нельзя.

В результате подъёма высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.

function relabel(Node u)
    h(u) = min{h(v): f(u, v) - c(u, v) < 0} + 1

Схема алгоритма

Для начала проинициализируем предпоток. Пропустим максимально возможный поток по рёбрам, инцидентным истоку, увеличив избыточный поток для каждой смежной с истоком вершиной на соответствующую величину. Все остальные потока не несут, следовательно, для вершин не смежных с истоком избыточный поток изначально будет нулевым. Также для всех вершин, кроме, естественно, истока, установим высоту, равную нулю.

Более формально это можно записать так:

[math] f(u, v) = \begin{cases} c(u, v), & u = s \\ -c(u, v), & v = s \\ 0, & u \neq s \text{ and } v \neq s \end{cases} [/math]


[math] h(u) = \begin{cases} \left\vert V \right\vert, & u = s \\ 0, & u \neq s \end{cases} [/math]


function initializePreflow(Node s)
    for u [math] \in [/math] V
        h(u) = 0
        e(u) = 0
    for (u, v) [math]\in[/math] E
        f(u, v) = 0
        f(v, u) = 0
    for u: (s, u) [math]\in [/math] E
        f(s, u) = c(s, u)
        f(u, s) = -c(s, u)
        e(u) = c(s, u)
        e(s) -= c(s, u)
    h(s) = |V|

После инициализации будем выполнять операции проталкивания и подъёма в произвольном порядке. Утверждается, что количество данных операций конечно, и после завершения работы алгоритма наш предпоток является максимальным потоком.

function pushRelabelMaxFlow(Node s, Node t)
    initializePreflow(s)
    while e(u) > 0 and (h(u) = h(v) + 1 or [math] \forall [/math] (u, v) [math]\in  E_f [/math] h(u) [math] \leqslant[/math] h(v))
        if e(u) > 0 and h(u) = h(v) + 1
          push(u, v)
        if e(u) > 0 and [math] \forall [/math] (u, v) [math]\in  E_f [/math] h(u) [math] \leqslant[/math] h(v) 
          relabel(u)
Пример сети.
Сеть после запуска потока, остаточная сеть, применение операции [math]\mathrm{relabel}[/math].
Применение операции [math]\mathrm{push}[/math].




















Корректность алгоритма

Для доказательства корректности алгоритма докажем несколько вспомогательных лемм.

Лемма ([math]1[/math]):
Во время выполнения алгоритма [math] \mathrm{pushRelabelMaxFlow} [/math] никакие свойства высоты не нарушаются.
Доказательство:
[math]\triangleright[/math]

Доказательство проведем по числу выполненных операций проталкивания и подъёма.

Для начала покажем, что после выполнения операции [math] \mathrm{initializePreflow} [/math] [math] h [/math] является функцией высоты. Для всех рёбер, не инцидентных [math] s [/math], высота обоих концов равна нулю, что удовлетворяет условиям. Единственными рёбрами [math] (u, v) [/math], для которых не выполняются условия, налагаемые на функцию высоты, то есть для которых [math] h(u) \gt h(v) + 1 [/math], являются рёбра, у которых [math] u = s [/math]. Но после операции [math] \mathrm{initializePreflow} [/math] рёбра являются насыщенными и не принадлежат остаточной сети.

Это будет базой нашей индукции.

Теперь докажем переход: если перед выполнением операции проталкивания или подъёма [math] h [/math] является функцией высоты, то и после выполнения операции она останется функцией высоты. Для этого рассмотрим проталкивание и подъём отдельно.

Покажем, что после окончания операции проталкивания утверждение верно. После выполнения операции [math] \mathrm{push}[/math][math](u, v)[/math] в [math] E_f [/math] может появиться ребро [math] (v, u) [/math], если до операции по ребру [math] (u, v) [/math] протекал нулевой поток, или же ребро [math] (u, v) [/math] может насытиться, и тогда оно перестанет принадлежать остаточной сети. В первом случае [math] h(v) = h(u) - 1 \lt h(u) + 1 [/math], и, следовательно, [math] h [/math] остается функцией высоты. Во втором же случае при удалении ребра [math] (u, v) [/math] из остаточной сети происходит лишь удаление соответствующих ограничений на высоты [math] u [/math] и [math] v [/math], так что [math] h [/math] остается функцией высоты.

Теперь рассмотрим операцию подъёма вершины [math] u [/math]. По определению данной операции гарантируется, что после её выполнения для любого ребра [math] (u, v) \in E_f [/math] выполняется условие [math] h(u) \leqslant h(v) + 1 [/math], то есть все выходящие рёбра удовлетворяют условиям, накладываемым на функцию высоты. Рассмотрим какое-то входящее ребро [math] (w, u) [/math]. Так как до операции [math] h [/math] являлась функцией высоты, то справедливо [math] h(w) \leqslant h(u) + 1 [/math]. После подъёма высота вершины [math] u [/math] увеличивается как минимум на единицу, следовательно, после выполнения данной операции [math] h(w) \lt h(u) + 1 [/math]. Таким образом, [math] h [/math] и после выполнения операции [math] \mathrm{relabel}[/math][math](u) [/math] остается функций высоты.
[math]\triangleleft[/math]


Лемма ([math]2[/math]):
Пусть [math] f [/math] — предпоток в сети [math] G [/math]. Тогда для любой переполненной вершины можно выполнить операцию проталкивания либо операцию подъёма.
Доказательство:
[math]\triangleright[/math]
Рассмотрим вершину [math] u [/math], для которой [math] e(u) \gt 0 [/math]. Для любого ребра [math] (u, v) \in E_f [/math] справедливо [math] h(u) \leqslant h(v) + 1 [/math] по свойствам функции высоты. Если к вершине [math] u [/math] применима операция проталкивания, то лемма доказана. Иначе, для всех рёбер [math] (u, v) \in E_f [/math] выполняется соотношение [math] h(u) \lt h(v) + 1 [/math]. Следовательно, [math] h(u) \leqslant h(v) [/math]. Но тогда данная вершина удовлетворяет условиям операции подъёма, следовательно, к вершине [math] u [/math] можно применить эту операцию.
[math]\triangleleft[/math]


Лемма ([math]3[/math]):
Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. [math] f [/math] и [math] h [/math] — предпоток и функция высоты соответственно. Тогда в остаточной сети [math] G_f [/math] нет пути из [math] s [/math] в [math] t [/math].
Доказательство:
[math]\triangleright[/math]

Докажем от противного.

Предположим, что в [math] G_f [/math] существует путь из [math] s [/math] в [math] t [/math]. Из теоремы о существовании простого пути следует, что в [math] G_f [/math] также существует и простой путь из [math] s [/math] в [math] t [/math]. Тогда пусть [math] p = \left \langle v_0, v_1, \dots, v_k \right \rangle [/math] — простой путь, где [math] v_0 = s [/math] и [math] v_k = t [/math]. А раз [math] p [/math] простой, то [math] k \lt \left\vert V \right\vert [/math]. Поскольку [math] h [/math] — функция высоты, то [math] \forall i \in \{0, 1, \dots, k - 1 \} [/math] справедливо [math] h(v_i) \leqslant h(v_{i+1}) + 1 [/math]. Следовательно, [math] h(s) \leqslant h(t) + k [/math]. А так как по определению функции высоты [math] h(t) = 0 [/math], то [math] h(s) \leqslant k \lt \left\vert V \right\vert [/math], что противоречит условию, что [math] h(s) = \left\vert V \right\vert [/math].
[math]\triangleleft[/math]


Теорема:
Если алгоритм [math] \mathrm{pushRelabelMaxFlow}[/math] завершается, то вычисленный им предпоток [math] f [/math] является максимальным потоком.
Доказательство:
[math]\triangleright[/math]

Для доказательства покажем, что перед каждой проверкой условия в цикле while [math] f [/math] является предпотоком.

Перед началом цикла, после завершения операции [math] \mathrm{initializePreflow}[/math], [math] f [/math] является предпотоком.

Внутри цикла выполняются лишь операции проталкивания и подъёма. Операция подъёма не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъёма не зависит, будет ли [math] f [/math] предпотоком. Операция [math] \mathrm{push}[/math][math](u, v)[/math] применяется, если [math] e(u) \gt 0 [/math], увеличивая поток через ребро [math] (u, v) [/math] на величину, не превышающую избыточный поток вершины [math] u [/math] и остаточную пропускную способность ребра [math] (u, v) [/math]. Следовательно, если перед выполнением операции проталкивания [math] f [/math] являлся предпотоком, то и после выполнения проталкивания [math] f [/math] останется предпотоком.

После завершения алгоритма для каждой вершины [math] u \in V \setminus \{s, t\} [/math] справедливо, что [math] e(u) = 0 [/math], что следует непосредственно из леммы ([math]1[/math]), леммы ([math]2[/math]) и того, что перед выполнением операций проталкивания или подъёма [math] f [/math] является предпотоком. Но тогда [math] f [/math] удовлетворяет условию сохранения потока, то есть сам является потоком.

Поскольку из леммы ([math]1[/math]) следует, что [math] h [/math] является функцией высоты и после завершения алгоритма, то по лемме ([math]3[/math]) в остаточной сети [math] G_f [/math] нет пути из [math] s [/math] в [math] t [/math]. Но тогда по теореме Форда-Фалкерсона [math] f [/math] — максимальный поток.
[math]\triangleleft[/math]

Оценка быстродействия

Чтобы показать, что алгоритм завершает свою работу, найдём максимальное количество операций проталкивания и подъёма. Для этого докажем несколько вспомогательных лемм.

Лемма ([math]4[/math]):
Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math], и [math] f [/math] — предпоток в [math] G [/math]. Тогда из любой переполненной вершины [math] u [/math] существует путь в [math] s [/math] в остаточной сети [math] G_f [/math].
Доказательство:
[math]\triangleright[/math]

Докажем лемму методом от противного.

Пусть для вершины [math] u [/math] верно, что [math] e(u) \gt 0 [/math]. Пусть также [math] U = \{v: u \leadsto v [/math] в [math] G_f \} [/math] и [math] \bar{U} = V \setminus U [/math]. Предположим, что [math] s \in \bar{U} [/math].

Покажем, что для любой пары вершин [math] v \in U [/math] и [math] w \in \bar{U} [/math] верно, что [math] f(w, v) \leqslant 0 [/math]. Если [math] f(w, v) \gt 0 [/math], то [math] f(v, w) \lt 0 [/math]. Но тогда из этого утверждения следует, что [math] c_f(v, w) = c(v, w) - f(v, w) \gt 0 [/math], что не может быть верным, так как в таком случае существует путь [math] u \leadsto v \to w [/math] в остаточной сети [math] G_f [/math], что противоречит выбору вершины [math] w [/math]. Следовательно, для каждой пары вершин [math] v \in U [/math] и [math] w \in \bar{U} [/math] верно, что [math] f(w, v) \leqslant 0 [/math]. Тогда верно и [math] f(\bar{U}, U) \leqslant 0 [/math]. Следовательно [math] e(U) = f(V, U) = f(U, U) + f(\bar{U}, U) = f(\bar{U}, U) \leqslant 0 [/math].

Но по определению избыток потока неотрицателен, из чего следует, что для любой вершины [math] v \in U [/math] [math] e(v) = 0 [/math], в том числе [math] e(u) = 0 [/math], что противоречит условию переполненности вершины [math] u [/math].
[math]\triangleleft[/math]


Лемма ([math]5[/math]):
Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. Тогда во время выполнения алгоритма [math] \mathrm{pushRelabelMaxFlow}[/math] для любой вершины [math] u [/math] в сети [math] G [/math] верно, что [math] h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]
Доказательство:
[math]\triangleright[/math]

По определению функции высоты [math] h(s) = \left\vert V \right\vert [/math] и [math] h(t) = 0 [/math], следовательно для истока и стока утверждение леммы выполнено.

Рассмотрим вершину [math] u [/math] отличную от истока и стока. Изначально [math] h(u) = 0 \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]. Покажем, что после любой операции подъёма [math] h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]. Для того, чтобы мы имели право произвести операцию [math] \mathrm{relabel}[/math][math](u) [/math], вершина [math] u [/math] должна быть переполнена. Тогда по лемме [math]4[/math] существует простой путь [math] p [/math] из [math] u [/math] в [math] s [/math] в остаточной сети [math] G_f [/math]. Рассмотрим этот путь. Пусть [math] p = \left\langle v_0, v_1, \dots, v_k \right\rangle [/math], где [math] v_0 = u [/math] и [math] v_k = s [/math]. Так как путь [math] p [/math] простой, то [math] k \leqslant \left\vert V \right\vert - 1 [/math]. По определению функции высоты имеем, что [math] \forall i \in \{0, 1, \dots, k - 1\} [/math] [math] h(v_i) \leqslant h(v_{i+1}) + 1[/math]. Но тогда для вершин [math] u [/math] и [math] v [/math] верно, что [math] h(u) \leqslant h(s) + \left\vert V \right\vert - 1 = 2 \cdot \left\vert V \right\vert - 1 [/math]
[math]\triangleleft[/math]


На основании предыдущей леммы покажем верхнюю границу числа подъёмов.

Лемма ([math]6[/math]):
Пусть [math] G [/math] — сеть с истоком [math] s [/math] и стоком [math] t [/math]. Тогда во время выполнения алгоритма [math] \mathrm{pushRelabelMaxFlow}[/math] общее число подъёмов не превышает [math] 2 \cdot \left\vert V \right\vert ^2 [/math]
Доказательство:
[math]\triangleright[/math]
Так как высоты истока и стока не изменяются в процессе работы алгоритма, то только [math] \left\vert V \right\vert - 2 [/math] вершин могут быть подняты. Пусть [math] u \in V \setminus \{s, t\}[/math]. Изначально [math] h(u) = 0 [/math], и по лемме ([math]5[/math]) известно, что [math] h(u) \leqslant 2 \cdot \left\vert V \right\vert - 1 [/math]. А так как при выполнении операции [math] \mathrm{relabel}[/math][math](u) [/math] высота вершины увеличивается как минимум на единицу, то максимальное количество подъёмов вершины [math] u [/math] также не превышает [math] 2 \cdot \left\vert V \right\vert - 1 [/math]. Тогда суммарно число подъёмов не превышает [math] (\left\vert V \right\vert - 2 ) \cdot (2 \cdot \left\vert V \right\vert - 1) \leqslant 2 \cdot \left\vert V \right\vert ^2 [/math].
[math]\triangleleft[/math]


Лемма ([math]7[/math]):
После ненасыщающего проталкивания из [math] u [/math] в [math] v [/math] вершина [math] u [/math] перестает быть переполненной.
Доказательство:
[math]\triangleright[/math]
Поскольку проталкивание ненасыщающее, то величина потока, проталкиваемого через ребро [math] (u, v) [/math] должна быть равна [math] e(u) [/math]. После выполнения проталкивания избыточный поток вершины должен уменьшится на величину проталкиваемого потока, следовательно, после ненасыщающего проталкивания из [math] u [/math] в [math] v [/math] величина [math] e(u) = 0 [/math].
[math]\triangleleft[/math]


Следующие две леммы показывают верхнюю границу количества проталкиваний.

Лемма ([math]8[/math]):
Количество насыщающих проталкиваний при выполнение алгоритма [math] \mathrm{pushRelabelMaxFlow}[/math] не превосходит [math] 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert [/math]
Доказательство:
[math]\triangleright[/math]
Возьмем произвольную пару вершин [math] u [/math] и [math] v [/math] и рассмотрим насыщающие проталкивания по рёбрам [math] (u, v) [/math] и [math] (v, u) [/math]. Предположим, что произошло насыщающее проталкивание по ребру [math] (u, v) [/math]. Тогда во время проталкивания [math] h(v) = h(u) - 1 [/math]. Для того, чтобы могло произойти еще одно насыщающее проталкивание по ребру [math] (u, v) [/math], мы должны для начала протолкнуть поток из [math] v [/math] в [math] u [/math], чтобы ребро [math] (u, v) [/math] снова появилось в остаточной сети. Но для этого должно выполняться условие [math] h(v) = h(u) + 1 [/math], то есть высота вершины [math] u [/math] должна увеличится как минимум на [math]2[/math]. По лемме ([math]5[/math]) высота вершины не превышает [math] 2 \cdot\left\vert V \right\vert - 1 [/math], следовательно, количество раз, когда высота вершины может увеличится на [math]2[/math], меньше [math] \left\vert V \right\vert [/math]. Поскольку между двумя насыщающими проталкиваниями высота одной из вершин должна увеличится по меньшей мере на [math]2[/math], то между вершинами [math] u [/math] и [math] v [/math] их будет не более [math] 2 \cdot\left\vert V \right\vert [/math]. Тогда суммарно по всем рёбрам во время работы алгоритма произойдут не более [math] 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert [/math] насыщающих проталкиваний.
[math]\triangleleft[/math]


Лемма ([math]9[/math]):
Количество ненасыщающих проталкиваний при выполнение алгоритма [math] \mathrm{pushRelabelMaxFlow}[/math] не превосходит [math] 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) [/math]
Доказательство:
[math]\triangleright[/math]

Пусть [math] \Phi = \sum \limits_{u: e(u) \gt 0} h(u)[/math]. Так как после завершения алгоритма ни одна из вершин не является переполненной, то и величина [math] \Phi [/math] после выполнения алгоритма должна равняться нулю.

Для начала рассмотрим, каким образом может увеличиваться величина [math] \Phi [/math]. Первое, что может увеличить [math] \Phi [/math], это подъём, поскольку, осуществляя данную операцию, мы не изменяем избыточный поток ни у одной вершины, а лишь увеличиваем высоту одной из них. При каждой операции подъёма [math] \Phi [/math] увеличивается менее чем на [math] 2 \cdot \left\vert V \right\vert [/math], так как подъём не может увеличить высоту вершины больше, чем её максимальная высота, которая согласно лемме ([math]5[/math]) может быть не более [math] 2 \cdot \left\vert V \right\vert - 1 [/math]. А поскольку из леммы ([math]6[/math]) известно, что число подъёмов не превышает [math] 2 \cdot \left\vert V \right\vert ^2 [/math], то суммарно подъёмы всех вершин могут увеличить [math] \Phi [/math] не более чем на [math] 4 \cdot \left\vert V \right\vert^3 [/math].

Во-вторых, величина [math] \Phi [/math] может увеличится при насыщающем проталкивании из [math] u [/math] в [math] v [/math], потому что [math] e(u) \gt 0 [/math] и после насыщающего проталкивания, а вершина [math] v [/math] может стать переполненной. Увеличение меньше [math] 2 \cdot \left\vert V \right\vert [/math], так как изменения высот не происходит, а высота вершины [math] v [/math] не превосходит [math] 2 \cdot \left\vert V \right\vert - 1 [/math]. Но по лемме (8) известно, что количество насыщающих проталкиваний за все время выполнения алгоритма не превосходит [math] 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert [/math], следовательно, за счет насыщающих проталкиваний [math] \Phi [/math] увеличится не более чем на [math] 4 \cdot \left\vert V \right\vert^2 \cdot \left\vert E \right\vert [/math].

Итого, получаем, что величина [math] \Phi [/math] не может быть больше [math] 4 \cdot \left\vert V \right\vert ^2 \cdot (\left\vert V \right\vert + \left\vert E \right\vert) [/math].

Теперь покажем, что ненасыщающее проталкивание уменьшает [math] \Phi [/math] как минимум на единицу. Пусть произошло ненасыщающее проталкивание из вершины [math] u [/math] в [math] v [/math]. Согласно лемме [math]7[/math] после ненасыщающего проталкивания вершина [math] u [/math] перестает быть переполненной, следовательно, [math] \Phi [/math] уменьшается на величину её высоты. После проталкивания вершина [math] v [/math] является переполненной, и поэтому [math] \Phi [/math] могла увеличится на [math] h(v) [/math]. Поскольку [math] h(u) = h(v) - 1 [/math], то при каждом ненасыщающем проталкивании [math] \Phi [/math] уменьшается по меньшей мере на единицу.

Зная верхнюю границу величины [math] \Phi [/math], её значение после выполнения алгоритма и то, что при каждом ненасыщающем проталкивании [math] \Phi [/math] уменьшается минимум на единицу, то можно сделать вывод, что количество ненасыщающих проталкиваний не больше чем [math] 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) [/math].
[math]\triangleleft[/math]


Теорема:
Пусть [math] G [/math] — сеть. Тогда любая реализация метода [math] \mathrm{pushRelabelMaxFlow}[/math] для [math] G [/math] завершает свою работу, и число основных операций составляет [math] O(V^2E) [/math]
Доказательство:
[math]\triangleright[/math]
Из леммы [math]6[/math], леммы [math]8[/math] и леммы [math]9[/math] следует, что число операций подъёма и проталкиваний не превышает [math] 2 \cdot \left\vert V \right\vert ^2 + 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert + 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) = O(V^2E) [/math]. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
[math]\triangleleft[/math]

См. также

Источники