403
правки
Изменения
м
→Корректность алгоритма
Внутри цикла выполняются лишь операции проталкивания и подъема. Операция подъема не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъема не зависит, будет ли <tex> f </tex> предпотоком. Операция <tex> push(u, v) </tex> применяется, если <tex> e(u) > 0 </tex>, увеличивая поток через ребро <tex> (u, v) </tex> на величину, не превышающую избыточный поток вершины <tex> u </tex> и остаточную пропускную способность ребра <tex> (u, v) </tex>. Следовательно, если перед выполнением операции проталкивания <tex> f </tex> являлся предпотоком, то и после выполнения проталкивания <tex> f </tex> останется предпотоком.
После завершения алгоритма для каждой вершины <tex> u \in V \setminus \{s, t\} </tex> справедливо, что <tex> e(u) = 0 </tex>, что следует непосредственно из [[#Лемма1|леммы (1)]], [[#Лемма2|леммы (2)]] и того, что перед выполнением операции операций проталкивания или подъема <tex> f </tex> является предпотоком. Но тогда <tex> f </tex> удовлетворяет условию сохранения потока, то есть сам является потоком.
Поскольку из [[#Лемма1|леммы (1)]] следует, что <tex> h </tex> является функцией высоты и после завершения алгоритма, то по [[#Лемма3|лемме (3)]] в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>. Но тогда по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] <tex> f </tex> {{---}} максимальный поток.
