37
правок
Изменения
Нет описания правки
=== Пример несходящегося алгоритма ===
[[Файл:F-f.5.png|thumb|right|рис. 1]]
Рассмотрим приведённую справа сеть, с источником <math>\ s</math>, стоком <math>\ t</math>, пропускными способностями рёбер <math>\ e_1</math>, <math>\ e_2</math> и <math>\ e_3</math> соответственно <math>\ 1</math>, <math>r=(\sqrt{5}-1)/2</math> и <math>\ 1</math> и пропускной способностью всех остальных рёбер, равной целому числу <math>M \ge 2</math>. Константа <math>\ r</math> выбрана так, что <math>\ r^2 = 1 - r</math>. Мы используем пути из остаточного графа, приведённые в таблице, причём <math>\ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}</math>, <math>\ p_2 = \{ s, v_2, v_3, v_4, t \}</math> и <math>\ p_3 = \{ s, v_1, v_2, v_3, t \}</math>.
=== Пример медленной работы алгоритма Форда-Фалкерсона с использованием поиска в глубину по сравнению с реализацией, использующей поиск в ширину ===
При использовании поиска в ширину алгоритму потребуется всего лишь 2 шага.
Дана сеть (рис. 12).[[Файл:F-f.1.png|thumb|center|рис. 12]]Благодаря двум итерациям (рис. 2 3 и рис. 34)[[Файл:F-f.2.png|thumb|center|рис. 23]][[Файл:F-f.3.png|thumb|center|рис. 34]]
рёбра <tex>AB, AC, BD, CD</tex> насытились лишь на 1.
Конечная сеть будет получена ещё через 1998 итераций (рис. 45).[[Файл:F-f.4.png|thumb|center|рис. 45]]
== См. также ==
