Изменения
→Корректность
:Предположим, что существуют <tex>\varphi</tex> и <tex>\varepsilon</tex> такие, что <tex>\varepsilon > -\mu(f)</tex> или <tex>-\varepsilon < \mu(f)</tex>.
:Рассмотрим такое ребро <tex>uv</tex>, входящее в цикл, что величина <tex>p_{\varphi}(uv)</tex> минимальна. Тогда верно следующее: <tex>p_{\varphi}(uv) \leqslant \mu(f)</tex>, то есть <tex>p_{\varphi}(uv) < -\varepsilon</tex>, что означает, что <tex>f</tex> не является <tex>\varepsilon</tex>-оптимальным. Получено противоречие, и, значит, <tex>\varepsilon(f) \leqslant -\mu(f)</tex>.
}}
{{Лемма
|statement=Отмена цикла минимального среднего веса не увеличивает <tex>\varepsilon(f)</tex>.
|proof=
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл <tex>C</tex> ребро <tex>uv</tex> удовлетворяет свойству <tex>\varepsilon(f)</tex>-оптимальности: <tex>p_{\varphi}(uv) \geqslant -\varepsilon(f)</tex>.
:По предыдущей лемме, <tex>\varepsilon(f)=-\mu(f)</tex>, то есть <tex>p_{\varphi}(uv) \geqslant \mu(f)</tex>. Но поскольку <tex>\mu(f)</tex> {{---}} средний вес цикла, то <tex>p_{\varphi}(uv) = \mu(f) = -\varepsilon(f)</tex>.
:По свойству антисимметричности потока, после отмены цикла <tex>C</tex>, в остаточной сети появятся ребра стоимости <tex>\varepsilon</tex>. Таким образом, свойство <tex>p_{\varphi}(uv) \geqslant -\varepsilon</tex> все еще выполняется.
}}
