Алгоритм Форда — Фалкерсона

Алгоритм або метод Форда — Фалкерсона знаходить максимальний потік у транспортній мережі.

Метод Форда — Фалкерсона — метод, який базується на трьох концепціях: залишкові мережі, шляхи що збільшуються і розрізи. Ключову роль у методі Форда — Фалкерсона грають два поняття: залишкові мережі і доповнюють шляху.  Дані концепції лежать в основі важливої теореми про максимальний потік і мінімальний розріз, яка визначає значення максимального нащадка за допомогою розрізів траспортної мережі. Метод Форда — Фалкерсона є ітеративним. Спочатку величині потоку присвоюється значення 0: $f(u,v)=0$ при будь-яких $u$, $v$ Є $V$. На кожній ітерації величина потоку збільшується за допомогою пошуку «шляху, що збільшується» (тобто деякого шляху від джерела $s$ до стоку $t$, уздовж якого можна послати більший потік) і подальшого збільшення потоку. Цей процес повторюється до тих пір, поки вже неможливо буде відшукати збільшуючийся шлях.

Алгоритми

Нехай $G(V,E)$ граф, і для кожного ребра з $u$ в $v$, нехай $c(u,v)$ буде ємність і $f(u,v)$ буде потік. Ми хочемо знайти максимальний потік від джерела $s$ до раковини $t$. Після кожного кроку в алгоритмі виходить наступне:

Обмеженість потенціалу:	$\forall (u,v)\in E\ f(u,v)\leq c(u,v)$	Потік уздовж краю не може перевищувати свій потенціал.
Косі симетрії:	$\forall (u,v)\in E\ f(u,v)=-f(v,u)$	Чистий потік від $u$ до $v$ повинен бути протилежністю чистого припливу від $v$ до $u$ (див приклад).
Збереження потоку:	$\forall u\in V:(u\neq s\land u\neq t)\Rightarrow \sum _{w\in V}f(u,w)=0$	Тобто, якщо $u$ не $s$ або $t$. Чистий потік до вузла дорівнює нулю, для джерела, який «виробляє» потік, і раковину, яка «поглинає» потік.
Значення (F):	$\sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)$	Тобто, потік виходячи з $s$ повинен бути рівним потоку, що надходить у $t$.

Це означає, що потік через мережу є легальним потоком після кожного раунду в алгоритмі. Визначимо залишкову мережу $G_{f}(V,E_{f})$, щоб бути в мережі з потужністю $c_{f}(u,v)=c(u,v)-f(u,v)$, і без потоку. Зверніть увагу, що може статися, що потік від $v$ до $u$ дозволений в залишковій мережі, хоча заборонений в вихідній мережі: якщо $f(u,v)>0$ та $c(v,u)=0$, тоді $c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0$.

Алгоритм Форда — Фалкерсона

Алгоритм:

На першому етапі джерелу присвоюється позначка нескінченність. На цьому етапі всі інші вузли не помічені. Постараємося розставити позначки дійшовши до стоку T®S.

1. Дійшовши до стоку йому приписуємо позначку [qij, k].

2. Шлях потоку від джерела буде знайдений і потік для кожної дуги цього шляху збільшиться на величину qt.

3. Дійшовши до стоку ми почнемо розставляти позначки спочатку, при цьому необхідно стежити, щоб залишкова пропускна здатність всіх дуг була перевищена.

4. Сток не може бути позначений, це означає, що потік не може бути збільшений і що знайдений потік на попередніх кроках є максимальним.

Ford Fulkerson Method ($G,s,t$)
1. Задаємо початкове значення потоку $f=0$;
2. while (Поки) існує шлях що збільшується $p$;
3. do збільшуємо потік $f$ уздовж шляху $p$;
4. return $f$;

Розріз

Існує теорема про максимальний потік в мережі, вона полягає в тому, що максимальний потік в мережі дорівнює її мінімального розрізу.

