276
правок
Изменения
→Корректность
:Рассмотрим теперь некоторое ребро <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>.}}
|statement=Если стоимости целочисленны и поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный, где <tex>\varepsilon < \dfrac{1}{V}</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости.
|proof=
:Рассмотрим цикл в остаточной сети <tex>C</tex>. Заметим, что <tex>p(C)=p_{\varphi}(C)</tex>(для доказательства этого факта достаточно расписать <tex>p_{\varphi}(C)</tex> по определению).
:Возьмем <tex>\varphi</tex> такое, что стоимости всех ребер в <tex>C</tex> не меньше <tex>-\varepsilon</tex>. Тогда стоимость всего цикла <tex>p_{\varphi}(C)\geqslant -V\cdot \varepsilon</tex> (в цикле не больше <tex>V</tex> ребер). Таким образом, <tex>p_{\varphi}(C) > -1</tex>, то есть <tex>p(C) > -1</tex>. Но исходные пропускные способности были целочисленными, поэтому <tex>p(C) \geqslant 0</tex>, а это означает, что в остаточной сети нет отрицательных циклов, и, соответственно, <tex>f</tex> {{---}} поток минимальной стоимости.}}
Обозначим за <tex>\mu(f)^{*}</tex> минимальную величину среди средних весов циклов для потока <tex>f</tex>, а за <tex>\varepsilon(f)^{*}</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный.
{{Лемма
|id=lemma3
|statement=Если <tex>f</tex> {{---}} поток не минимальной стоимости, то <tex>\varepsilon(f)^{*}=-\mu(f)^{*}</tex>.
|proof=
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса в остаточной сети.*Покажем, что <tex>\mu(f) ^{*} \geqslant -\varepsilon(f)</tex>.:Рассмотрим в остаточной сети некоторый цикл <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>.
*Теперь покажем, что <tex>\mu(f) ^{*} \leqslant -\varepsilon(f)^{*}</tex>.:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса в остаточной сети. Поскольку поток <tex>f</tex> не минимален, в остаточной сети существует отрицательный цикл, и тогда <tex>\mu(C)=\mu(f) ^{*} < 0</tex>. :Предположим, что существуют <tex>\varphi</tex> и <tex>\varepsilon</tex> такие, что <tex>\varepsilon > -\mu(f)^{*}</tex> или <tex>-\varepsilon < \mu(f)^{*}</tex>. :Рассмотрим такое ребро <tex>uv</tex>, входящее в цикл, что величина <tex>p_{\varphi}(uv)</tex> минимальна. Тогда верно следующее: <tex>p_{\varphi}(uv) \leqslant \mu(f)^{*}</tex>, то есть <tex>p_{\varphi}(uv) < -\varepsilon</tex>, что означает, что <tex>f</tex> не является <tex>\varepsilon</tex>-оптимальным. Получено противоречие, и, значит, <tex>\varepsilon(f) ^{*} \leqslant -\mu(f)^{*}</tex>.
}}
{{Лемма
|id=lemma4
|statement=Отмена цикла минимального среднего веса не увеличивает <tex>\varepsilon(f)^{*}</tex>.
|proof=
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл <tex>C</tex> ребро <tex>uv</tex> удовлетворяет свойству <tex>\varepsilon(f)</tex>-оптимальности: <tex>p_{\varphi}(uv) \geqslant -\varepsilon(f)</tex>.
