Изменения

:Поскольку поток Пусть <tex>p'(uv)=p(uv)-\mu^{*}</tex> для любого <tex>uv \in E_{f}</tex> не минимален. Логичным будет также обозначить для некоторого цикла <tex>C</tex> за <tex>\mu'(C)</tex> величину <tex>\dfrac{p'(C)}{\texttt{len}(C)}</tex>. Таким образом, в остаточной сети существует отрицательный циклдля любого цикла <tex>C</tex>, и тогда <tex>\mu'(C)=\mu(C)-\mu^{*} < \geqslant 0</tex>. :ПредположимДалее проведем рассуждения, что аналогичные доказательству [[#lemma1|первой леммы]].:Добавим вершину <tex>fa</tex> является и проведем из нее ребро стоимости <tex>\varepsilon0</tex>-оптимальным при во все вершины графа <tex>\varepsilon > -\mu^G_{*f}</tex>. :Рассмотрим такое ребро В качестве <tex>\varphi(u)</tex> выберем стоимость (<tex>p'(au)</tex>) минимального пути из <tex>uva</tex>, входящее в цикл <tex>Cu</tex>. :Таким образом, что величина <tex>p_{\varphi}(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv)- \mu^{*}</tex> максимальна. Тогда верно следующее: Отсюда получаем, что <tex>p_{\varphi}(uv) \geqslant \mu^{*}</tex> для любого ребра <tex>uv</tex> из остаточной сети <tex>E_{f}</tex>, то есть что означает, что <tex>f</tex> {{---}} <tex>(-\mu^{*})</tex>-оптимален. По оптимальный, и, по определению <tex>\varepsilon^{*}</tex>, <tex>\varepsilon^{*} \leqslant -\mu^{*}</tex>.