Розріз — це безліч дуг виключення яких ділить всі безліч вузлів в мережі на 2 непересічних частини.

Пропускна здатність розрізу — це сума пропускної здатності дуг входять в розріз.

Відповідно до цієї теореми ми можемо побудувати і розглянути всі розрізи і знайти мінімум — це максимум пропускної здатності даної мережі. Але з цієї теоремі ми не можемо знайти всі потоки проходять по дугах мережі. Використовуються позначки для вказівки величини потоку і його джерело.

Наприклад, якщо з вершини i в j передається qj одиниць потоку і ця добавка викликає збільшення потоку по дузі, то вузлу j приписується позначка [qj, i], якщо ж величина потоку qj викликає зменшення потоку по цій дузі, то вузлу j присвоюється позначка [ -qij, i].

[qj, i] — пряма дуга; [-qj, i] — зворотна дуга.

Потік по кожній прямій дузі збільшується, при цьому він не повинен перевищувати її пропускну спроможність, а потік по кожній зворотного дузі зменшується, але при цьому він не повинен ставати негативним.

Залишкові мережі

Залишкова мережа — мережа, що складається з ребер, що допускають збільшення потоку. Більш строго, нехай дана транспортна мережа $G=(V,E)$ з джерелом $s$ і стоком $t$. Нехай $f$ — деякий потік в $G$. Розглянемо пару вершин $u$,$v\in V$. Величина додаткового потоку, який ми можемо направити з $u$ в $v$, не перевищивши пропускну спроможність $c(u,v)$, є залишковою пропускною здатністю ( residual capacity ) ребра ($u,v$), і задається формулою $c_{f}(u,v)=c(u,v)-f(u,v)$ . Наприклад, якщо $c(u,v)''=16$ і $f(u,v)=11$, то $f(u,v)$ можна збільшити на $c_{f}(u,v)=5$, не порушивши обмеження пропускної спроможності для ребра $(u,v)$. Коли потік $f(u,v)$ негативний, то залишкова пропускна спроможність $c_{f}(u,v)$ більше ніж пропускна спроможність $c(u,v)$. Так, якщо $c(u,v)=20$. Цю ситуацію можна зобразити наступним чином: існує потік величиною 4 одиниці з $u$ в $v$, не порушивши обмеження пропускної здатності для ребра $(u,v)$. Таким чином, починаючи з потоку $f(u,v)=-4$, ми направили додаткові 20 одиниць потоку, перш ніж досягли обмеження пропускної спроможності. Для заданої транспортної мережі $G=(V,E)$ і потоку $f$, залишкової мережі (residual network) в $G$, породженої потоком $f$, є мережа $G_{f}-(V,E_{f})$, де $E_{f}={(u,v)\in V*V:c_{f}(u,v)>0}$.

Малюнок 1

На Мал. 1 зображені:
а) Транспортна мережа $G$ і потік $f$.
б) Залишкова мережа $G_{f}$ з виділеним збільшуючимся шляхом; його залишкова пропускна здатність дорівнює$4$.
в) Потік в мережі $G$, отриманий в результаті збільшення потоку уздовж шляху $p$ на величину його залишкової пропускної здатності$4$.
г) Залишкова мережу, породжена потоком, показаним в частині в)

