Изменения
→Пример графа на котором алгоритм дает плохую асимптотику
== Пример графа на котором алгоритм дает плохую асимптотику ==
[[Файл: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> с пропускной способностью k,
[[Файл: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> шагов. Поток равен восьми]]
==Примечания==
