693
правки
Изменения
Нет описания правки
== Определения ==
<!--------oxxx------------------[[Файл:OrGraphAlgoPreflow.png|500px|thumb|Пример]] <!-----скорее всего, надо переместить, ибо тут надо показать переполненные вершины, высоту, все дела...----->
{{Определение
|definition=
Тогда вершина <tex> u \in V \setminus \{s, t\} </tex> будет называться '''переполненной''' (англ. ''overflowing''), если <tex> e(u) > 0 </tex>.
}}
{{Определение
|definition=
Данная операция работает следующим образом: по ребру <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> \exists \mathrm{push} forall </tex>(u, v) '''or''' <tex>\exists in E_f </tex> h(u) <tex> \mathrm{relabel} leqslant</tex>h(uv)) '''if''' e(u)<tex> > 0</tex> '''and''' h(u) = h(v) + <tex>1</tex>
push(u, v)
'''if''' e(u)<tex> > 0</tex> '''and''' <tex> \forall </tex> (u, v) <tex>\in E_f \quad </tex> h(u) <tex> \leqslant </tex> h(v) </tex>
relabel(u)
[[Файл:OrGraphPush0.png|545px|left|Пример сети.]] [[Файл:OrGraphPush1.png|545px|right|Сеть после запуска потока, остаточная сеть, применение операции <tex>\mathrm{relabel}</tex>.]][[Файл:OrGraphPush2.png|545px|left|Применение операции <tex>\mathrm{push}</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> после выполнения алгоритма должна равняться нулю.
{{Теорема
|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>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
