9
правок
Изменения
Нет описания правки
Если увеличивающий путь находить поиском в ширину, то каждую итерацию цикла <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>.
[[Файл:MaxFlowWorstCase.png|365px|thumb|right| "грибок"]]
Рассмотрим этот случай более подробно. Норман Заде(англ. Norman Zadeh) описал примеры, которые позволяют добиться асимптотики <tex>O(V^3)</tex><ref>Norman Zadeh. Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal Flows.</ref>. В нашем примере алгоритм выполнит <tex>O(V^3)</tex> улучшений пути вне зависимости от выбора этого пути.
Разделим все вершины(за исключением <tex>s</tex> и <tex>t</tex> на подмножества: <tex>S</tex>={s1,…,sk}, <tex>T</tex>={t1,…,tk}, <tex>U</tex>={u1,…,u2p} и <tex>V</tex>={v1,…,v2p}. <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</tex>, <tex>u1</tex>, <tex>u2</tex>, <tex>T</tex>, <tex>S</tex>, <tex>v2</tex>, <tex>v1</tex>, <tex>t</tex>) длины 7, затем путь <tex>(s, u1, u2, u3, u4, S, T, v4, v3, v2, v1, t)</tex> длины 11 и так далее...
Кол-во вершин в нашей сети: <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>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути
==Примечания==
*[https://ru.wikipedia.org/wiki/Алгоритм_Эдмондса_—_Карпа Википедия: Алоритм Эдмондса-Карпа]
* [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]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
