403
правки
Изменения
→Проталкивание (Push)
Как упоминалось ранее, в алгоритме выполняются две основные операции: проталкивание из переполненной вершины избытка потока в смежные вершины, высота которых меньше, чем у переполненной, и подъем вершины.
=== Проталкивание (Push) ===
Операция проталкивания из вершины <tex> u </tex> в вершину <tex> v </tex> может применяться тогда, когда <tex> e(u) > 0 </tex>, то есть вершина <tex> u </tex> является переполненной, <tex> c_f(u, v) > 0 </tex> и <tex> h(u) = h(v) + 1 </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> увеличивается на эту же величину.
=== Подъем (Relabel) ===
