693
правки
Изменения
Нет описания правки
Данная операция работает следующим образом: по ребру <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> стала равна нулю. Все остальные проталкивания будем называть '''ненасыщающими'''. Подобная классификация проталкиваний понадобится нам при оценке их количества.
В результате подъёма высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток.
'''function''' relabel('''Node''' u): h(u) = min({h(v): f(u, v) - c(u, v) < <tex>0</tex>) } + <tex>1</tex>;
== Схема алгоритма ==
'''function''' initializePreflow('''Node''' s):
'''for''' u <tex> \in </tex> V
h(u) = <tex>0</tex> e(u) = <tex>0</tex>
'''for''' (u, v) <tex>\in</tex> E
f(u, v) = <tex>0</tex> f(v, u) = <tex>0</tex>
'''for''' u: (s, u) <tex>\in </tex> E
f(s, u) = 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 forall </tex> push(u, v) '''or''' <tex>\exists in E_f </tex> relabelh(u) <tex> \leqslant</tex> h(v)) '''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 </tex> E_f<tex>\quad</tex> h(u)<tex> \leqslant</tex> h(v)
relabel(u)
[[Файл:OrGraphPush0.png|500px545px|left|Пример сети.]] [[Файл:OrGraphPush1.png|500px545px|right|Сеть после запуска потока, остаточная сеть, применение операции <tex>\mathrm{relabel}</tex>.]][[Файл:OrGraphPush2.png|500px545px|left|Применение операции <tex>\mathrm{push}</tex>.]]``
== Корректность алгоритма ==
