276
правок
Изменения
→Корректность
|statement=Отмена цикла минимального среднего веса не увеличивает <tex>\varepsilon^{*}</tex>.
|proof=
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл <tex>C</tex> ребро <tex>uv</tex> удовлетворяет свойству <tex>\varepsilon(f)^{*}</tex>-оптимальности: <tex>p_{\varphi}(uv) \geqslant -\varepsilon(f)^{*}</tex>. :По [[#lemma3|предыдущей лемме]], <tex>\varepsilon(f)^{*}=-\mu(f)^{*}</tex>, то есть <tex>p_{\varphi}(uv) \geqslant \mu(f)^{*}</tex>. Но поскольку <tex>\mu(f)^{*}</tex> {{---}} средний вес цикла, то <tex>p_{\varphi}(uv) = \mu(f) ^{*} = -\varepsilon(f)^{*}</tex>.
:По свойству антисимметричности потока, после отмены цикла <tex>C</tex>, в остаточной сети появятся ребра стоимости <tex>\varepsilon</tex>. Таким образом, свойство <tex>p_{\varphi}(uv) \geqslant -\varepsilon</tex> все еще выполняется.
}}
