276
правок
Изменения
→Корректность
{{Лемма
|id=lemma2
|statement=Если стоимости целочисленны и поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный, где <tex>\varepsilon < \dfrac{1}{nV}</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 -nV\cdot \varepsilon</tex> (в цикле не больше <tex>nV</tex> ребер). Таким образом, <tex>p_{\varphi}(C) > -1</tex>, то есть <tex>p(C) > -1</tex>. Но исходные пропускные способности были целочисленными, поэтому <tex>p(C) \geqslant 0</tex>, а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, <tex>f</tex> {{---}} поток минимальной стоимости.}}
Обозначим за <tex>\mu(f)</tex> минимальную величину среди средних весов циклов для потока <tex>f</tex>, а за <tex>\varepsilon(f)</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный.