Таким чином, як і зазначалося вище, по кожному ребру залишкової мережі, або залишковим ребру (residual edge) , можна направити потік, більший 0. На Малюнку 1 (а) відтворені транспортна мережа $G$ і потік $f$, представлені на рисунку 1 (б), а на Малюнку 1 (б), показана відповідна залишкова мережа $G_{f}$. Ребрами $E_{f}$ є або ребра $E$, або зворотні їм. Якщо $f(u,v)<c(u,v)$ для деякого ребра $(u,v)\in E$, то $c_{f}(u,v)=c(u,v)-f(u,v)>0$ і $(u,v)\in E_{f}$. Якщо $f(u,v)>0$ для деякого ребра $(u,v)\in E$, то $F(v,u)<0$. У такому випадку $c_{f}(v,u)=c(v,u)-f(v,u)>0$ і, отже, $(v,u)\in E_{f}$. Якщо у вихідній мережі немає ні ребра $(u,v)$, ні $(v,u)$, то $c(u,v)=c(v,u)=0,f(u,v)=f(v,u)=0$, і $c_{f}(u,v)=c_{f}(v,u)=0$. Таким чином, можна зробити висновок, що ребро $(u,v)$ може опинитися в остаточній мережі тільки в тому випадку, якщо хоча б одне з ребер $(u,v)$ або $(v,u)$ знаходиться у вихідній транспортній мережі, тому:$|E_{f}|\leq 2|E|$ Зверніть увагу, що залишкова мережа $G_{f}$ є транспортною мережею зі значеннями пропускних спроможностей, заданими $c_{f}$. Наступна лема показує, як потік у залишковій мережі пов'язаний з потоком у вихідній транспортній мережі.

Для збереження потоку, при всіх $u\in V-{s,t}$ виконується рівність $\sum _{v\in V}(f+f)(u,v)=\sum _{v\in V}(f(u,v)+f(u,v))=\sum _{v\in V}f(u,v)+\sum _{v\in V}f(u,v)=0+0$. І тоді, $|f+f|=\sum _{v\in V}(f+f)(s,u)''=\sum _{v\in V}(f(s,u)+f(s,u))=\sum _{v\in V}f(s,u)+\sum _{v\in V}f(s,u)=|f|+|F|$.

Шляхи, що збільшуються

Для заданої транспортної мережі $G=(V,E)$ і потоку $f$ шляхом, що збільшується ( augmenting path) є простий шлях з $s$ в $t$ в залишковій мережі $G_{f}$. Згідно з визначенням залишкової мережі, кожне ребро $(u,v)$ шляху, що збільшується допускає деякий додатковий позитивний потік з $u$ в $v$ без порушення обмеження пропускної здатності для даного ребра. Виділений шлях на Малюнку 1 (б) є шляхом, що збільшується. Розглядаючи представлену на малюнку залишкову мережу як $G_{f}$ як деяку транспортну мережу, можна збільшувати потік уздовж кожного ребра даного шляху аж до 4 одиниць, не порушуючи обмежень пропускної здатності, оскільки найменша залишкова пропускна спроможність на даному шляху становить $C_{f}(v_{2},v_{3})=4$. Максимальна величина, на яку можна збільшити потік уздовж кожного ребра шляху, що збільшується $p$ і задається формулою $c_{f}(p)=min{c_{f}(u,v):(u,v)\in p}$.

Розрізи транспортних мереж

У методі Форда — Фалкерсона проводиться неодноразове збільшення потоку уздовж шляхів, що збільшуються до тих пір, поки не буде знайдений максимальний потік. Для доказу даної теореми вводимо поняття розрізу. Розрізом (CUT) $(S,T)$ транспортної мережі $G=(V,E)$ називається розбиття множини вершин на безлічі $S$ і $T=V-S$, такі що $s\in S$, а $t\in T$. Якщо $f$ — потік, то чистий потік (net flow) через розріз $(S,T)$ за визначенням дорівнює $f(S,T)$. Пропускною здатністю (capacity) розрізу $(S,T)$ є $c(S,T)$. Мінімальним розрізом (minimum cut) мережі є розріз, пропускна здатність якого серед всіх розрізів мережі мінімальна. На Малюнку 2 показаний розріз $({s,v_{1},v_{2}},{v_{3},v_{4},t})$ транспортної мережі. Чистий потік через даний розріз дорівнює $f(v_{1},v_{3})+f(v_{2},v_{3})+f(v_{2},v_{4})=12+(-4)+11=19$, а пропускна здатність цього розрізу дорівнює $c(v_{1},v_{3})+c(v_{2},v_{4})=12+14=26$. Зверніть увагу, що чистий потік через розріз може включати в себе негативні потоки між вершинами, але пропускна здатність розрізу складається виключно з невід'ємних значень. Іншими словами, чистий потік через розріз $(S,T)$ складається з позитивних потоків в обох напрямках; позитивний потік з $S$ в $T$ додається, а позитивний потік з $T$ в $S$ віднімається. З іншого боку, пропускна здатність розрізу $(S,T)$ обчислюється тільки по ребрах, що йде з $S$ в $T$. Ребра, що ведуть з $T$ в $S$, не беруть участі в обчисленні $c(S,T)$. Наступна лема показує, що чистий потік через будь розріз однаковий і дорівнює величині потоку.

