693
правки
Изменения
→Пример графа на котором алгоритм дает плохую асимптотику
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути.
[[Файл:InGraph.png|600px300px|thumb|left| Изначальный граф, нулевой поток]][[Файл:SecondStage.png|600px300px|center|thumb| Граф после <tex>k^2</tex> поисков пути(в нашем случае <tex>k^2 = 4</tex>).<br/>Рёбра из между множествами <tex>S</tex> и <tex>T</tex> полностью насыщены. Поток равен четырем]][[Файл:ThirdStageEdmunds karp.png|600px300px|thumb|left| Алгоритм нашел путь через рёбра бесконечной вместимости, совершив еще <tex>k^2 = 4</tex> шагов. Поток равен восьми]]
==Примечания==
