276
правок
Изменения
→Корректность
:Возьмем <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) \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>-оптимальный.
{{Лемма
|statement=Если <tex>f</tex> {{---}} поток не минимальной стоимости, то <tex>\varepsilon(f)=-\mu(f)</tex>.
|proof=
*Покажем, что <tex>\mu(f) \geqslant -\varepsilon(f)</tex>.
:Рассмотрим в остаточной сети некоторый цикл <tex>C</tex>.
:Поскольку поток <tex>f</tex> является <tex>\varepsilon(f)</tex>-оптимальным, верно следующее: <tex>p(C) = p_{\varphi}(C) \geqslant -\texttt{len}(C) \cdot \varepsilon(f)</tex> или <tex>\dfrac{p(C)}{\texttt{len}(C)} \geqslant -\varepsilon(f) </tex>, то есть <tex>\mu(C) \geqslant -\varepsilon(f)</tex>, а поскольку это верно для любого цикла, то и <tex>\mu(f) \geqslant -\varepsilon(f)</tex>.
*Теперь покажем, что <tex>\mu(f) \leqslant -\varepsilon(f)</tex>.
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса в остаточной сети. Поскольку поток <tex>f</tex> не минимален, в остаточной сети существует отрицательный цикл, и тогда <tex>\mu(C)=\mu(f) < 0</tex>.
:Предположим, что существуют <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>.
}}
