276
правок
Изменения
→Корректность
{{Лемма
|id=lemma5
|statement=Последовательность из <tex>m</tex> отмен циклов минимального среднего веса уменьшает <tex>\varepsilon(f)</tex> в не более чем <tex>\left(1-\dfrac{1}{nV}\right)^{m}</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>\mu(C) \geqslant -\left(1-\dfrac{1}{nV}\right)\varepsilon</tex>. Тогда непосредственно перед отменой <tex>C</tex>, <tex>\varepsilon(f) \leqslant \left(1-\dfrac{1}{nV}\right)\varepsilon</tex> (по [[#lemma3|лемме]]). Поскольку мы [[#lemma4|знаем]], что <tex>\varepsilon(f)</tex> не увеличивается, доказываемое утверждение верно.}}
{{Лемма
|statement=Пусть <tex>k=VE(\lceil \log V + 1 \rceil)</tex>. Разобьем работу алгоритма на группы по <tex>k</tex> последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре <tex>uv</tex>, то есть итерации из другой группы не меняют величину <tex>f(uv)</tex>.
|proof=
Оценка следует непосредственно из этого утверждения. Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <tex>f</tex> {{---}} поток до первой итерации рассматриваемой группы, а <tex>f'</tex> {{---}} поток после последней итерации. Также пусть для простоты обозначений <tex>\varepsilon = \varepsilon(f)</tex>, <tex>\varepsilon'=\varepsilon(f')</tex>, при этом <tex>\varphi'</tex> {{---}} функция потенциалов такая, что <tex>f'</tex> удовлетворяет свойству <tex>\varepsilon'</tex>-оптимальности. Рассмотрим цикл <tex>C</tex>, отмененный после первой итерации группы. Выбор <tex>k</tex> дает нам <tex>\varepsilon' \leqslant \varepsilon \left(1-\dfrac{1}{V} \right)^{V(\log V + 1)} \leqslant \dfrac{\varepsilon}{2V}</tex>. Поскольку средний вес цикла <tex>C</tex> равен <tex>-\varepsilon</tex>, некоторое ребро <tex>uv</tex> цикла <tex>C</tex> должно иметь приведенную стоимость <tex>p_{\varphi'}(uv) \leqslant -\varepsilon \leqslant -2n2V\varepsilon'</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, каждая группа фиксирует поток на независимом ребре.}}
==Алгоритм поиска цикла минимального среднего веса==
