Изменения
Нет описания правки
== Пример графа на котором алгоритм дает плохую асимптотику ==
[[Файл:MaxFlowWorstCase.png|365px|thumb|right| "грибок" <br/>. Схема построения "сложного" для алгоритма Эдмондса-Карпа графа]]Заметим также, что сущетсвует ''сеть "грибок"''<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|600px|thumb|left| Изначальный граф, нулевой поток]]
