403
правки
Изменения
→Подъем (Relabel)
По своему результату все проталкивания можно разделить на 2 группы. Будем называть проталкивание из вершины <tex> u </tex> в вершину <tex> v </tex> '''насыщающим''', если после него остаточная пропускная способность ребра <tex> (u, v) </tex> стала равна нулю. Все остальные проталкивания будем называть '''ненасыщающими'''. Подобная классификация проталкиваний понадобится нам при оценке времени работы алгоритма.
=== Подъем (Relabelrelabel) ===Операция подъема применима для вершины <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> произвести нельзя. В результате подъема высота текущей вершины становится на единицу больше высоты самый низкой смежной вершины в остаточной сети, вследствие чего появляется как минимум одно ребро, по которому можно протолкнуть поток. <pre>relabel(u) h(u) = min(h(v): f(u, v) - c(u, v) > 0) + 1;</pre>
== Схема алгоритма ==