Малюнок 2. Розріз (S, T) транспортної мережі, представленої на рисунку 1 (б), S = {s, v ₁ , v ₂ }, T = {v ₃ , v ₄ , t} . Вершини, що належать S , відзначені чорним кольором, а вершини T  — білим.

Теорема про максимальний потік і мінімальний розріз

Якщо $f$ — деякий потік в транспортній мережі $G=(V,E)$ з джерелом $s$ і стоком $t$, то наступні твердження еквівалентні. 1. $f$ — максимальний потік в $G$. 2. Залишкова мережа $G_{f}$ не містить збільшують шляхів. 3. $|f|=C(S,T)$ для деякого розрізу $(S,T)$ мережі $G$.

Доведення

(1) → (2): Припустимо, що $f$ є максимальним потоком в $G$, але $G_{f}$ містить збільшує шлях $p$. Відповідно до наслідку Леми 2, сума потоків $f+f_{p}$, де $f_{p}$ задається рівнянням з наслідку Леми 3, є потоком в $G$, величина якого суворо більше, ніж $|f|$, що суперечить припущенню, що $f$ — максимальний потік.

(2) → (3): Припустимо, що $G_{f}$ не містить збільшуючого шляху, тобто $G_{f}$ не містить шляху з $s$ в $t$. Визначимо $S=((v\in V):G_{f})$ існує шлях з $(s\in v)$ $T=V-S$. Розбиття $(S,T)$ є розрізом: очевидно, що $s\in S$, а $t$ не належить $S$, оскільки в $G_{f}$ не існує шляху з $s$ в $t$. Для кожної пари вершин $u\in S,v\in T$ справедливо співвідношення $f(u,v)=c(u,v)$, оскільки в іншому випадку $(u,v)\in E_{f}$ і $v$ слід помістити в множину $S$. Отже, згідно Леми 3, $|f|=F(S,T)=c(S,T)$.

(3) → (1): Згідно наслідку Леми 3, $|f|\leqslant c(S,T)$ для всіх розрізів $(S,T)$, тому з умови $|f|=C(S,T)$ випливає, що $f$ — максимальний потік.

Леми

Лема 1

Нехай $G=(V,E)$ — транспортна мережа з джерелом $s$ і стоком $t$, а $f$ — потік в $G$. Нехай $G_{f}$ — залишкова мережа в $G$, породжена потоком $f$, а $f$ — потік в $G_{f}$. Тоді сума потоків $f+f$, обумовлена рівнянням, є потоком в $G$, і величина цього потоку дорівнює$|f+f|=|F|+|F|$

Доведення

Для $u,v\in V$, справедливо: $(f+f)(u,v)=f(u,v)+f(u,v)=-f(v,u)-f(v,u)=-(f(v,u)+f(v,u))=-(f+f)(v,u)$. Так як $f(u,v)\leq c_{f}(u,v)$ для всіх $u,v\ inV$. То випливає, що $(f+f)(u,v)=f(u,v)+f(u,v)\leq f(u,v)+(c(u,v)-f(u,v))c(u,v)$.

Лема 2

