ТЕОРЕМА ФОРДУ
Потоком у мережі між вершиноюt(джерелом) іs(стоком) називається набір чиселcij, (тобто кількість умовного “вантажу”, що перевозиться з вершини з номеромiу вершину з номеромj), що задовольняють чотирма умовами:
1) числаcijЈ 0, причому якщоcij> 0, тоcji= 0 (немає зустрічних перевезень);
2) числаcijЈqij(відповідних пропускних здібностей ребер);
3) якщо вершина з номером i – проміжна (не співпадає з джерелом та стоком), то
т. е. кількість "вантажу", що вивозиться з вершиниi, дорівнює кількості "вантажу", що ввозиться в цю вершину;
4) кількість “вантажу”, що вивозиться з джерелаt, має дорівнювати кількості вантажу, що ввозиться у стікs:
ЧислоАназивається величиною даного потоку або просто потоком міжtіs.
Для подальшого потрібне таке визначення:
Нехай є деякий переріз між вершинамиtтаs. Тоді величиною перерізу називається сума пропускних здібностей ребер, що входять до цього перерізу. Перетин називається мінімальним (максимальним), якщо його величина мінімальна (максимальна).
Теорема Форда - Фалкерсона (1955). Максимальний потік між вершинамиtіsдорівнює величині мінімального перерізу між цими вершинами.
Доказ цієї теореми є конструктивним (тобто показує, як знайти потрібний максимальний потік), тому наводиться нижче.
Доведемо спочатку, що будь-який потік між вершинамиtіsменший або дорівнює величині будь-якого перерізу. Нехай дано деякий потік і деякий переріз. Величина цього потокускладається з величин "вантажів", що перевозяться по всіх можливих шляхах з вершиниtуs. Кожен такий шлях повинен мати спільне ребро з цим перетином. Так як по кожному ребру перерізу сумарно не можна перекласти "вантажу" більше, ніж його пропускна здатність, тому сума всіх вантажів менша або дорівнює сумі всіх пропускних здібностей ребер даного перерізу. Твердження доведене.
Звідси випливає, що будь-який потік менший або дорівнює величині мінімального перерізу, а значить і максимальний потік менший або дорівнює величині мінімального перерізу.
1. Доведемо тепер зворотну нерівність. Нехай є деякий потік cij (якийсь потік завжди існує, наприклад, нульовий, коли всі cij = 0). Помічатимемо вершини графа, причому вважаємо, що всі помічені вершини утворюють безліч Y. Позначки вершин виробляються від джерела. Кожна позначка вершини (якщо ця вершина може бути позначена) складається з двох чисел: перше – це “+” або “–” номер вершини (з Y), з якою пов'язана нова вершина, що позначається, і друге – (обов'язково має бути позитивним) – це фактично та добавка до потоку, яка може бути додатково "довезена" до цієї вершини з джерела в порівнянні з вихідним потоком.
Більш точно, безліч помічених вершин Y утворюється так:
джерело t належить Y та його позначка (0,Ґ ); друге число, умовно кажучи, дорівнює нескінченності - що для дискретної математики означає, що це настільки велике число, як нам знадобиться;
якщо вершина i належить Y таcij0 дорівнюєdj= min dj,qij-cij>. Зауважимо, що тут числоdi– це друге число вже поміченої вершини i, а знак + перед номером i означає, що дуга, що зв'язує вершини (i, j), є прямою (і ненасиченою);
якщо вершина належить Y іcik> 0 (зворотна дуга), то вершина з номером j також повинна належати Y та її позначка дорівнює (–к,dj), де знак мінус означає, що вершина j пов'язана з уже поміченою вершиною до зворотної дугою,dj= min dk,qik+cik, причому очевидно, що dj також строго більше нуля. Таким чином, побудова множини Y є індуктивним, тобто нова вершина додається в Y, якщо вона пов'язана з деякою вершиною вже входить у Y або прямою ненасиченою дугою, або зворотною дугою.
Після того, як побудова безлічі Y закінчена (до нього не можна додати нових вершин), можливі 2 випадки.
1. Стік (тобто вершина з номером s) не входить у безліч вершин Y. Тоді позначимо безліч вершин, що не входять у Y через Z. Наш граф за умовою є зв'язковим, тому з Y, Z йдуть деякі ребра. За правилами побудови Y ці ребра є прямими насиченими дугами (рис. 1).
Ребра, що йдуть з безлічі Y Z, утворюють переріз між вершинами t і s. Видно також, що сума пропускних здібностей ребер цього перерізу (а всі ці ребра є прямими, насиченими) дорівнює потоку t s. Значить, даний потік є максимальним (оскільки він дорівнює величині деякого перерізу), а даний переріз є мінімальним.
2. Вершина s також входить до Y, і нехай друге число її позначки d s > 0. Тоді, очевидно, що між вершинами t і s існує ланцюг (що складається з спрямованих ребер - прямих і зворотних дуг), що з'єднує ці вершини
Схематично це на рис. 2
Зауважимо, що дуга, що виходить із джерела, і дуга, що входить у стік, повинні бути обов'язково прямими. Додамоdsдоcijдля прямих дуг цього ланцюга (за побудовою видно, щоотримане число буде менше або дорівнюєqij) і віднімемо цеds зcijдля зворотних дуг (може вийти негативне число, але воно обов'язково буде по абсолютній величині менше qij, оскільки за побудовоюdsЈcij+qij, а це означає, що зворотна дуга змінює напрямок, стає прямою дугою і його "навантаження" дорівнюватиме модулю числа
Тоді нові числа для дуг, що входять до нашого ланцюга, а також “старі” для всіх дуг, що не входять до нашого ланцюга, утворюють новий потік з вершини t у вершинуs(легко перевірити простою міркуванням, що для нових чисел виконуються умови (1)–(4)). Крім того, величина нового потоку в порівнянні зі старим збільшилася на ds. 0 . Для нового потоку знову проведемо ту саму процедуру тощо.
Так як щоразу величина потоку збільшується, принаймні, на 1 (пропускні здібності ребер є цілими числами), а величина максимального потоку обмежена (величиною мінімального перерізу), то ця процедура не може тривати нескінченно і, отже, на якомусь кроці отримаємо потік, для якого вершина s не входить у Y, тобто потік є максимальним і величина його дорівнює величині мінімального перерізу. Теорему доведено.
Міркування теореми Форда - Фалкерсона фактично є алгоритмом знаходження максимального потоку між двома вершинами (або доказом того, що цей потік є максимальним). Примітка. Якщо даному графі з пропускними здібностями ребер (т. е. мережі) є кілька джерел і кілька стоків, то описаний вище алгоритм можна застосувати в такий спосіб. Вводимо нове джерело та новий стік, причому нове джерело з'єднуємо ребрами з усіма джерелами, а новий стік – з усіма стоками, при цьому пропускні здібності нових ребервважаємо як завгодно великими числами, так що ці дуги в будь-якому можливому потоці були б ненасиченими (нагадаємо, що ребра, що йдуть з джерела і ребра, що йдуть у стік завжди є прямими дугами). Після цього для нового графа розв'язуємо задачу про максимальний потік (з одного нового джерела в один новий стік). Вирішивши її, стираємо всі введені ребра та вершини.