403
правки
Изменения
м
→Корректность алгоритма
{{Лемма
|about = 2
|id = Лемма 2Лемма2
|statement =
Пусть <tex> f </tex> {{---}} предпоток в сети <tex> G </tex>. Тогда для любой переполненной вершины можно выполнить операцию проталкивания либо операцию подъема.
{{Лемма
|about = 3
|id = Лемма 3Лемма3
|statement =
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. <tex> f </tex> и <tex> h </tex> {{---}} предпоток и функция высоты соответственно. Тогда в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>.
Внутри цикла выполняются лишь операции проталкивания и подъема. Операция подъема не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъема не зависит, будет ли <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|леммы(1)]], [[#Лемма 2Лемма2|леммы(2)]] и того, что перед выполнением операции проталкивания или подъема <tex> f </tex> является предпотоком. Но тогда <tex> f </tex> удовлетворяет условию сохранения потока, то есть сам является потоком.
Поскольку из [[#Лемма 1Лемма1|леммы(1)]] следует, что <tex> h </tex> является функцией высоты и после завершения алгоритма, то по [[#Лемма 3Лемма3|лемме(3)]] в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>. Но тогда по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] <tex> f </tex> {{---}} максимальный поток.
}}
