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