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