Изменения

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

Рассмотрим этот случай более подробно. Норман Заде(англ. 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={s1,\ldots,sk}</tex>, <tex>T={t1,\ldots,tk}</tex>, <tex>U={u1,\ldots,u2p}</tex> и <tex>V={v1,\ldots,v2p}</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>.