276
правок
Изменения
→Сложность
<tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом
<tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
====Доказательство====
Пусть <tex>k=VE(\lceil \log V + 1 \rceil)</tex>. Разобьем работу алгоритма на группы по <tex>k</tex> последовательных итераций. Утверждается, что каждая группа фиксирует поток на независимом ребре <tex>uv</tex>, то есть итерации из другой группы не меняют величину <tex>f(uv)</tex>.
Оценка следует непосредственно из этого утверждения. Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <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 -2n\varepsilon'</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, каждая группа фиксирует поток на независимом ребре.
==Алгоритм поиска цикла минимального среднего веса==
