5
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Предпотоком''' ('англ. ''preflow''') будем называть функцию <tex> f: V \times V \rightarrow \mathbb{R} </tex>, удовлетворяющую следующим свойствам:
1) <tex> f(u, v) = -f(v, u) </tex> (антисимметричность)
{{Определение
|definition=
'''Избыточным потоком''' ('англ. ''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>.
}}
{{Определение
|definition=
Функция <tex> h: V \rightarrow \mathbb{Z}_+</tex> называется '''высотой вершины''' ('англ. ''vertex label'''), если она удовлетворяет условиям:
1) <tex> h(s) = \left\vert V \right\vert </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, 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> увеличиваются на эту же величину.
'''pushfunction'''push(u, v):
d = min(e(u), c(u, v) - f(u, v));
f(u, v) += d;
В результате подъема высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.
'''relabelfunction'''relabel(u):
h(u) = min(h(v): f(u, v) - c(u, v) > 0) + 1;
'''initializePreflowfunction'''initializePreflow(s) '''for''' <tex> \forall u \in V </tex>
h(u) = 0;
e(u) = 0;
'''for''' <tex> \forall (u, v) \in E </tex>
f(u, v) = 0;
f(v, u) = 0;
'''for''' <tex> \forall u: (s, u) \in E </tex>
f(s, u) = c(s, u);
f(u, s) = -c(s, u);
После инициализации будем выполнять операции проталкивания и подъема в произвольном порядке. Утверждается, что количество данных операций конечно, и после завершения работы алгоритма наш предпоток является максимальным потоком.
'''pushRelabelMaxFlowfunction'''pushRelabelMaxFlow(s, t)
initializePreflow(s);
'''while''' существует <tex> \exists </tex> применимая операция <tex> \mathrm{push } </tex> или <tex> \mathrm{relabel} </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> остается функций высоты.
}}
{{Теорема
|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|леммы (1)]], [[#Лемма2|леммы (2)]] и того, что перед выполнением операций проталкивания или подъема <tex> f </tex> является предпотоком. Но тогда <tex> f </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|лемме (4)]] существует простой путь <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>
}}
|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|лемме (5)]] известно, что <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>.
}}
|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> должна увеличится как минимум на 2. По [[#Лемма5|лемме (5)]] высота вершины не превышает <tex> 2 \cdot\left\vert V \right\vert - 1 </tex>, следовательно, количество раз, когда высота вершины может увеличится на 2, меньше <tex> \left\vert V \right\vert </tex>. Поскольку между двумя насыщающими проталкиваниями высота одной из вершин должна увеличится по меньшей мере на 2, то между вершинами <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> насыщающих проталкиваний.
|id = Лемма9
|statement =
Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> \mathrm{pushRealbelMaxFlow }</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> после выполнения алгоритма должна равняться нулю.
{{Теорема
|statement =
Пусть <tex> G </tex> {{---}} сеть. Тогда любая реализация метода <tex> pushRelabelMaxFlow \mathrm{pushRealbelMaxFlow}</tex> для <tex> G </tex> завершает свою работу, и число основных операций составляет <tex> O(V^2E) </tex>
|proof =
Из [[#Лемма6|леммы (6)]], [[#Лемма8|леммы (8)]] и [[#Лемма9|леммы (9)]] следует, что число операций подъема и проталкиваний не превышает <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>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
