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