Алгоритм або метод Форда – Фалкерсона – класичний алгоритм для знаходження максимального потоку в орієнтованій мережі з пропускними здатностями (транспортній мережі). Алгоритм розробили Лестер Форд і Делберт Фалкерсон у 1956 р. Його основна мета – знайти максимальний потік у транспортній (потоковій) мережі, тобто в орієнтованому графі, де кожне ребро має пропускну здатність. У математиці та інформатиці "транспортна мережа" – це модель потоку в графі (не обов'язково транспорт у буквальному сенсі).

Метод Форда – Фалкерсона – це метод, який базується на трьох концепціях: залишкова мережа, збільшуючі шляхи та розрізи. Ключову роль у методі Форда – Фалкерсона відіграють поняття: залишкової мережі та збільшуючого шляху. Ці концепції лежать в основі важливої теореми про максимальний потік і мінімальний розріз, яка встановлює, що величина максимального потоку дорівнює пропускній здатності мінімального розрізу транспортної мережі. Метод Форда – Фалкерсона є ітеративним: спочатку потік у всіх ребрах дорівнює 0: при будь-яких , Є . На кожній ітерації величина потоку збільшується завдяки пошуку збільшуючого шляху – тобто такого шляху від джерела до стоку , уздовж якого можна передати додатковий потік. Процес триває доти, поки в залишковій мережі існує хоча б один збільшуючий шлях.

Алгоритми

Нехай граф, і для кожного ребра з в , нехай буде ємність і буде потік. Ми хочемо знайти максимальний потік від джерела до раковини . Після кожного кроку в алгоритмі виходить наступне:

| Обмеженість потенціалу: || ||Потік уздовж краю не може перевищувати свій потенціал. |- | Косі симетрії: || || Чистий потік від до повинен бути протилежністю чистого припливу від до (див приклад). |- | Збереження потоку: || || Тобто, якщо не або . Чистий потік до вузла дорівнює нулю, за винятком джерела, яке «виробляє» потік, і раковини, яка «поглинає» потік. |- | Значення (F): || ||Тобто, потік виходячи з повинен бути рівним потоку, що надходить у .

Це означає, що потік через мережу є легальним потоком після кожного раунду в алгоритмі. Визначимо залишкову мережу , щоб бути в мережі з потужністю , і без потоку. Зверніть увагу, що може статися, що потік від до дозволений в залишковій мережі, хоча заборонений в вихідній мережі: якщо та , тоді .

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

Алгоритм:

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

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

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

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

4. Сток не може бути позначений, це означає, що потік не може бути збільшений і що знайдений потік на попередніх кроках є максимальним. Ford Fulkerson Method () 1. Задаємо початкове значення потоку ; 2. while (Поки) існує шлях що збільшується ; 3. do збільшуємо потік уздовж шляху ; 4. return ;

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

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

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

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

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

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

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

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

Залишкова мережа – мережа, що складається з ребер, що допускають збільшення потоку. Більш строго, нехай дана транспортна мережа з джерелом і стоком . Нехай  – деякий потік в . Розглянемо пару вершин ,. Величина додаткового потоку, який ми можемо направити з в , не перевищивши пропускну спроможність , є залишковою пропускною здатністю ( residual capacity ) ребра (), і задається формулою . Наприклад, якщо і , то можна збільшити на , не порушивши обмеження пропускної спроможності для ребра . Коли потік негативний, то залишкова пропускна спроможність більше ніж пропускна спроможність . Так, якщо . Цю ситуацію можна зобразити наступним чином: існує потік величиною 4 одиниці з в , не порушивши обмеження пропускної здатності для ребра . Таким чином, починаючи з потоку , ми направили додаткові 20 одиниць потоку, перш ніж досягли обмеження пропускної спроможності. Для заданої транспортної мережі і потоку , залишкової мережі (residual network) в , породженої потоком , є мережа , де .

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

Таким чином, як і зазначалося вище, по кожному ребру залишкової мережі, або залишковим ребру (residual edge) , можна направити потік, більший 0. На Малюнку 1 (а) відтворені транспортна мережа і потік , представлені на рисунку 1 (б), а на Малюнку 1 (б), показана відповідна залишкова мережа . Ребрами є або ребра , або зворотні їм. Якщо для деякого ребра , то і . Якщо для деякого ребра , то . У такому випадку і, отже, . Якщо у вихідній мережі немає ні ребра , ні , то , і . Таким чином, можна зробити висновок, що ребро може опинитися в остаточній мережі тільки в тому випадку, якщо хоча б одне з ребер або знаходиться у вихідній транспортній мережі, тому: Зверніть увагу, що залишкова мережа є транспортною мережею зі значеннями пропускних спроможностей, заданими . Наступна лема показує, як потік у залишковій мережі пов'язаний з потоком у вихідній транспортній мережі.

Для збереження потоку, при всіх виконується рівність . І тоді, .

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

Для заданої транспортної мережі і потоку шляхом, що збільшується ( augmenting path) є простий шлях з в в залишковій мережі . Згідно з визначенням залишкової мережі, кожне ребро шляху, що збільшується допускає деякий додатковий позитивний потік з в без порушення обмеження пропускної здатності для даного ребра. Виділений шлях на Малюнку 1 (б) є шляхом, що збільшується. Розглядаючи представлену на малюнку залишкову мережу як як деяку транспортну мережу, можна збільшувати потік уздовж кожного ребра даного шляху аж до 4 одиниць, не порушуючи обмежень пропускної здатності, оскільки найменша залишкова пропускна спроможність на даному шляху становить . Максимальна величина, на яку можна збільшити потік уздовж кожного ребра шляху, що збільшується і задається формулою .

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

У методі Форда – Фалкерсона проводиться неодноразове збільшення потоку уздовж шляхів, що збільшуються до тих пір, поки не буде знайдений максимальний потік. Для доказу даної теореми вводимо поняття розрізу. Розрізом (CUT) транспортної мережі називається розбиття множини вершин на безлічі і , такі що , а . Якщо  – потік, то чистий потік (net flow) через розріз за визначенням дорівнює . Пропускною здатністю (capacity) розрізу є . Мінімальним розрізом (minimum cut) мережі є розріз, пропускна здатність якого серед всіх розрізів мережі мінімальна. На Малюнку 2 показаний розріз транспортної мережі. Чистий потік через даний розріз дорівнює , а пропускна здатність цього розрізу дорівнює . Зверніть увагу, що чистий потік через розріз може включати в себе негативні потоки між вершинами, але пропускна здатність розрізу складається виключно з невід'ємних значень. Іншими словами, чистий потік через розріз складається з позитивних потоків в обох напрямках; позитивний потік з в додається, а позитивний потік з в віднімається. З іншого боку, пропускна здатність розрізу обчислюється тільки по ребрах, що йде з в . Ребра, що ведуть з в , не беруть участі в обчисленні . Наступна лема показує, що чистий потік через будь розріз однаковий і дорівнює величині потоку.

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

Якщо  — деякий потік в транспортній мережі з джерелом і стоком , то наступні твердження еквівалентні. 1.  – максимальний потік в . 2. Залишкова мережа не містить збільшують шляхів. 3. для деякого розрізу мережі .

Доведення (1) → (2): Припустимо, що є максимальним потоком в , але містить збільшує шлях . Відповідно до наслідку Леми 2, сума потоків , де задається рівнянням з наслідку Леми 3, є потоком в , величина якого суворо більше, ніж , що суперечить припущенню, що  – максимальний потік.

(2) → (3): Припустимо, що не містить шляху, що збільшується, тобто не містить шляху з в . Визначимо існує шлях з . Розбиття є розрізом: очевидно, що , а не належить , оскільки в не існує шляху з в . Для кожної пари вершин справедливо співвідношення , оскільки в іншому випадку і слід помістити в множину . Отже, згідно Леми 3, .

(3) → (1): Згідно наслідку Леми 3, для всіх розрізів , тому з умови випливає, що  — максимальний потік.

Леми

Лема 1

Нехай  – транспортна мережа з джерелом і стоком , а  – потік в . Нехай  – залишкова мережа в , породжена потоком , а  – потік в . Тоді сума потоків , обумовлена рівнянням, є потоком в , і величина цього потоку дорівнює

Доведення

Для , справедливо: . Так як

для всіх . То випливає, що .

Лема 2

Нехай  – транспортна мережа, а  – деякий потік в , і нехай  – деякий шлях, що збільшується у . Визначимо функцію → наступним чином: якщо належить , якщо належить , в іншому випадку. Тоді є потоком в і його величина становить . Випливає з даної леми наслідок показує, що якщо додати до , то ми отримаємо новий потік в , величина якого ближче до максимальної. На Малюнку 1 (в), показаний результат додавання , представленого на рисунку 1 (б), до , показаному на рисунку 1 (а).

Лема 3

Нехай  – деякий потік в транспортній мережі з джерелом і стоком , і нехай  – розріз . Тоді чистий потік через дорівнює .

Доведення

Зауважимо, що відповідно до властивості збереження потоку , так що . Безпосереднім наслідком леми є доведений раніше результат – що величина потоку дорівнює сумарному потоку, що входить в стік. Інший наслідок леми показує, як пропускні спроможності розрізів можна використовувати для визначення кордону величини потоку.

Наслідок

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

Доведення

Нехай  – довільний розріз , а  – деякий потік. Згідно з попередньою лемою і обмеженням пропускної здатності,

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

Дослідження

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