Нехай $G=(V,E)$ — транспортна мережа, а $f$ — деякий потік в $G$, і нехай $p$ — деякий шлях, що збільшується у $G_{f}$. Визначимо функцію $f_{p}:V*V$ → $R$ наступним чином: $f_{p}(u,v)=c_{p}(p)$ якщо $(u,v)$ належить $p$, $f_{p}(u,v)=-c_{f}(p)$ якщо $(v,u)$ належить $p$, $f_{p}(u,v)=0$ в іншому випадку. Тоді $f_{p}$ є потоком в $G$ і його величина становить $|f_{p}|=C_{f}(p)>0$. Випливає з даної леми наслідок показує, що якщо додати $f_{p}$ до $f$, то ми отримаємо новий потік в $G$, величина якого ближче до максимальної. На Малюнку 1 (в), показаний результат додавання $f_{p}$, представленого на рисунку 1 (б), до $f$, показаному на рисунку 1 (а).

Лема 3

Нехай $f$ — деякий потік в транспортній мережі $G$ з джерелом $s$ і стоком $t$, і нехай $(S,T)$ — розріз $G$. Тоді чистий потік через $(S,T)$ дорівнює $f(S,T)=|f|$.

Доведення

Зауважимо, що відповідно до властивості збереження потоку $f(S-s,V)=0$, так що $f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V)=|f|$. Безпосереднім наслідком леми є доведений раніше результат — що величина потоку дорівнює сумарному потоку, що входить в стік. Інший наслідок леми показує, як пропускні спроможності розрізів можна використовувати для визначення кордону величини потоку.

Наслідок

Величина будь-якого потоку $f$ у транспортній мережі $G$ не перевищує пропускну спроможність довільного розрізу $G$.

Доведення

Нехай $(S,T)$ — довільний розріз $G$, а $f$ — деякий потік. Згідно з попередньою лемою і обмеженням пропускної здатності, $|f|=F(S,T)=\sum _{u\in S}\sum _{v\in T}f_{u,v}$ $\leq$ $\sum _{u\in S}\sum _{v\in T}c(u,v)=c(S,T)$

З цього наслідку випливає, що максимальний потік в мережі не перевищує пропускної здатності мінімального розрізу. Зараз ми сформулюємо і доведемо важливу теорему про максимальний потік і мінімальний розріз, в якій стверджується, що значення максимального потоку дорівнює пропускній здатності мінімального розрізу.

Дослідження

Вперше проблеми пов'язані з пересилкою потоків у мережах були розглянуті Канторовичем в 1933 році. (Більше того — він розглядав більш загальну задачу з рухом потоку рідин різних типів (multicommodity flows)). Основи теорії потоків були закладені в період з листопада 1954 по грудень 1955 дослідниками корпорації RAND (Санта-Моніка, Каліфорнія). Простежимо за розвитком теорії потоків у хронологічному порядку за звітами RAND.

Перший звіт «Максимальний потік в мережі» датується 19 м листопада 1954. Автори звіту — Форд (Ford) і Фалкерсоном (Fulkerson), довели теорему про максимальний потік і мінімальному розрізі для неорієнтованих графів: значення максимального потоку в мережі одно мінімальної пропускної здатності розрізу. (Розрізом в мережі називається розбиття множини її вершин на два непересічних класу, таких що джерело і стік лежать у різних класах. Пропускний здатністю розрізу називається сума пропускних спроможностей ребер, кінці яких лежать в різних класах.) У 1955 році в роботі Робахера (Robacher) було згадано, що вперше цю теорему довів Фалкерсоном.

Робота Форда і Фалкерсона про потоки і розрізах була мотивована вивченням транспортних мереж залізниць (див. Далі). У тому ж звіту вони також описали простий алгоритм знаходження максимального потоку для планарних графів, що володіють такими додатковим властивістю: після додавання дуги з джерела в стік граф залишається планарним.

Посилання

• Бібліотека алгоритмів [Архівовано 22 грудня 2015 у Wayback Machine.]