276
правок
Изменения
Нет описания правки
{{Определение
|definition='''Средним весом''' (англ. ''mean weight'') цикла будем называть отношение его стоимости к его длине <tex>\mu (C)=\dfrac{p(C)}{\texttt{len}(C)}</tex>}}
Данный алгоритм заключается в последовательной отмене циклов минимального среднего веса в [[Дополняющая сеть, дополняющий путь|остаточной сети]] посредством их насыщения. Алгоритм работает до тех пор, пока минимальный средний вес циклов не окажется положительным, что будет означать, что поток минимальной стоимости найден.
* '''Шаг 1'''. Рассмотрим некоторый поток <tex>f</tex>.
* '''Шаг 2'''. Найдем цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geqslant 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
===Сложность===
Для сетей с целочисленными стоимостями<tex>O(VE\cdot VE\log{CV})</tex>, с вещественными {{---}} <tex>O(VE\cdot VE^{2}\log{V})</tex>, при этом.В обоих случаях <tex>O(VE)</tex> времени тратится на поиск цикла минимального среднего веса.
===Корректность===
{{Лемма
|id=lemma1
|about=№1
|statement=Если <tex>f</tex> {{---}} поток минимальной стоимости, то <tex>\exists \varphi</tex> такое, что <tex>\forall uv: \; c_{f}(uv) > 0 \qquad p_{\varphi}(uv) \geqslant 0</tex>.
|proof=
:Рассмотрим [[Дополняющая сеть, дополняющий путь|остаточную сеть]] {{---}} граф <tex>G_{f}</tex>. В нем нет отрицательных циклов, так как <tex>f</tex> {{---}} поток минимальной стоимости<ref>[[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]</ref>.
:Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость минимального пути из <tex>a</tex> в <tex>u</tex>.
:Рассмотрим теперь некоторое ребро <tex>uv</tex>. Понятно, что <tex>\varphi(v) \leqslant \varphi(u) + p(uv)</tex>. (Здесь сравниваются минимальный путь <tex>a \rightsquigarrow v</tex> и путь <tex>a \rightsquigarrow u \rightarrow v</tex>). Перенеся <tex>\varphi(v)</tex> в другую часть неравенства, получаем <tex>0 \leqslant \varphi(u) + p(uv) - \varphi(v)</tex> или <tex>0 \leqslant p_{\varphi}(uv)</tex>, что и требовалось доказать.}}
{{Определение
{{Лемма
|id=lemma2
|about=№2
|statement=Если стоимости целочисленны и поток <tex>f</tex> {{---}} <tex>\varepsilon</tex>-оптимальный, где <tex>\varepsilon < \dfrac{1}{V}</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости.
|proof=
{{Лемма
|id=lemma3
|about=№3
|statement=Если <tex>f</tex> {{---}} поток не минимальной стоимости, то <tex>\varepsilon^{*}=-\mu^{*}</tex>.
|proof=
*Теперь покажем, что <tex>\mu^{*} \leqslant -\varepsilon^{*}</tex>.
:Пусть <tex>p'(uv)=p(uv)-\mu^{*}</tex> для любого <tex>uv \in E_{f}</tex>. Логичным будет также обозначить для некоторого цикла <tex>C</tex> за <tex>\mu'(C)</tex> величину <tex>\dfrac{p'(C)}{\texttt{len}(C)}</tex>. Таким образом, для любого цикла <tex>C</tex>, <tex>\mu'(C)=\mu(C)-\mu^{*}\geqslant 0</tex>.
:Далее проведем рассуждения, аналогичные доказательству [[#lemma1|первой леммы№1]].
:Добавим вершину <tex>a</tex> и проведем из нее ребро стоимости <tex>0</tex> во все вершины графа <tex>G_{f}</tex>. В качестве <tex>\varphi(u)</tex> выберем стоимость (считая стоимостью функцию <tex>p'</tex>) минимального пути из <tex>a</tex> в <tex>u</tex>.
:Таким образом, <tex>\varphi(v) \leqslant \varphi(u) + p'(uv) = \varphi(u) + p(uv) - \mu^{*}</tex>. Отсюда получаем, что <tex>p_{\varphi}(uv) \geqslant \mu^{*}</tex> для любого ребра <tex>uv</tex> из остаточной сети <tex>E_{f}</tex>, что означает, что <tex>f</tex> {{---}} <tex>(-\mu^{*})</tex>-оптимальный, и, по определению <tex>\varepsilon^{*}</tex>, <tex>\varepsilon^{*} \leqslant -\mu^{*}</tex>.
{{Лемма
|id=lemma4
|about=№4
|statement=Отмена цикла минимального среднего веса не увеличивает <tex>\varepsilon^{*}</tex>.
|proof=
:Пусть <tex>C</tex> {{---}} цикл минимального среднего веса, который мы хотим отменить на текущем шаге нашего алгоритма. Перед тем, как мы отменим этот цикл, любое ребро в остаточной сети, в том числе, любое входящее в цикл <tex>C</tex> ребро <tex>uv</tex> удовлетворяет свойству <tex>\varepsilon^{*}</tex>-оптимальности: <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</tex>.
:По [[#lemma3|предыдущей лемме№3]], <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> все еще выполняется.
}}
{{Лемма
|id=lemma5
|about=№5
|statement=Пусть <tex>f</tex> {{---}} некоторый поток, а <tex>f'</tex> {{---}} поток после <tex>E</tex> отмен циклов минимального среднего веса. Тогда <tex>\varepsilon'^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>, где <tex>\varepsilon'^{*}</tex> {{---}} минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> <tex>\varepsilon</tex>-оптимальный.
|proof=
:Изначально любое ребро <tex>uv</tex> удовлетворяет свойству <tex>p_{\varphi}(uv) \geqslant -\varepsilon^{*}</tex>. Отмена цикла добавляет в остаточную сеть <tex>G_{f}</tex> только ребра положительной приведенной стоимости (см. [[#lemma4|предыдущую лемму№4]]) и удаляет из сети <tex>G</tex> как минимум одно ребро. Рассмотрим два случая:
:#Ни один из отмененных циклов не содержал ребер, обладающих неотрицательной приведенной стоимостью. Тогда каждая отмена цикла уменьшает размер допустимого графа <tex>H</tex> и после <tex>E</tex> отмен граф <tex>H</tex> пуст, что означает, что <tex>f'</tex> {{---}} оптимальный поток, то есть <tex>\varepsilon'^{*}=0</tex>.
:#Некоторые из отмененных циклов содержали ребра неотрицательной приведенной стоимости. Пусть впервые такое случилось на <tex>i</tex>-ой итерации, и, соответственно, <tex>C_{i}</tex> {{---}} первый из таких циклов. Для <tex>C_{i}</tex> имеем, что каждое его ребро обладает приведенной стоимостью как минимум <tex>-\varepsilon_{i}^{*}</tex> (при этом <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} \leqslant \varepsilon^{*}</tex> по [[#lemma4|предыдущей лемме№4]]), хотя бы одно из ребер <tex>C_{i}</tex> обладает неотрицательной приведенной стоимостью и количество ребер в <tex>C_{i}</tex> не превышает <tex>V</tex>. Тогда средний вес этого цикла <tex>\mu(C_{i}) = \mu_{i}^{*} \geqslant -\left(1-\dfrac{1}{V}\right)\varepsilon_{i}^{*} \geqslant - \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>, и <tex>\varepsilon'^{*} \leqslant \varepsilon_{i}^{*} = -\mu_{i}^{*} \leqslant \left(1-\dfrac{1}{V}\right)\varepsilon^{*}</tex>.}}
{{Определение
:Покажем теперь, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимальный.
:Обозначим за <tex>G_{>}</tex> подграф <tex>G</tex> такой, что <tex>G_{>}=(V, \{uv \in E \;|\; f'(uv) > f(uv) \})</tex>. Рассмотрим некоторое ребро <tex>uv</tex> в <tex>G_{>}</tex>. Поскольку <tex>f</tex> и <tex>f'</tex> являются циркуляциями, в <tex>G_{>}</tex> должен содержаться простой цикл <tex>C</tex>, проходящий через <tex>uv</tex>. Поскольку все ребра в <tex>C</tex> {{---}} остаточные, стоимость <tex>C</tex> не меньше <tex>p_{\varphi}(uv) - (\texttt{len}(C)-1)\varepsilon \geqslant 2V\varepsilon - (V-1)\varepsilon > V\varepsilon</tex>.
:Теперь рассмотрим цикл <tex>\overline{C}</tex>, который получен из <tex>C</tex> разворотом всех его ребер. Заметим, что <tex>\overline{C}</tex> является циклом в <tex>G_{<}=(V,\{uv \in E \;|\; f'(uv) < f(uv)\})</tex> и, соответственно, циклом в <tex>G_{f}</tex>. По свойству антисимметричности, стоимость <tex>\overline{C}</tex> меньше, чем <tex>-V\varepsilon</tex> и, таким образом, <tex>\mu(\overline{C}) < -\varepsilon</tex>. Откуда по [[#lemma3|лемме№3]] имеем, что <tex>f'</tex> не <tex>\varepsilon</tex>-оптимален.
}}
|proof=
:Оценка времени работы следует непосредственно из этого утверждения.
:Чтобы доказать его, рассмотрим некоторую группу итераций. Пусть <tex>f</tex> {{---}} поток до первой итерации, а <tex>f'</tex> {{---}} после последней итерации этой группы. Обозначим за <tex>\varepsilon'^{*}</tex> минимальное <tex>\varepsilon</tex> такое, что поток <tex>f'</tex> <tex>\varepsilon</tex>-оптимальный, а за <tex>\varphi'</tex> {{---}} функцию потенциалов такую, что <tex>f'</tex> удовлетворяет свойству <tex>\varepsilon'^{*}</tex>-оптимальности. Выбор <tex>k</tex> и [[#lemma5|предыдущая лемма№5]] дают нам следующее неравенство: <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|лемму№3]]), некоторое ребро <tex>uv</tex> цикла <tex>C</tex> должно иметь приведенную стоимость <tex>p_{\varphi'}(uv) \leqslant -\varepsilon^{*} \leqslant -2V\varepsilon'^{*}</tex>. Таким образом, поток на ребре <tex>uv</tex> не изменится при итерациях, происходящих после этой группы. Таким образом, по [[#theorem1|теореме]] каждая группа фиксирует поток на независимом ребре.}}
==Алгоритм поиска цикла минимального среднего веса==
