Алгоритм Эдмондса-Карпа

2015-02-06T06:19:20Z

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

== Алгоритм ==

Для заданной сети <tex>G(V, E, c)</tex> алгоритм Эдмондса-Карпа находит поток максимальной величины из заданного истока <tex>s</tex> в заданный сток <tex>t</tex> за <tex>O(V E^2)</tex>.

== Псевдокод ==

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

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

Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]]. На каждой итерации цикла '''while''' поток в графе <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> максимальный.

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

{{Лемма
|id=lemma1
|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> не убывает после каждого увеличения потока.
|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</tex> и из предыдущего утверждения получаем, что <tex>\delta'_f (s, u) \ge \delta_f(s,u)</tex>.

Предположим <tex>(u, v) \in E_f</tex>, тогда <tex>\delta_f(s,v) \le \delta_f(s, u) + 1 \le \delta'_f(s,u) + 1 = \delta'_f(s, v)</tex>. Это противоречит <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>.

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

Опираясь на предшествующую лемму, докажем следующую теорему, которая ограничивает сверху число итераций цикла '''while''' в алгоритме Эдмондса-Карпа.

{{Теорема
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, тогда общее число итераций цикла '''while''' составляет <tex>O(V E)</tex>.
|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</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 \ge \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>O(V E)</tex>. На каждой итерации цикла '''while''' рассматривается ровно один увеличивающий путь, а поскольку в случае отсутствия такого пути выполнение цикла прерывается, то число итераций цикла '''while''' также составляет <tex>O(V E)</tex>.
}}

Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла '''while''' можно выполнить за время <tex>O(E)</tex>. Инициализация в процедуре '''Edmonds_Karp''' производится за <tex>O(E)</tex>, следовательно время работы алгоритма алгоритма Эдмондса-Карпа составляет <tex>O(V E^2)</tex>. Заметим также, что сущетсвует сеть [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited "грибок"] на которой нижняя граница времени работы алгоритмы Эдмондса-Карпа также составляет <tex>\Omega(V E^2)</tex>.

== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]

Викиконспекты - Вклад участника [ru]

Алгоритм Эдмондса-Карпа