Изменения

== Пример графа на котором алгоритм дает плохую асимптотику ==

Заметим также, что сущетсвует ''сеть грибок''<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>) на подмножества:

[[Файл: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> шагов. Поток равен восьми]]

==Примечания==