Изменения

:Оценка времени работы следует непосредственно из этого утверждения. :Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <tex>f</tex> {{---}} поток до первой итерации рассматриваемой группы, а <tex>f'</tex> {{---}} поток после последней итерацииэтой группы. Также пусть для простоты обозначений Обозначим за <tex>\varepsilon = '^{*}</tex> минимальное <tex>\varepsilon(f)</tex>такое, что поток <tex>\varepsilonf'=</tex> <tex>\varepsilon(f')</tex>-оптимальный, при этом а за <tex>\varphi'</tex> {{---}} функция функцию потенциалов такаятакую, что <tex>f'</tex> удовлетворяет свойству <tex>\varepsilon'^{*}</tex>-оптимальности. Рассмотрим цикл <tex>C</tex>, отмененный после первой итерации группы. Выбор <tex>k</tex> дает и [[#lemma5|предыдущая лемма]] дают нам следующее неравенство: <tex>\varepsilon' ^{*} \leqslant \varepsilon ^{*} \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon^{*}}{2V}</tex>. :Рассмотрим цикл <tex>C</tex>, отмененный на первой итерации рассматриваемой группы. Поскольку средний вес цикла <tex>C</tex> равен <tex>-\varepsilon^{*}</tex>(см. [[#lemma3|лемму]]), некоторое ребро <tex>uv</tex> цикла <tex>C</tex> должно иметь приведенную стоимость <tex>p_{\varphi'}(uv) \leqslant -\varepsilon ^{*} \leqslant -2V\varepsilon'^{*}</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, каждая группа фиксирует поток на независимом ребре.}}