Изменения
→Корректность
{{Определение
|definition=Будем говорить, что поток <tex>f</tex> {{---}} '''<tex>\varepsilon</tex>-оптимальный''' (англ. ''<tex>\varepsilon</tex>-optimal''), если <tex>\exists \varphi</tex> такая, что <tex>\forall uv: c_{f}(uv) > 0 \qquad p_{\varphi}(uv) \geqslant -\varepsilon</tex>.}}
{{Лемма
|statement=Если стоимости целочисленны и поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный, где <tex>\varepsilon < \dfrac{1}{n}</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости.
|proof=
:Рассмотрим цикл в остаточной сети <tex>C</tex>. Заметим, что <tex>p(C)=p_{\varphi}(C)</tex>.
:Возьмем <tex>\varphi</tex> такое, чтобы стоимости всех ребер в <tex>C</tex> были не меньше <tex>-\varepsilon</tex>. Тогда стоимость всего цикла <tex>p_{\varphi}(C)\geqslant -n\cdot \varepsilon</tex> (в цикле не больше <tex>n</tex> ребер). Таким образом, <tex>p_{\varphi}(C) > -1</tex>, то есть <tex>p(C) > -1</tex>. Но исходные пропускные способности были целочисленными, поэтому <tex>p(C) > 0</tex>, а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, <tex>f</tex> {{---}} поток минимальной стоимости.
}}
===Сложность===
