1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Определения ==
<!--------oxxx------------------[[Файл:OrGraphAlgoPreflow.png|500px|thumb|Пример]] <!-----скорее всего, надо переместить, ибо тут надо показать переполненные вершины, высоту, все дела...----->
{{Определение
|definition=
Тогда вершина <tex> u \in V \setminus \{s, t\} </tex> будет называться '''переполненной''' (англ. ''overflowing''), если <tex> e(u) > 0 </tex>.
}}
[[Файл:OrGraphExample.png|left|thumb|Пример сети с истоком A и стоком D. Вершина B является переполненной.]]
{{Определение
|definition=
В итоге, у нас не останется ни одной переполненной вершины, та часть потока, которая могла пройти к стоку, окажется там, остальная же вернется в исток. В такой ситуации предпоток превращается в обычный поток, так как для каждой вершины выполняется условие сохранения потока. Как будет показано далее, предпоток становится не только обычным, но и максимальным потоком.
<!-----[[Файл:OrGraphAlgoPreflow.png|550px|thumb|left|Пример]][[Файл:OrGraphAlgoPreflow.png|550px|thumb|left|something poxozhee]]---->
== Операции ==
Данная операция работает следующим образом: по ребру <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>.
В результате подъёма высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.
'''function''' relabel('''Node''' u): h(u) = min({h(v): f(u, v) - c(u, v) < 0) } + 1;
== Схема алгоритма ==
\begin{cases}
c(u, v), & u = s \\
-c(u, v, u), & v = s \\
0, & u \neq s \text{ and } v \neq s
\end{cases}
'''function''' initializePreflow('''Node''' s): '''for''' u <tex> u \in V </tex>V h(u) = 0; e(u) = 0; '''for''' <tex> (u, v) <tex>\in E </tex>E f(u, v) = 0; f(v, u) = 0; '''for''' <tex> u: (s, u) <tex>\in E </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> \exists 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{pushrelabel} </tex> или .]][[Файл:OrGraphPush2.png|545px|left|Применение операции <tex> \mathrm{relabelpush} </tex>.]] выбрать операцию и выполнить её
== Корректность алгоритма ==
{{Лемма
|about = <tex>1</tex>
|id = Лемма1
|statement =
{{Лемма
|about = <tex>2</tex>
|id = Лемма2
|statement =
{{Лемма
|about = <tex>3</tex>
|id = Лемма3
|statement =
Внутри цикла выполняются лишь операции проталкивания и подъёма. Операция подъёма не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъёма не зависит, будет ли <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 =
{{Лемма
|about = <tex>5</tex>
|id = Лемма5
|statement =
По определению функции высоты <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 =
Следующие две леммы показывают верхнюю границу количества проталкиваний.
{{Лемма
|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{pushRealbelMaxFlowpushRelabelMaxFlow}</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{pushRealbelMaxFlowpushRelabelMaxFlow}</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>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
}}
