📅 Липень 2026⏱ 13 хв🟡 Середній рівень·Останнє оновлення: 3 липня 2026 р.
Максимальний потік у мережах: як працює алгоритм Форда-Фалкерсона
Скільки води може пройти через мережу труб, перш ніж якесь вузьке місце обмежить потік? Скільки пакетів за секунду може пройти інтернетом від сервера-джерела до сервера-призначення? Задача про максимальний потік дає точну відповідь на це питання, а її розв'язок — теорема про максимальний потік і мінімальний розріз — один з найелегантніших і найкорисніших результатів усієї алгоритмічної теорії графів.
1. Потокові мережі: пропускні здатності та збереження
Потокова мережа — це орієнтований граф G = (V, E), де кожне ребро (u, v) має невід'ємну пропускну здатність c(u,v) ≥ 0 — максимальну кількість "речовини" (вода, струм, дані, товари), яка може пройти через нього. Двом особливим вершинам надано спеціальні ролі: джерело s (звідки потік починається) і стік t (куди потік прямує).
Потік — це функція f(u,v), що приписує кожному ребру дійсне число за двох умов:
Обмеження потокової мережі:
1. Обмеження пропускної здатності:
0 ≤ f(u,v) ≤ c(u,v) для кожного ребра (u,v)
2. Збереження потоку:
Σ f(v,u) = Σ f(u,w) для кожної вершини u ≠ s,t
(вхідний потік) (вихідний потік)
Величина потоку |f| — це чистий потік, що виходить із джерела:
|f| = Σ f(s,v) − Σ f(v,s)
v∈V v∈V
Мета: знайти потік f, що максимізує |f| за умов (1) і (2).
Збереження — той самий принцип, що й перший закон Кірхгофа для електричних кіл: усе, що втікає у внутрішній вузол, має витекти назад — нічого не створюється й не зникає, крім джерела та стоку. Саме це робить потокові мережі природною моделлю як для фізичних транспортних систем, так і для абстрактних задач на кшталт планування та паросполучення.
2. Залишкові графи та збільшувальні шляхи
Центральна ідея кожного алгоритму максимального потоку — залишковий граф G_f, що відстежує, скільки додаткового потоку ще можна протиснути через кожне ребро — і, що важливо, скільки потоку можна "скасувати", протиснувши в зворотному напрямку.
Залишкова пропускна здатність:
c_f(u,v) = c(u,v) − f(u,v) (залишок прямої пропускної здатності)
c_f(v,u) = f(u,v) (здатність "скасувати" наявний потік)
Залишковий граф G_f містить ребро (u,v), якщо c_f(u,v) > 0.
Збільшувальний шлях P — будь-який шлях від s до t у G_f.
Його вузьке місце (bottleneck) дорівнює:
Δ = min{ c_f(u,v) : (u,v) ∈ P }
Протискання Δ одиниць потоку вздовж P:
для кожного ребра (u,v) у P:
f(u,v) += Δ якщо (u,v) — пряме ребро
f(v,u) -= Δ якщо (u,v) — зворотне ребро
Саме зворотні ребра — той трюк, що робить метод коректним: ранній жадібний вибір можна частково "скасувати" пізніше, якщо виявиться, що він неоптимальний, дозволяючи алгоритму фактично перемаршрутизувати потік, ніколи не повертаючись до вихідної структури графу.
3. Метод Форда-Фалкерсона
Форд і Фалкерсон (1956) запропонували найпростішу можливу стратегію: багаторазово знаходити будь-який збільшувальний шлях у залишковому графі та протискати стільки потоку, скільки дозволяє його вузьке місце, доки збільшувальних шляхів не залишиться.
FORD-FULKERSON(G, s, t):
для кожного ребра (u,v) у E:
f(u,v) = 0
поки існує збільшувальний шлях P від s до t у G_f:
Δ = мінімальна залишкова пропускна здатність вздовж P
для кожного ребра (u,v) у P:
збільшити f вздовж (u,v) на Δ # оновити пряме/зворотне
перебудувати G_f
повернути f # f тепер максимальний потік
Термінація:
Якщо всі пропускні здатності — цілі числа, кожне збільшення
підвищує |f| щонайменше на 1, а |f| обмежено зверху повною
пропускною здатністю, що виходить із s → гарантована термінація
для цілочисельних пропускних здатностей.
За ірраціональних пропускних здатностей Форд-Фалкерсон може
взагалі не завершитися — класичний патологічний приклад
(Форд і Фалкерсон, 1962).
Чому "будь-який" шлях небезпечний: Форд-Фалкерсон не вказує, як шукати збільшувальний шлях — звичайний DFS може повторно обирати патологічно погані шляхи, вимагаючи до |f_max| ітерацій навіть на крихітних графах. На графі з пропускною здатністю 1 000 000 і лише двома шляхами пропускної здатності 1, що почергово насичуються й скасовують одне одного, наївний DFS-Форд-Фалкерсон потребує 2 000 000 ітерацій. Саме це мотивувало появу алгоритму Едмондса-Карпа.
4. Едмондс-Карп: гарантія поліноміального часу
Едмондс і Карп (1972) виправили патологічний найгірший випадок однією зміною: завжди обирати найкоротший збільшувальний шлях (з найменшою кількістю ребер), знайдений через пошук у ширину (BFS), а не DFS.
EDMONDS-KARP(G, s, t):
f = 0 на всіх ребрах
поки BFS(G_f, s, t) знаходить шлях P:
Δ = мінімальна залишкова пропускна здатність вздовж P
збільшити f вздовж P на Δ
повернути f
Аналіз складності:
Кожен BFS займає O(E).
Ключова лема: відстань найкоротшого шляху від s до будь-якої
вершини в G_f монотонно не спадає з кожною ітерацією.
Кожне ребро може стати "критичним" (насичити вузьке місце)
щонайбільше O(V) разів за весь запуск.
Загальна кількість збільшень: O(VE)
Загальна часова складність: O(V E²)
Порівняно з наївним Форд-Фалкерсоном: O(E · |f_max|) — не
обмежено ані V, ані E окремо, і може бути експоненційним для
ірраціональних або дуже великих цілих пропускних здатностей.
Едмондс-Карп став підручниковим стандартом, бо його складність — справжня поліноміальна межа, незалежна від самих значень пропускної здатності, чого наївному Форд-Фалкерсону бракує повністю.
5. Теорема про максимальний потік і мінімальний розріз
Розріз s-t — це поділ вершин на дві множини S і T = V \ S, де s ∈ S, а t ∈ T. Пропускна здатність розрізу — це сумарна пропускна здатність ребер, що перетинають межу від S до T. Інтуїтивно розріз відображає "вузьке місце" — набір труб, розрізавши які, можна повністю відʼєднати джерело від стоку.
Теорема про max-flow min-cut (Форд і Фалкерсон, 1956):
max |f| за всіма допустимими потоками f
=
min cap(S,T) за всіма розрізами s-t (S,T)
де cap(S,T) = Σ c(u,v) для u∈S, v∈T, (u,v)∈E
Схема доведення:
(≤) Слабка двоїстість: будь-яка величина потоку ≤ будь-якої
пропускної здатності розрізу, бо кожна одиниця потоку від s
до t повинна перетнути розріз щонайменше один раз.
(=) В оптимумі: коли Форд-Фалкерсон завершується, збільшувального
шляху не існує. Нехай S = вершини, досяжні з s у G_f,
T = решта. Кожне ребро, що перетинає S→T, має бути насиченим
(f = c), а кожне ребро T→S має нести потік 0 (інакше воно
було б залишковим ребром назад у S). Отже |f| = cap(S,T)
точно, що доводить: знайдений потік дорівнює пропускній
здатності саме цього розрізу — а значить, вона мінімальна.
Ця двоїстість — не лише теоретична елегантність: вона означає, що кожен алгоритм максимального потоку водночас є алгоритмом мінімального розрізу. Пошук мінімального набору ребер, видалення яких розʼєднує два вузли (наприклад, найслабші ланки в ланцюгу поставок або найвразливіші зʼєднання в електромережі), розв'язується безкоштовно, щойно обчислено максимальний потік.
6. Алгоритм Дініца та швидші методи
Алгоритм Дініца (1970) — O(V² E):
Повторювати:
1. Побудувати "пошаровий граф" через BFS від s (кожна вершина
позначена своєю відстанню найкоротшого шляху від s у G_f).
2. Знайти блокувальний потік у пошаровому графі через DFS —
потік, за якого кожен шлях s-t насичений принаймні один раз.
3. Додати блокувальний потік до f; перебудувати пошаровий граф.
Поки t недосяжний з s у G_f.
Ключовий факт: "рівень" t за BFS строго зростає після кожної
фази → щонайбільше V фаз. Кожне обчислення блокувального потоку
коштує O(VE) → загалом O(V² E).
На графах з одиничною пропускною здатністю (наприклад,
двочасткове паросполучення) Дініц працює за O(E √V) — значно
швидше.
Ще швидше (для довідки):
Push-relabel (Голдберг-Тарʼян, 1988): O(V² E) амортизовано, швидко на практиці
Push-relabel + highest-label + gap: O(V² √E)
Алгоритм Орліна (2013): O(VE) — збігається з теоретичною нижньою межею
На практиці алгоритм Дініца (іноді званий алгоритмом Дінітца) — робочий кінь, що використовується у спортивному програмуванні та багатьох виробничих системах, бо поєднує сильну оцінку найгіршого випадку з відмінною реальною продуктивністю, особливо на графах з майже одиничною пропускною здатністю, що виникають у задачах паросполучення.
7. Двочасткове паросполучення через максимальний потік
Одна з найкорисніших редукцій в усій алгоритміці: максимальне двочасткове паросполучення — поєднання пар з двох неперетинних множин вершин (наприклад, працівників із роботами, студентів зі школами) так, щоб кожна пара відповідала дозволеним ребрам, а жодна вершина не використовувалась двічі — розв'язується безпосередньо через максимальний потік.
Редукція: двочасткове паросполучення → максимальний потік
Дано двочастковий граф із частинами L (ліва) і R (права):
1. Додати супер-джерело s, з'єднане з кожною вершиною в L,
пропускна здатність 1 на кожному ребрі.
2. Додати супер-стік t, з'єднаний з кожної вершини в R,
пропускна здатність 1 на кожному ребрі.
3. Кожне вихідне ребро (l, r) отримує пропускну здатність 1,
орієнтоване l → r.
Твердження: максимальний потік у цій мережі = розмір
максимального паросполучення.
Чому: усі пропускні здатності — 1, а потік цілочисельний
(теорема про цілочисельність — якщо всі пропускні здатності
цілі, існує максимальний потік, цілочисельний на кожному ребрі),
тому кожна одиниця потоку від s до t відповідає рівно одній
парі l→r, а збереження гарантує, що жодна вершина не
використовується двічі.
З алгоритмом Дініца це виконується за O(E √V) — цей окремий
випадок є не чим іншим, як знаменитим алгоритмом Хопкрофта-Карпа.
Теорема про цілочисельність: якщо кожна пропускна здатність у потоковій мережі — ціле число, існує максимальний потік, у якому потік на кожному окремому ребрі також ціле число. Саме це гарантує, що редукція до двочасткового паросполучення дійсно дає коректне 0/1-паросполучення, а не дробові пари — властивість, яка не виконується для загальних лінійних програм без додаткової структури.
8. Реальні застосування
Надійність мереж і планування пропускної здатності: провайдери інтернету моделюють магістральні канали як потокову мережу, щоб знайти максимальну стійку швидкість передачі даних між двома дата-центрами, а мінімальний розріз точно вказує, які фізичні канали є вузьким місцем, вартим модернізації.
Планування авіаперевезень і логістики: призначення літаків на маршрути або вантажівок на доставки часто моделюється як потокова задача з часово-розгорнутими мережами — вершини представляють пари (місце, час), а ребра — можливі переміщення.
Сегментація зображень (комп'ютерний зір): алгоритм мінімального розрізу / максимального потоку Бойкова-Колмогорова відокремлює передній план від фону, моделюючи пікселі як вузли графу з вагами ребер на основі схожості кольору — розв'язується як мінімальний розріз s-t.
Вибування у спортивних турнірах: визначення, чи може команда математично ще виграти лігу, — класична редукція до максимального потоку, де ігри, що залишились, — джерела, команди, яким потрібні перемоги, — стоки, і якщо максимальний потік насичує всі ребра джерела, команда ще не вибула.
Вибір проєктів і "вибування у бейсболі": вибір підмножини взаємозалежних проєктів, що максимізує прибуток за умов передумов, зводиться до обчислення мінімального розрізу на графі "вибору проєктів".
Циркуляція з нижніми межами: узагальнення максимального потоку, що вимагає мінімального потоку на деяких ребрах (не лише стелі пропускної здатності), моделює реальні ланцюги поставок, де певний трубопровід має нести щонайменше законтрактований мінімум — розв'язується розширеною формулою Форда-Фалкерсона.
Контекст складності: максимальний потік упевнено належить до класу P — розв'язується за поліноміальний час, а сучасні алгоритми (Орлін, 2013, і наближені майже лінійні методи на основі технік електричного потоку з 2013 року й далі) наближаються дедалі ближче до теоретичної нижньої межі O(VE). Саме ця розв'язуваність — причина того, чому стільки, здавалося б, непов'язаних комбінаторних задач — паросполучення, планування, сегментація, вибування — свідомо переформульовуються як потокові задачі: щойно виражена як потокова мережа, задача, що виглядає NP-важкою, часто стає розв'язуваною за поліноміальний час.