276
правок
Изменения
→Корректность
:По свойству антисимметричности потока, после отмены цикла <tex>C</tex>, в остаточной сети появятся ребра стоимости <tex>\varepsilon</tex>. Таким образом, свойство <tex>p_{\varphi}(uv) \geqslant -\varepsilon</tex> все еще выполняется.
}}
{{Определение
|definition='''Допустимым графом''' (англ. ''admissible graph'') будем называть такой подграф остаточной сети, что он включает только ребра отрицательной приведенной стоимости. <tex>E=\{uv \in E_{f}\;|\; p_{\varphi}(uv) < 0\}</tex>
}}
{{Лемма
|id=lemma5
|statement=Последовательность из <tex>m</tex> отмен циклов минимального среднего веса уменьшает <tex>\varepsilon(f)</tex> в не более чем <tex>1-\dfrac{1}{n}</tex> раз.
|proof=
:Рассмотрим последовательность <tex>m</tex> отмен циклов минимального среднего веса. Изначально любое ребро <tex>uv</tex> удовлетворяет свойству <tex>p_{\varphi}(uv) \leqslant -\varepsilon</tex>. Отмена цикла добавляет в остаточную сеть <tex>G_{f}</tex> только ребра положительной приведенной стоимости (см. [[#lemma4|предыдущую лемму]]) и удаляет из сети <tex>G</tex> как минимум одно ребро. Рассмотрим два случая:
#Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа <tex>E</tex> и после <tex>m</tex> отмен граф <tex>E</tex> пуст, что означает, что <tex>f</tex> {{---}} оптимальный поток, то есть <tex>\varepsilon(f)=0</tex>.
#Некоторые из отмененных циклов содержат ребра неотрицательной приведенной стоимости. Пусть <tex>C</tex> {{---}} первый из таких циклов. Каждое ребро в <tex>C</tex> обладает приведенной стоимостью как минимум <tex>-\varepsilon</tex>, хотя бы одно из ребер <tex>C</tex> обладает неотрицательной приведенной стоимостью, количество ребер в <tex>C</tex> не превышает <tex>V</tex>. Тогда средний вес цикла <tex>C</tex> как минимум <tex>-\left(1-\dfrac{1}{n}\right)\varepsilon</tex>. Тогда непосредственно перед отменой <tex>C</tex>, <tex>\varepsilon(f) \leqslant \left(1-\dfrac{1}{n}\right)\varepsilon</tex> (по [[#lemma3|лемме]]). Поскольку мы [[#lemma4|знаем]], что <tex>\varepsilon(f)</tex> не увеличивается, доказываемое утверждение верно.}}
{{Лемма
