403
правки
Изменения
→Корректность алгоритма
После завершения алгоритма для каждой вершины <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> {{---}} максимальный поток.
}}
