Изменения

|statement=Последовательность из Пусть <tex>f</tex> {{---}} некоторый поток, а <tex>f'</tex> {{---}} поток после <tex>E</tex> отмен циклов минимального среднего веса уменьшает . Тогда <tex>\varepsilon'^{*}</tex> не более чем в <tex>\leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>, где <tex>\varepsilon'^{*}</tex> {{---}} минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> раз<tex>\varepsilon</tex>-оптимальный.

:Рассмотрим такую последовательность. Изначально любое ребро <tex>uv</tex> удовлетворяет свойству <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</tex>. Отмена цикла добавляет в остаточную сеть <tex>G_{f}</tex> только ребра положительной приведенной стоимости (см. [[#lemma4|предыдущую лемму]]) и удаляет из сети <tex>G</tex> как минимум одно ребро. Рассмотрим два случая::#Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа <tex>H</tex> и после <tex>E</tex> отмен граф <tex>H</tex> пуст, что означает, что <tex>f'</tex> {{---}} оптимальный поток, то есть <tex>\varepsilon'^{*}=0</tex>.:#Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть впервые такое случилось на <tex>Ci</tex>-ой итерации, и, соответственно, <tex>C_{i}</tex> {{---}} первый из таких циклов. Для <tex>CC_{i}</tex> имеем, что каждое его ребро обладает приведенной стоимостью как минимум <tex>-\varepsilon_{i}^{*}</tex> (при этом <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} \leqslant \varepsilon^{*}</tex>по [[#lemma4|предыдущей лемме]]), хотя бы одно из ребер <tex>CC_{i}</tex> обладает неотрицательной приведенной стоимостью, и количество ребер в <tex>CC_{i}</tex> не превышает <tex>V</tex>. Тогда средний вес этого цикла <tex>\mu(CC_{i}) = \mumu_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon</tex>. Тогда непосредственно перед отменой <tex>C^{*}</tex>, и <tex>-\muvarepsilon'^{*} \leqslant \varepsilon_{i}^{*}=-\varepsilonmu_{i}^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon</tex> (по [[#lemma3|лемме]]). Поскольку мы [[#lemma4|знаем]], что <tex>\varepsilon^{*}</tex> не увеличивается, доказываемое утверждение верно.}}