9
правок
Изменения
→Пример графа на котором алгоритм дает плохую асимптотику
В начале работы алгоритма путь увеличиться <tex>k^2</tex> раз по пути (<tex>s</tex>, <tex>S</tex>, <tex>T</tex>, <tex>t</tex>), длина которого равна трем. После этого остаточная сеть будет содержать обратные ребра из <tex>T</tex> в <tex>S</tex>, и алгоритм выберет еще <tex>k^2</tex> путей <tex>(s, u1, u2, T, S, v2, v1, t)</tex> длины <tex>7</tex>, затем путь <tex>(s, u1, u2, u3, u4, S, T, v4, v3, v2, v1, t)</tex> длины <tex>11</tex> и так далее...
Число вершин в нашей сети: <tex>n = 2\cdot k + 4\cdot p + 2</tex>. Число ребер: <tex> m = k^2 + 2\cdot p\cdot k + 2\cdot k + 4\cdot p</tex>. Нетрудно заметить, что число удлиняющих путей <tex> a = k^2\cdot (p+1)</tex>
Возьмем <tex>p</tex> равным <tex>k - 1</tex>. В этом случае <tex>n = 6 \cdot k - 2</tex> и <tex>a = k^3</tex>. Заде приводит более хитрые примеры с такой же асимптотикой, но они зависят от выбора пути
=== Пример ===
[[Файл:InGraph.png|600px|thumb|left| Изначальный граф, нулевой поток]]
[[Файл: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> шагов. Поток равен восьми]]
==Примечания==
