Изменения

Алгоритм Эдмондса-Карпа является реализацией метода [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Форда-Фалкерсона]], в которой в качестве дополняющего пути выбирается [[Обход в ширину |кратчайший по ребрам рёбрам путь]] в остаточной сети (длины всех ребер рёбер равны <tex>1</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) \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>\dfrac{(|V| -2)}{2} = \dfrac{|V|}{2} - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра рёбра в остаточной сети, то общее количество критических ребер рёбер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</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>. Рассмотрим этот случай более подробно. Норман Заде (англ. ''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={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> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>.

[[Файл:SecondStage.png|600px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Ребра Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]][[Файл:ThirdStageEdmunds karp.png|600px|thumb|left| Алгоритм нашел путь через ребра рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]