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