align="justify">. Відшукання якого-небудь потоку;
. Відшукання повного потоку;
. Відшукання максимального потоку. br/>
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) = 6 - 3 = 3;
? * = 2.
Збільшення потоку, що проходить через цей шлях на 2, призводить до насичення дуг (1,4) і (5,7) (малюнок 6).
В
Малюнок 6 - Граф ТП з насиченими дугами (1,4) і (5,7)
Розглянемо наступний шлях, який не містить насичених дуг: (1, 3, 2, 8, 9).
? (1,3) = 8 - 4 = 4;
? (3, 2) = 6 - 4 = 2;
? ( 2,8) = 9 - 5 = 3;
? (8,9) = 7 - 6 = 1;
? * = 1.
Збільшення потоку, що проходить через цей шлях на 1, призводить до насичення дуги (8,9) (малюнок 7).
В
Малюнок 7 - Граф ТП з насиченою дугою (8,9)
Розглянемо шлях (1, 3, 2, 8, 7, 9) і за теоремою 2 збільшимо потік до максимального:
? (1,3) = 8 - 5 = 3;
? (3,2) = 6 - 5 = 1;
? (2,8) = 9 - 6 = 3;
? (4,9) = 2> 0;
? (7,9) = 6 - 5 = 1;
? * = 1.
Збільшення потоку сонаправленнимі дуг і зменшення потоку зустрічних дуг призводить до насичення дуг (3,2) і (...
