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

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

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

Алгоритми

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

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

Це означає, що потік через мережу є легальним потоком після кожного раунду в алгоритмі. Визначимо залишкову мережу ${\displaystyle G_{f}(V,E_{f})}$, щоб бути в мережі з потужністю ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$, і без потоку. Зверніть увагу, що може статися, що потік від ${\displaystyle v}$ до ${\displaystyle u}$ дозволений в залишковій мережі, хоча заборонений в вихідній мережі: якщо ${\displaystyle f(u,v)>0}$ та ${\displaystyle c(v,u)=0}$, тоді ${\displaystyle 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 (${\displaystyle G,s,t}$) 1. Задаємо початкове значення потоку ${\displaystyle f=0}$; 2. while (Поки) існує шлях що збільшується ${\displaystyle p}$; 3. do збільшуємо потік ${\displaystyle f}$ уздовж шляху ${\displaystyle p}$; 4. return ${\displaystyle f}$; 

Розріз

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

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

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

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

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

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

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

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

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

Малюнок 1

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

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

Для збереження потоку, при всіх ${\displaystyle u\in V-{s,t}}$ виконується рівність ${\displaystyle \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}$. І тоді, ${\displaystyle |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|}$.

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

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

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

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

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

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

Докладніше: Теорема Форда — Фалкерсона

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

Доведення

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

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

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

Леми

Лема 1

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

Доведення

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

Лема 2

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

Лема 3

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

Доведення

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

Наслідок

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

Доведення

Нехай ${\displaystyle (S,T)}$ — довільний розріз ${\displaystyle G}$, а ${\displaystyle f}$ — деякий потік. Згідно з попередньою лемою і обмеженням пропускної здатності, ${\displaystyle |f|=F(S,T)=\sum _{u\in S}\sum _{v\in T}f_{u,v}}$ ${\displaystyle \leq }$ ${\displaystyle \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) було згадано, що вперше цю теорему довів Фалкерсоном.

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

Примітки

1. Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 26.2 Метод Форда — Фалкерсона. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

Посилання

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