Підручник з дискретної математики
Потокомвсетімеждувершінойt (джерелом) іs (стоком) називається набір чисел сij, (т. Е. Кількість умовного "вантажу", що перевозиться з вершини з номером i в вершину з номером j), які відповідають чотирьом умовам:
3) якщо вершина з номером i - проміжна (не збігається з джерелом і стоком), то
т. е. кількість "вантажу", що вивозиться з вершини i, дорівнює кількості "вантажу", що ввозиться в цю вершину;
4) кількість "вантажу", що вивозиться з джерела t, має дорівнювати кількості вантажу, що ввозиться в стік s:
Число А називається величиною даного потоку або просто потоком між t і s.
Для подальшого нам потрібно наступне визначення:
Нехай є деяка перетин між вершинами t і s. Тоді величиною перетину називається сума пропускних спроможностей ребер, що входять в це перетин. Перетин називається мінімальним (максимальним), якщо його величина мінімальна (максимальна).
Теорема Форда - Фалкерсона (1955). Максимальний потік між вершинами t і s дорівнює величині мінімального перетину між цими вершинами.
Доказ цієї теореми є конструктивним (т. Е. Показує, як знайти потрібний максимальний потік), тому наводиться нижче.
- Доведемо спочатку, що будь-який потік між вершинами t і s менше або дорівнює величині будь-якого перетину. Нехай дано деякий потік і деякий перетин. Величина даного потоку складається з величин "вантажів", що перевозяться по всьому возможнимпутям з вершини t в s. Кожен такий шлях зобов'язаний мати загальне ребро з даними перетином. Так як по кожному ребру перетину сумарно можна перевести "вантажу" більше, ніж його пропускна здатність, тому сума всіх вантажів менше або дорівнює, сумі всіх пропускних спроможностей ребер даного перетину. Затвердження доведено.
Звідси випливає, що будь-який потік менше або дорівнює величині мінімального перетину, а значить і максимальний потік менше або дорівнює величині мінімального перетину.
Більш точно, безліч помічених вершин Y утворюється в такий спосіб:
джерело t належить Y і його позначка (0, Ґ); друге число, умовно кажучи, дорівнює нескінченності - що для дискретної математики означає, що це настільки велике число, як нам знадобиться;
якщо вершина i належить Y і cij
якщо вершина до належить Y і сjk> 0 (зворотна дуга), то вершина з номером j також повинна належати Y і її позначка дорівнює (- к. dj), де знак мінус означає, що вершина j пов'язана з уже поміченої вершиною до зворотного дугою , dj = mink, qjk + cjk>, причому очевидно, що 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].