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