о, що максимальний потік обов'язково є повним (тому що в іншому випадку в D існує деяка проста ланцюг з V1 у Vn, що не містить насичених дуг, а отже, можна збільшити на одиницю потоки по всіх дуг з і тим самим збільшити на одиницю, що суперечить умові максимальності потоку). Зворотний ж, взагалі кажучи, невірно. Існують повні потоки, які не є максимальними. Тим на менш повний потік можна розглядати як деяке наближення до максимального потоку.
Орграф збільшень.
Введемо для заданої транспортної мережі D і допустимого потоку в цій мережі орграф збільшень, що має ті ж вершини, що і мережа D. Кожній дузі транспортної мережі D в орграфе збільшень відповідає дві дуги: і - дуга, протилежна за напрямку дузі. Припишемо дуг орграфа збільшень довжину:
В В
тобто орграф є навантаженим. При цьому очевидно, що довжина будь-якого шляху з о в орграфе дорівнює або 0, або нескінченності.
Алгоритм побудови максимального потоку в транспортній мережі.
Важливим наслідком теореми Форда-Фалкерсона є Алгоритм побудови максимального потоку в транспортній мережі.
Алгоритм:
Крок 1. Вважаємо i = 0. Нехай - будь допустимий потік в транспортної мережі D (наприклад, повний, можна починати з нульового потоку:).
Крок 2. По мережі D і потоку будуємо орграф збільшень. p> Крок 3. Знаходимо просту ланцюгВ , Що є мінімальним шляхом з вВ в навантаженому орграфе. Якщо довжина цього ланцюга дорівнює нескінченності, то потік максимальний, і робота алгоритму закінчена. У Інакше збільшуємо потік ввдоль ланцюга на максимально допустиму величину, таку, що при цьому зберігається умова 1 допустимого потоку (для будь дуги величина, звана потоком по дузі х, задовольняє умові). У силу, використовуючи і, отримуємо, що вказана величина існує. В результаті змінюється потік в транспортній мережі D, тобто від потоку ми перейшли до потоку, і при цьому. Прісваєваєм і переходимо до кроку 2. p>
В
В
ПРАКТИЧНА ЧАСТИНА:
В
Задача про максимальний потік.
Для заданої транспортної мережі визначити величину максимального потоку вантажів, які можна доставити в протягом заданого часу з міста S в місто t. Пропускні здатності всіх ділянок доріг вважаються відомими.
Етап 1.
Почнемо з процедури розстановки позначок. Позначка джерела S Далі розглянемо ті вершини, які з'єднані з джерелом дугою. Це V, V, V. Припустимо по всій мережі первісний нульової потік Припишемо біля кожної дуги після значення пропускної здатності значення початкового потоку.
Переглянемо вершину S, для цього пометим вершіниV, V, V.
Переглянемо вершину V, ставимо мітки. Перегляне...
