Розглядається мережу з одним вузлом входу (джерело) і одним вузлом виходу (стік). Яка максимальна величина потоку (кількість машин, повідомлень, рідини і т.д.), який може увійти в мережеву систему і вийти з неї в заданий період часу? При цьому припускаємо, що потік, що випливає з вузла, дорівнює потоку, що впадає в вузол.
Під пропускною здатністю (потужністю) дуги будемо розуміти верхнє обмеження на потік в цій дузі. Потужність потоку може залежати від його напряму. Умовне зображення в мережі
Чи означає, що потужність потоку від вузла 1 до вузла 2 дорівнює 6, а потужність від 2 до 1 дорівнює 0.
Алгоритм визначення максимального потоку:
- Знайти будь-якої шлях від джерела до стоку, який утворений дугами, кожна з яких має в напрямку потоку ненулевую потужність. Якщо такого шляху немає, то оптимальне рішення знайдено.
- Знайти найменше значення потужності дуги Р на обраному шляху кроку 1. Збільшити потік через мережу на величину Р.
- На шляху з кроку 1 скоротити на Р потужності потоків на всіх дугах в напрямку потоку і збільшити на Р потужності потоків на всіх дугах в зворотному напрямку. Перейти до кроку 1.
Приклад. Система автодоріг «Північ-Південь», що проходять через Псковську область, може забезпечити пропускні спроможності, показані на наведеній нижче схемі (тис. Автомашин в годину).
Який максимальний потік через цю систему (тис. Автомашин в годину)? Скільки автомашин має проїхати по дорозі 5-6, щоб забезпечити максимальний потік?
Шукану величину максимального потоку покладемо рівною нулю.
Вибираємо шлях 1-3-6. Р = min (6,2) = 2. Тому потужності потоків на шляху 1-3-6 в напрямку потоку зменшуємо на величину Р = 2, а потужності потоків в зворотному напрямку на шляху 1-3-6 збільшимо на Р = 2. Загальний потік стане 0 + 2 = 2. отримаємо:
Вибираємо шлях 1-4-6. Р = min (3,3) = 3. Всі потоки на шляху 1-4-6 в напрямку загального потоку зменшуємо на 3, а в зворотному напрямку збільшуємо на 3. Загальний потік збільшуємо на 3. Разом, 2 + 3 = 5. отримаємо:
Вибираємо шлях 1-2-5-6. Р = min (2,4,6) = 2. Всі потоки на шляху 1-2-5-6 в напрямку загального потоку зменшуємо на 2, в зворотному збільшуємо на 2. Загальний потік збільшуємо теж на 2. Разом 5 + 2 = 7. отримаємо:
Вибираємо шлях 1-3-4-5-6. Р = min (4,3,1,4) = 1. Всі потоки на шляху 1-3-4-5-6 в напрямку загального потоку (4,3,1,4) зменшуємо на величину Р = 1, а всі потоки на цьому шляху в зворотному напрямку збільшуємо на Р = 1. Разом, загальний потік 7 + 1 = 8. отримаємо:
Вибираємо шлях 1-3-4-2-5-6. Р = min (3,2,1,2,3) = 1. У прямому напрямку зменшуємо на 1, в зворотному збільшуємо на 1. Загальний потік дорівнює 8 + 1 = 9. отримаємо:
Більше не існує шляхів з вузла 1 до вузла 6 з потужністю, що перевищує 0 на всьому шляху (Р = 0). Отже, 9 тис. - це максимальний потік через мережу.
Визначимо тепер величину і напрямок потоку на кожній дузі, щоб досягти максимального потоку в 9 тис. Автомобілів. Потік проходить по дузі з величиною, що дорівнює різниці між первісною і кінцевої потужностями потоку. Так, первісна потужність дуги 1-2 дорівнює 2, а кінцева - 0. Тоді в напрямку від вузла 1 до вузла 2 потік має потужність 2-0 = 2. Порівнюючи кінцеві і початкові потужності потоку для всіх дуг мережі, ми отримуємо кінцеву модель потоків.
Чому дорівнює максимальний потік автомашин для системи автодоріг? Розглядається можливість введення секції 3-4 з пропускною спроможністю 3 тис. Автомашин на годину. На скільки збільшиться величина максимального потоку автомашин?
Стіл Р.Р. Безлічі. Логіка. Аксіоматичні теорії. - М. Просвітництво, 1968.