276
правок
Изменения
→Корректность
{{Лемма
|statement=Если <tex>f</tex> {{---}} поток минимальной стоимости, то <tex>\exists \varphi</tex> такое, что <tex>\forall uv: \; c_{f}(uv) > 0 \qquad p_{\varphi}(uv) \geqslant 0</tex>.
|proof=
:Рассмотрим [[Дополняющая сеть, дополняющий путь|остаточную сеть]] {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]</ref>.
:Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость минимального пути из <tex>a</tex> в <tex>u</tex>.
:Рассмотрим теперь некоторое ребро <tex>uv</tex>. Понятно, что <tex>\varphi(v) \leqslant \varphi(u) + p(uv)</tex>. (Здесь сравниваются минимальный путь <tex>a \rightsquigarrow v</tex> и путь <tex>a \rightsquigarrow u \rightarrow v</tex>). Перенеся <tex>\varphi(v)</tex> в другую часть неравенства, получаем <tex>0 \leqslant \varphi(u) + p(uv) - \varphi(v)</tex> или <tex>0 \leqslant p_{\varphi}(uv)</tex>, что и требовалось доказать.}}
{{Определение
|definition=Будем говорить, что поток <tex>f</tex> {{---}} '''<tex>\varepsilon</tex>-оптимальный''' (англ. ''<tex>\varepsilon</tex>-optimal''), если <tex>\exists \varphi</tex> такая, что <tex>\forall uv: c_{f}(uv) > 0 \qquad p_{\varphi}(uv) \geqslant -\varepsilon</tex>.}}
:Рассмотрим цикл в остаточной сети <tex>C</tex>. Заметим, что <tex>p(C)=p_{\varphi}(C)</tex>.
:Возьмем <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>\varepsilon(f)</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный.{{Лемма|statement=Если <tex>f</tex> {{---}} поток не минимальной стоимости, то <tex>\varepsilon(f)=-\mu(f)</tex>.|proof=:Рассмотрим в остаточной сети некоторый цикл <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>.
}}
