justify"> j Х N = c (U + A ) = ГҐ c (u), u ГЋ U + A, де
+ A - безліч дуг, що входять в розріз;
c (U + A ) - пропускна здатність розрізу .
Теорема 4 (теорема Форда-Фалкерсона)
Для заданої транспортної мережі максимальне значення потоку одно мінімальної пропускної здатності розрізу.
max j Х N = min c (U + A ) .
Алгоритм Форда-Фалкерсона увазі наступні етапи:
. Відшукання якогось потоку;
. Відшукання повного потоку;
. Відшукання максимального потоку.
3.3 Рішення завдання за варіантом
На малюнку 4 наведено граф, у вигляді якого представлений ТП з відповідними ТО:
В
Рисунок 4 - Граф ТП
Шлях (1, 4, 6, 7, 9) не містить насичених дуг.
Знаходимо різницю в кожній дузі між максимальною її пропускною здатністю і дійсною:
? (1, 4) = 6 - 2 = 4;
? ( 4,6) = 6 - 4 = 2;
? ( 6,7) = 5 - 3 = 2;
? ( 7,9) = 6 - 1 = 5.
? * = 2.
Збільшення потоку, що проходить через цей шлях на 2, призводить до насичення дуг (4,6) і (6,7) (малюнок 5).
В
Рисунок 5 - Граф ТП з насиченими дугами (4,6) і (6,7)
Розглянемо наступний шлях, який не містить насичених дуг:
(1, 4, 5, 7, 9).
? (1, 4) = 6 - 4 = 2;
? ( 4,5) = 7 - 2 = 5;
? ( 5,7) = 5 - 3 = 2;
? (7,9...
