403
правки
Изменения
→Корректность алгоритма
|id = Лемма 2
|statement =
|proof =
Рассмотрим вершину <tex> u </tex>, для которой <tex> e(u) > 0 </tex>. Для любого ребра <tex> (u, v) \in E_f </tex> справедливо <tex> h(u) \leqslant h(v) + 1 </tex> по свойствам функции высоты. Если к вершине <tex> u </tex> применима операция проталкивания, то лемма доказана. Иначе, для всех ребер <tex> (u, v) \in E_f </tex> выполняется соотношение <tex> h(u) < h(v) + 1 </tex>. Следовательно, <tex> h(u) \leqslant h(v) </tex>. Но тогда данная вершина удовлетворяет условиям операции подъема, следовательно, к вершине <tex> u </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)]], [[#Лемма 2|леммы(2)]] и того, что перед выполнением операции проталкивания или подъема <tex> f </tex> является предпотоком. Но тогда <tex> f </tex> удовлетворяет условию сохранения потока, то есть сам является потоком.
}}
