Изменения

[[Файл: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={s_1,\ldots,s_k}</tex> — множество вершин, в которые входят ребра из <tex>s</tex> с пропускной способностью k,

*<tex>T={t_1,\ldots,t_k}</tex> — множество вершин, из которых исходят ребра в <tex>t</tex> с пропускной способностью k,