Алгоритм Эдмондса-Карпа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м (rollbackEdits.php mass rollback)
 
(не показана 31 промежуточная версия 12 участников)
Строка 1: Строка 1:
 
== Алгоритм ==
 
== Алгоритм ==
  
Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона, в которой в качестве дополняющего пути выбирается кратчайший по ребрам путь в остаточной сети (длины всех ребер равны <tex>1</tex>).
+
Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]], в которой в качестве дополняющего пути выбирается [[Обход в ширину |кратчайший по рёбрам путь]] в остаточной сети (длины всех рёбер равны <tex>1</tex>).
  
 
=== Описание ===
 
=== Описание ===
Строка 18: Строка 18:
 
== Псевдокод ==
 
== Псевдокод ==
  
  '''Edmonds_Karp''' (G, s, t)
+
  '''function''' EdmondsKarp(G, s, t):
 
     '''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
 
     '''for''' (для) каждого ребра <tex>(u,v) \in E[G]</tex>
 
         <tex>f[u,v] \leftarrow 0</tex>
 
         <tex>f[u,v] \leftarrow 0</tex>
Строка 30: Строка 30:
 
== Корректность алгоритма Эдмондса-Карпа ==
 
== Корректность алгоритма Эдмондса-Карпа ==
  
Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]]. На каждой итерации цикла <tex>\mathrm {while}</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует никакого вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.
+
На каждой итерации цикла <tex>\mathrm {while}</tex> поток в графе <tex>G</tex> увеличивается вдоль одного из кратчайших путей в <tex>G_f</tex> из истока <tex>s</tex> в сток <tex>t</tex>. Этот процесс повторяется до тех пор пока существует кратчайший <tex>s \leadsto t</tex> путь в <tex>G_f</tex>. Если в <tex>G_f</tex> не существует кратчайшего пути из <tex>s</tex> в <tex>t</tex>, значит, не существует вообще никакого <tex>s \leadsto t</tex> пути в <tex>G_f</tex> следовательно по [[Теорема Форда-Фалкерсона|теореме Форда-Фалкерсона]] найденный поток <tex>f</tex> максимальный.
  
 
== Оценка быстродействия ==
 
== Оценка быстродействия ==
Строка 37: Строка 37:
 
|id=lemma1
 
|id=lemma1
 
|statement=
 
|statement=
Если в сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> увеличение потока производится вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>, то для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.
+
Если в сети <tex>G(V,E)</tex> с истоком <tex>s</tex> и стоком <tex>t</tex> увеличение потока производится вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>, то для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.
 
|proof=
 
|proof=
 
Предположим противное, пусть существует вершина <tex>v \in V \backslash\{s,t\}</tex>, что после какого-то увеличения потока длина кратчайшего пути из <tex>s</tex> в <tex>v</tex> уменьшилась. Обозначим потоки до и после увеличения соответственно за <tex>f</tex> и <tex>f'</tex>. Пусть <tex>v</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v)</tex> от <tex>s</tex> до которой минимально и уменьшилось с увеличением потока. Имеем <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Рассмотрим путь <tex>p = s \leadsto u \rightarrow v</tex>, являющийся кратчайшим от <tex>s</tex> к <tex>v</tex> в <tex>G'_f</tex>. Тогда верно, что <tex>\delta'_f(s, u) = \delta'_f(s,v) - 1</tex>.
 
Предположим противное, пусть существует вершина <tex>v \in V \backslash\{s,t\}</tex>, что после какого-то увеличения потока длина кратчайшего пути из <tex>s</tex> в <tex>v</tex> уменьшилась. Обозначим потоки до и после увеличения соответственно за <tex>f</tex> и <tex>f'</tex>. Пусть <tex>v</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v)</tex> от <tex>s</tex> до которой минимально и уменьшилось с увеличением потока. Имеем <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Рассмотрим путь <tex>p = s \leadsto u \rightarrow v</tex>, являющийся кратчайшим от <tex>s</tex> к <tex>v</tex> в <tex>G'_f</tex>. Тогда верно, что <tex>\delta'_f(s, u) = \delta'_f(s,v) - 1</tex>.
Строка 54: Строка 54:
 
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла <tex>\mathrm {while}</tex>  составляет <tex>O(V E)</tex>.
 
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла <tex>\mathrm {while}</tex>  составляет <tex>O(V E)</tex>.
 
|proof=
 
|proof=
Рассмотрим множество ребер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные ребра критическими. Покажем, что каждое из <tex>|E|</tex> ребер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические ребра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.
+
Рассмотрим множество рёбер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные рёбра критическими. Покажем, что каждое из <tex>|E|</tex> рёбер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</tex> все критические рёбра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути {{---}} критическое.
  
Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \le \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \geqslant \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.
+
Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производится вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшено по обратному ребру <tex>(v, u)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \leqslant \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \geqslant \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.
  
Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>(|V| -2)/2 = |V|/2 - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.  
+
Итак в промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>\dfrac{(|V| -2)}{2} = \dfrac{|V|}{2} - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать рёбра в остаточной сети, то общее количество критических рёбер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.  
  
 
Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла <tex>\mathrm {while}</tex>  рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла <tex>\mathrm {while}</tex>  также составляет <tex>O(V E)</tex>.
 
Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла <tex>\mathrm {while}</tex>  рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла <tex>\mathrm {while}</tex>  также составляет <tex>O(V E)</tex>.
 
}}
 
}}
  
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует сеть  "грибок"<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com  ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.
+
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <tex>\mathrm {while}</tex>  можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>.  
 +
 
 +
== Пример графа, на котором алгоритм дает плохую асимптотику ==
 +
[[Файл:MaxFlowWorstCase.png|365px|thumb|right|«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]]
 +
 
 +
Заметим также, что существует ''сеть  грибок''<ref>[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Cтатья на TopCoder.com  ]</ref> на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>. Рассмотрим этот случай более подробно. Норман Заде (англ. ''Norman Zadeh'') описал примеры, которые позволяют добиться асимптотики <tex>\Omega(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>\Omega(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.
 +
Разделим все вершины (за исключением <tex>s</tex> и <tex>t</tex>) на подмножества:
 +
*<tex>S={s_1,\ldots,s_k}</tex> — множество вершин, в которые входят рёбра из <tex>s</tex> с пропускной способностью <tex>k</tex>,
 +
*<tex>T={t_1,\ldots,t_k}</tex> — множество вершин, из которых исходят рёбра в <tex>t</tex> с пропускной способностью <tex>k</tex>,
 +
*<tex>U={u_1,\ldots,u_{2p}}</tex> — множество вершин, достижимых из <tex>s</tex> по рёбрам с бесконечной пропускной способностью (не используя иные рёбра),
 +
*<tex>V={v_1,\ldots,v_{2p}}</tex> — множество вершин, из которых можно достигнуть <tex>t</tex> по рёбрам с бесконечной пропускной способностью (не используя иные рёбра).
 +
 
 +
<tex>S</tex> и <tex>T</tex> содержат <tex>k</tex> вершин, <tex>U</tex> и <tex>V</tex> содержат <tex>2p</tex> вершин. Где <tex>k</tex> и <tex>p</tex> фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества <tex>S</tex> и <tex>T</tex>), имеет единичную пропускную способность; пунктирные рёбра имеют бесконечную пропускную способность; остальные рёбра(в форме дуги) имеют пропускную способность <tex>k</tex>.
 +
В начале работы алгоритма путь увеличиться <tex>k^2</tex> раз по пути (<tex>s</tex>, <tex>S</tex>, <tex>T</tex>, <tex>t</tex>), длина которого равна трем. После этого остаточная сеть будет содержать обратные рёбра из <tex>T</tex> в <tex>S</tex>, и алгоритм выберет еще <tex>k^2</tex> путей <tex>(s, u_1, u_2, T, S, v_2, v_1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t)</tex> длины <tex>11</tex> и так далее.
 +
:Число вершин в сети: <tex>n = 2\cdot k + 4\cdot p + 2</tex>.
 +
:Число рёбер: <tex> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>.
 +
 
 +
Нетрудно заметить, что число удлиняющих путей <tex> a = k^2\cdot (p+1)</tex>.
 +
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.
 +
 
 +
[[Файл:InGraph.png|300px|thumb|left| Изначальный граф, нулевой поток]]
 +
[[Файл:SecondStage.png|300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]]
 +
[[Файл:ThirdStageEdmunds karp.png|300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
== См. также ==
 +
*[[Определение сети, потока]]
 +
*[[Обход в ширину]]
 +
*[[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|Алгоритм Форда-Фалкерсона]]
  
 
==Примечания==
 
==Примечания==
Строка 71: Строка 127:
 
== Источники информации ==
 
== Источники информации ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
*[https://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа Википедия: Алоритм Эдмондса-Карпа]
+
*[https://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа Википедия: Алгоритм Эдмондса-Карпа]
* [https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm Википедия: Алоритм Эдмондса-Карпа (англ.)]
+
* [https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm Википедия: Алгоритм Эдмондса-Карпа (англ.)]
 +
*[https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-augmenting-path-algorithms-comparison/#! Статья на TopCoder.com]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о максимальном потоке]]
 
[[Категория: Задача о максимальном потоке]]

Текущая версия на 19:25, 4 сентября 2022

Алгоритм

Алгоритм Эдмондса-Карпа является реализацией метода Форда-Фалкерсона, в которой в качестве дополняющего пути выбирается кратчайший по рёбрам путь в остаточной сети (длины всех рёбер равны [math]1[/math]).

Описание

  1. Положим все потоки равными нулю. Остаточная сеть изначально совпадает с исходной сетью.
  2. В остаточной сети находим кратчайший путь из источника в сток. Если такого пути нет, останавливаемся.
  3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:
    1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью [math]\mathrm{c_{min}}[/math].
    2. Для каждого ребра на найденном пути увеличиваем поток на [math]\mathrm{c_{min}}[/math], а в противоположном ему — уменьшаем на [math]\mathrm{c_{min}}[/math].
    3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
  4. Возвращаемся на шаг 2.

Сложность

Сложность алгоритма Эдмондса-Карпа равна [math]O(VE^2)[/math].

Псевдокод

function EdmondsKarp(G, s, t):
    for (для) каждого ребра [math](u,v) \in E[G][/math]
        [math]f[u,v] \leftarrow 0[/math]
        [math]f[v,u] \leftarrow 0[/math]
    while существует кратчайший путь [math]p[/math] из [math]s[/math] в [math]t[/math] в остаточной сети [math]G_f[/math]
        [math]c_f(p) \leftarrow min\{c_f(u,v) : (u,v) \in p\}[/math]
        for [math](u,v) \in p[/math]
            [math]f[u,v] \leftarrow f[u,v] + c_f(p)[/math]
            [math]f[v,u] \leftarrow -f[u,v][/math]

Корректность алгоритма Эдмондса-Карпа

На каждой итерации цикла [math]\mathrm {while}[/math] поток в графе [math]G[/math] увеличивается вдоль одного из кратчайших путей в [math]G_f[/math] из истока [math]s[/math] в сток [math]t[/math]. Этот процесс повторяется до тех пор пока существует кратчайший [math]s \leadsto t[/math] путь в [math]G_f[/math]. Если в [math]G_f[/math] не существует кратчайшего пути из [math]s[/math] в [math]t[/math], значит, не существует вообще никакого [math]s \leadsto t[/math] пути в [math]G_f[/math] следовательно по теореме Форда-Фалкерсона найденный поток [math]f[/math] максимальный.

Оценка быстродействия

Лемма:
Если в сети [math]G(V,E)[/math] с истоком [math]s[/math] и стоком [math]t[/math] увеличение потока производится вдоль кратчайших [math]s \leadsto t[/math] путей в [math]G_f[/math], то для всех вершин [math]v \in V\backslash\{s,t\}[/math] длина кратчайшего пути [math]\delta_f(s, v)[/math] в остаточной сети [math]G_f[/math] не убывает после каждого увеличения потока.
Доказательство:
[math]\triangleright[/math]

Предположим противное, пусть существует вершина [math]v \in V \backslash\{s,t\}[/math], что после какого-то увеличения потока длина кратчайшего пути из [math]s[/math] в [math]v[/math] уменьшилась. Обозначим потоки до и после увеличения соответственно за [math]f[/math] и [math]f'[/math]. Пусть [math]v[/math] — вершина, расстояние [math]\delta'_f(s,v)[/math] от [math]s[/math] до которой минимально и уменьшилось с увеличением потока. Имеем [math]\delta'_f(s,v) \lt \delta_f(s,v)[/math]. Рассмотрим путь [math]p = s \leadsto u \rightarrow v[/math], являющийся кратчайшим от [math]s[/math] к [math]v[/math] в [math]G'_f[/math]. Тогда верно, что [math]\delta'_f(s, u) = \delta'_f(s,v) - 1[/math].

По выбору [math]v[/math] и из предыдущего утверждения получаем, что [math]\delta'_f (s, u) \geqslant\delta_f(s,u)[/math].

Предположим [math](u, v) \in E_f[/math], тогда [math]\delta_f(s,v) \leqslant \delta_f(s, u) + 1 \leqslant \delta'_f(s,u) + 1 = \delta'_f(s, v)[/math]. Это противоречит [math]\delta'_f(s,v) \lt \delta_f(s,v)[/math].

Пусть [math](u,v) \notin E_f[/math], но известно, что [math](u,v) \in E_f'[/math]. Появление ребра [math](u,v)[/math] после увеличения потока означает увеличение потока по обратному ребру [math](v, u)[/math]. Увеличение потока производится вдоль кратчайшего пути, поэтому кратчайший путь из [math]s[/math] в [math]u[/math] вдоль которого происходило увеличения выглядит как [math]s \leadsto v \rightarrow u[/math], из чего получаем [math]\delta_f(s, v) = \delta_f(s, u) - 1 \leqslant \delta'_f(s, u) - 1 = \delta'(s, v) - 2[/math]. Данное утверждение противоречит [math]\delta'_f(s,v) \lt \delta_f(s,v)[/math]. Итак мы пришли к противоречию с существованием вершины [math]v[/math], кратчайшее расстояние до которой уменьшилось с увеличением потока.
[math]\triangleleft[/math]


Опираясь на предшествующую лемму, докажем следующую теорему, которая ограничивает сверху число итераций цикла [math]\mathrm {while}[/math] в алгоритме Эдмондса-Карпа.

Теорема:
Пусть для некоторой сети [math]G(V,E)[/math] с источником [math]s[/math] и стоком [math]t[/math] выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла [math]\mathrm {while}[/math] составляет [math]O(V E)[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим множество рёбер [math](u,v)[/math] остаточной сети [math]G_f[/math], принадлежащих увеличивающему пути [math]p[/math], таких что [math]c_f(p) = c_f(u,v)[/math]. Назовем данные рёбра критическими. Покажем, что каждое из [math]|E|[/math] рёбер может становиться критическим не более, чем [math]|V| - 1[/math] раз. Заметим, что после увеличения потока вдоль пути [math]p[/math] все критические рёбра исчезают из остаточной сети, кроме того по определению остаточной пропускной способности пути хотя бы одно ребро увеличивающего пути — критическое.

Рассмотрим две вершины [math]u[/math] и [math]v[/math] принадлежащие [math]V[/math], соединенные некоторым ребром из [math]E[/math]. Увеличение производится вдоль кратчайших путей, поэтому если ребро [math](u,v)[/math] становиться критическим в первый раз, верно, что [math]\delta_f(s,v) = \delta_f(s,u) + 1[/math]. После увеличения потока ребро [math](u, v)[/math] исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшено по обратному ребру [math](v, u)[/math]. Это может произойти только в том случае, если ребро [math](v, u)[/math] встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети [math]G[/math] составлял [math]f'[/math], то поскольку увеличение производиться вдоль кратчайших путей, верно: [math]\delta'_f(s,u) = \delta'_f(s, v) + 1[/math]. Согласно лемме [math]\delta_f(s,v) \leqslant \delta'_f(s,v)[/math], откуда [math]\delta'_f(s,u) = \delta'(s,v) + 1 \geqslant \delta_f(s,v) + 1 = \delta_f(s,u) + 2[/math].

Итак в промежуток времени между тем, когда ребро [math](u,v)[/math] становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от [math]s[/math] до [math]u[/math] увеличивается минимум на [math]2[/math]. Расстояние [math]\delta(s,u)[/math] в начальный момент времени больше либо равно [math]0[/math]. Среди промежуточных вершин на кратчайшем пути [math]s \leadsto u[/math] не могут находиться [math]s[/math], [math]u[/math] или [math]t[/math]. Следовательно к тому моменту, когда вершина [math]u[/math] станет недостижимой из источника расстояние до нее не превысит [math]|V| - 2[/math]. Получаем, что ребро [math](u, v)[/math] могло стать критическим не более [math]\dfrac{(|V| -2)}{2} = \dfrac{|V|}{2} - 1[/math] раз. Поскольку в графе не более [math]O(E)[/math] пар вершин, между которыми могут существовать рёбра в остаточной сети, то общее количество критических рёбер в ходе выполнения алгоритма Эдмондса-Карпа равно [math]O(V E)[/math].

Так как каждый увеличивающий путь содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет [math]O(V E)[/math]. На каждой итерации цикла [math]\mathrm {while}[/math] рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла [math]\mathrm {while}[/math] также составляет [math]O(V E)[/math].
[math]\triangleleft[/math]

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла [math]\mathrm {while}[/math] можно выполнить за время [math]O(E)[/math]. Инициализация в процедуре Edmonds Karp производится за [math]O(E)[/math], следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет [math]O(V E^2)[/math].

Пример графа, на котором алгоритм дает плохую асимптотику

«Грибок». Схема построения "сложного" для алгоритма Эдмондса-Карпа графа

Заметим также, что существует сеть грибок[1] на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет [math]\Omega(V E^2)[/math]. Рассмотрим этот случай более подробно. Норман Заде (англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики [math]\Omega(V^3)[/math][2]. В нашем примере алгоритм выполнит [math]\Omega(V^3)[/math] улучшений пути вне зависимости от выбора этого пути. Разделим все вершины (за исключением [math]s[/math] и [math]t[/math]) на подмножества:

  • [math]S={s_1,\ldots,s_k}[/math] — множество вершин, в которые входят рёбра из [math]s[/math] с пропускной способностью [math]k[/math],
  • [math]T={t_1,\ldots,t_k}[/math] — множество вершин, из которых исходят рёбра в [math]t[/math] с пропускной способностью [math]k[/math],
  • [math]U={u_1,\ldots,u_{2p}}[/math] — множество вершин, достижимых из [math]s[/math] по рёбрам с бесконечной пропускной способностью (не используя иные рёбра),
  • [math]V={v_1,\ldots,v_{2p}}[/math] — множество вершин, из которых можно достигнуть [math]t[/math] по рёбрам с бесконечной пропускной способностью (не используя иные рёбра).

[math]S[/math] и [math]T[/math] содержат [math]k[/math] вершин, [math]U[/math] и [math]V[/math] содержат [math]2p[/math] вершин. Где [math]k[/math] и [math]p[/math] фиксированные целые числа. Каждое ребро, выделенное жирным(см. рисунок, соединяют множества [math]S[/math] и [math]T[/math]), имеет единичную пропускную способность; пунктирные рёбра имеют бесконечную пропускную способность; остальные рёбра(в форме дуги) имеют пропускную способность [math]k[/math]. В начале работы алгоритма путь увеличиться [math]k^2[/math] раз по пути ([math]s[/math], [math]S[/math], [math]T[/math], [math]t[/math]), длина которого равна трем. После этого остаточная сеть будет содержать обратные рёбра из [math]T[/math] в [math]S[/math], и алгоритм выберет еще [math]k^2[/math] путей [math](s, u_1, u_2, T, S, v_2, v_1, t)[/math] длины [math]7[/math], затем путь [math](s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t)[/math] длины [math]11[/math] и так далее.

Число вершин в сети: [math]n = 2\cdot k + 4\cdot p + 2[/math].
Число рёбер: [math] m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p[/math].

Нетрудно заметить, что число удлиняющих путей [math] a = k^2\cdot (p+1)[/math]. Возьмем [math]p[/math] равным [math]k - 1[/math]. В этом случае [math]n = 6 \cdot k - 2[/math] и [math]a = k^3[/math]. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.

Изначальный граф, нулевой поток
Граф после [math]k^2[/math] поисков пути(в нашем случае [math]k^2 = 4[/math]).
Рёбра из между множествами [math]S[/math] и [math]T[/math] полностью насыщены. Поток равен четырем
Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще [math]k^2 = 4[/math] шагов. Поток равен восьми
















См. также

Примечания

  1. Cтатья на TopCoder.com
  2. Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.

Источники информации