Матеріал з ВікіОсвіта
12. Мережі, потоки в мережах. Теорема Форда - Фалкерсона
Потоком в мережі між вершиною t (джерелом) і s (стоком) називається набір чисел сij, (т. Е. Кількість умовного "вантажу", що перевозиться з вершини з номером i в вершину з номером j), які відповідають чотирьом умовам:
1) числа сij Ј 0, причому якщо сij> 0, то сji = 0 (немає зустрічних перевезень);
2) числа cij Ј qij (відповідних пропускних спроможностей ребер);
3) якщо вершина з номером i - проміжна (не збігається з джерелом і стоком), то
т. е. кількість "вантажу", що вивозиться з вершини i, дорівнює кількості "вантажу", що ввозиться в цю вершину;
4) кількість "вантажу", що вивозиться з джерела t, має дорівнювати кількості вантажу, що ввозиться в стік s:
Число А називається величиною даного потоку або просто потоком між t і s.
Для подальшого нам потрібно наступне визначення:
Нехай є деяка перетин між вершинами t і s. Тоді величиною перетину називається сума пропускних спроможностей ребер, що входять в це перетин. Перетин називається мінімальним (максимальним), якщо його величина мінімальна (максимальна).
Теорема Форда - Фалкерсона (1955). Максимальний потік між вершинами t і s дорівнює величині мінімального перетину між цими вершинами.
Доказ цієї теореми є конструктивним (т. Е. Показує, як знайти потрібний максимальний потік), тому наводиться нижче.
Більш точно, безліч помічених вершин Y утворюється в такий спосіб:
джерело t належить Y і його позначка (0, Ґ); друге число, умовно кажучи, дорівнює нескінченності - що для дискретної математики означає, що це настільки велике число, як нам знадобиться;
якщо вершина i належить Y і cij
якщо вершина до належить Y і сjk> 0 (зворотна дуга), то вершина з номером j також повинна належати Y і її позначка дорівнює (- до, dj), де знак мінус означає, що вершина j пов'язана з уже поміченої вершиною до зворотного дугою , dj = min, причому очевидно, що dj також строго більше нуля. Таким чином, побудова безлічі Y є індуктивним, т. Е. Нова вершина додається в Y, якщо вона пов'язана з деякою вершиною вже входить в Y або прямий ненасиченої дугою, або зворотного дугою.
Після того як побудова безлічі Y закінчено (до нього не можна додати нових вершин), можливі 2 випадки.
1. Сток (т. Е. Вершина з номером s) не входить в безліч вершин Y. Тоді позначимо безліч вершин, що не входять в Y через Z. Наш граф за умовою є зв'язковим, тому з Y, в Z йдуть деякі ребра. За правилами побудови Y всі ці ребра є прямими насиченими дугами (рис. 7).
Ребра, що йдуть з безлічі Y в Z, утворюють перетин між вершинами t і s. Видно також, що сума пропускних спроможностей ребер цього перетину (а всі ці ребра є прямими, насиченими) дорівнює потоку з t в s. Значить, цей потік є максимальним (так як він дорівнює величині деякого перетину), а дане перетин є мінімальним.
2. Вершина s також входить в Y, і нехай друге число її позначки d s> 0. Тоді, очевидно, що між вершинами t і s існує ланцюг (що складається з спрямованих ребер - прямих і зворотних дуг), що з'єднує ці вершини
Схематично це представлено на рис. 8. t ® · ® · ¬ · ¬ · ® · ® · ¬ · ¬ · ® · ®s
Зауважимо, що дуга, яка виходить з джерела, і дуга, що входить в стік, повинні бути обов'язково прямими. Додамо ds до cij для прямих дуг цьому ланцюзі (з побудови видно, що отримане число буде менше або дорівнює qij) і віднімемо це ds з cij для зворотних дуг (може вийти негативне число, але воно обов'язково буде за абсолютною величиною менше qij, так як з побудови ds Ј cij + qij. а це означає, що зворотна дуга змінює напрямок, стає прямою дугою і його "навантаження" буде дорівнює модулю числа Тоді нові числа для дуг, що входять в нашу ланцюг, а також "старі" cij для всіх дуг , що не входять в нашу ланцюг, утворюють новий потік з вершини t в вершину s (ле ДКО перевірити простим міркуванням, що для нових чисел виконуються умови (1) - (4)). Крім того, величина нового потоку в порівнянні зі старим збільшилася на ds> 0. Для нового потоку знову проведемо ту ж процедуру і т. д.
Так як кожен раз величина потоку збільшується, принаймні, на 1 (пропускні спроможності ребер є цілими числами), а величина максимального потоку обмежена (величиною мінімального перетину), то ця процедура не може тривати нескінченно і, отже, на якомусь етапі отримаємо потік, для якого вершина s не входить в Y, т. е. потік є максимальним і величина його дорівнює величині мінімального перетину. Теорема доведена.
Міркування теореми Форда - Фалкерсона фактично є алгоритмом знаходження максимального потоку між двома вершинами (або доказом того, що цей потік є максимальним). Докладний приклад на цю тему наведено в розд. 15 "Рішення типових задач".
Примітка. Якщо в даному графі з пропускними здатностями ребер (т. Е. Мережі) є кілька джерел і кілька стоків, то описаний вище алгоритм можна застосувати такий спосіб. Вводимо нове джерело і новий стік, причому нове джерело з'єднуємо ребрами з усіма джерелами, а новий стік - з усіма стоками, при цьому пропускні спроможності нових ребер вважаємо як завгодно великими числами, так що ці дуги в будь-якому можливому потоці були б ненасиченими (нагадаємо, що ребра, що йдуть з джерела і ребра, що йдуть в стік завжди є прямими дугами). Після цього для нового графа вирішуємо завдання про максимальний потік (з одного нового джерела в один новий стік). Вирішивши її, стираємо всі введені ребра і вершини.
Розглянемо ще деякі питання (досить загального характеру) з теорії графів. Зауважимо, що в наступних розділах ми наводимо тільки найпростіші докази, а основні докази наведені в книзі Р. Уїлсона [6].