Изменения

Перейти к: навигация, поиск

Метод проталкивания предпотока

Нет изменений в размере, 18:48, 10 декабря 2012
м
Проталкивание (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> увеличивается увеличиваются на эту же величину.
'''push'''(u, v)
403
правки

Навигация