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

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

Після вступу США у Другу світову війну у 1941 році математик Джордж Бернард Данціг почав працювати у відділі статистичного управління Військово-повітряних сил США у Вашингтоні. З 1941 по 1946 роки він очолював підрозділ аналізу військових дій (Combat Analysis Branch), де працював над різноманітними математичними проблемами.^[1][2] Згодом з використанням роботи Данцига задача про максимальний потік була вперше розв'язана у ході підготовки повітряного мосту під час Берлінського повітряного мосту, що відбувався у 1948–1949 роках.^[3][4][5]

У 1951 році Джордж Данциг вперше сформулював задачу у загальному вигляді.^[6]

У 1955 році Лестер Форд^[en] і Делберт Фалкерсон^[en] вперше побудували алгоритм, призначений для вирішення цього завдання. Їх алгоритм отримав назву алгоритм Форда — Фалкерсона.^[7][8]

Надалі рішення задачі багато разів поліпшувалося.

У 2010 році дослідники Джонатан Келнер (Jonathan Kelner) і Олександр Мондри (Aleksander Mądry) з МТІ разом зі своїми колегами Даніелєм Спілманом з Єльського університету і Шень-Хуа Тенем^[en] з університету Південної Каліфорнії продемонстрували чергове покращення алгоритму, вперше за 10 років.^[3][9][10]

Розглянемо транспортну мережу ${\displaystyle \scriptstyle N=(V,E)}$ з джерелом ${\displaystyle \scriptstyle s\in V}$, стоком ${\displaystyle \scriptstyle t\in V}$ та пропускними здатностями ${\displaystyle \scriptstyle c}$.

Величиною потоку (value of flow) називається сума потоків з джерела ${\displaystyle \scriptstyle |f|=\sum _{v\in V}f_{sv}}$. У статті «Транспортна мережа» доведено, що вона дорівнює сумі потоків у сток ${\displaystyle \ \sum _{w\in V}f(w,t)}$.

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

В таблиці перераховано деякі алгоритми розв'язування задачі.

Метод	Складність	Опис
Лінійне програмування	Залежить від конкретного алгоритму. Для симплекс-методу експоненціальна.	Розглянемо задачу про максимальний потік як задачу лінійного програмування. Змінними є потоки по ребрах, а обмеженнями — збереження потоку й обмеження пропускної здатності.
Алгоритм Форда — Фалкерсона	Залежить від алгоритму пошуку шляху, що збільшується. Потребує O(max| f |) таких пошуків.	Знайти будь-який шлях, що збільшується. Збільшити потік по всіх його ребрах на мінімальну з їх залишкових пропускних здатностей. Повторювати, поки є шлях, що збільшується. Алгоритм працює тільки для цілих пропускних здатностей. В іншому випадку, він може працювати нескінченно довго, не сходячись до правильної відповіді.
Алгоритм Едмондса-Карпа	O(VE²)	Виконуємо алгоритм Форда — Фалкерсона, щоразу обираючи найкоротший шлях, що збільшується (знаходиться пошуком у ширину).
Алгоритм Дініца	O(V²E) ${\displaystyle \scriptscriptstyle O(V{\sqrt {E}})}$ для одиничних пропускних здатностей ${\displaystyle O(VE\log(V))}$ з використанням динамічних дерев Слетора і Тар'яна[11]	Удосконалення алгоритму Едмондса-Карпа (але хронологічно був знайдений раніше). На кожній ітерації, використовуючи пошук у ширину, визначаємо відстані від джерела до всіх вершин у залишковій мережі. Будуємо граф, який містить лише такі ребра залишкової мережі, на яких ця відстань зростає на 1. Виключаємо з графу усі тупикові вершини з інцидентними їм ребрами, поки всі вершини стануть не тупиковими. (Тупиковою називається вершина, в яку не входить і з якої не виходить жодне ребро, крім джерела і стоку.) На отриманому графі відшукуємо найкоротший шлях, що збільшується (їм буде будь-який шлях з s в t). Виключаємо із залишкової мережі ребро з мінімальною пропускною здатністю, знову виключаємо тупикові вершини, і так поки ще існують шляхи, що збільшуються.
Алгоритм просовування предпотоку[en]	O(V²E)	Замість потоку оперує з передпотоком. Різниця в тому, що для будь-якої вершини u, крім джерела і стоку, сума потоків, що входять до неї для потоку повинна бути строго нульовою (умова збереження потоку), а для передпотока — невід'ємною. Ця сума називається надмірним потоком у вершину, а вершина з позитивним надмірним потоком називається переповненою . Крім того, для кожної вершини алгоритм зберігає додаткову характеристику, висоту, яка є цілим невід'ємним числом. Алгоритм використовує дві операції: просування , коли потік по ребру, що йде з більш високої в нижчу вершину, збільшується на максимально можливу величину, і підйом , коли переповнена вершина, просування з якої неможливо через недостатню висоту, підіймається. Просування можливо, коли ребро належить залишковій мережі, коли воно веде з більш високої вершини в більш низьку, і вихідна вершина переповнена. Підйом можливий, коли вершина, що піднімається, переповнена, але жодна з вершин, в котру з неї ведуть ребра залишкової мережі, не нижче за неї. Він вчиняється до висоти на 1 більшою, ніж мінімальна з висот цих вершин. Спочатку висота джерела V, по всім ребрам, що виходять з джерела, тече максимально можливий потік, а решта висоти і потоки нульові. Операція просування і підйому виконуються до тих пір, поки це можливо.
Алгоритм «підняти на початок»[en]	O(V³) O(VE log(V²/E)) з використанням динамічних дерев	Варіант попереднього алгоритму, що спеціальним чином визначає порядок операцій просовування і підйому.
Алгоритм двійкового блокуючого потоку [1]	${\displaystyle \scriptscriptstyle O(E\min(V^{2/3},{\sqrt {E}})\log(V^{2}/E)\log {\max {|f|}})}$

Для детальнішого списку, див. ^[2].

Якщо пропускні спроможності цілі, максимальна величина потоку теж ціла.

Теорема випливає, наприклад, з теореми Форда — Фалкерсона.

Деякі узагальнення задачі про максимальний потік легко зводяться до вихідної задачі.

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

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

Кожне неорієнтоване ребро (u, v) замінюємо на пару орієнтованих ребер (u, v) і (v, u).

Кожну вершину v з обмеженою пропускною здатністю ${\displaystyle c_{v}}$ розщеплюємо на дві вершини v_in і v_out. Всі ребра, які до розщеплення входять до v, тепер входять в v_in. Всі ребра, які до розщеплення виходять з v, тепер виходять з v_out. Додаємо ребро (v_in,v_out) з пропускною здатністю ${\displaystyle c_{v}}$.

• Потокова мережа

• Schrijver, Alexander, «On the history of the transportation and maximum flow problems» [Архівовано 10 листопада 2014 у Wayback Machine.], Mathematical Programming 91 (2002) 437—445
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 26. Максимальний потік. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• ↑ Andrew V. Goldberg^[en] and S. Rao (1998). Beyond the flow decomposition barrier. J. Assoc. Comput. Mach. 45: 753—782. doi:10.1145/290179.290181.
• ↑ Andrew V. Goldberg^[en] and Robert E. Tarjan (1988). A new approach to the maximum-flow problem. Journal of the ACM. New York, New York, U.S.: ACM Press. 35 (4): 921—940. doi:10.1145/48014.61051. ISSN 0004-5411.
• ↑ Joseph Cheriyan and Kurt Mehlhorn (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters. 69 (5): 239—242. doi:10.1016/S0020-0190(99)00019-8.
• ↑ Daniel D. Sleator and Robert E. Tarjan (1983). A data structure for dynamic trees (PDF). Journal of Computer and System Sciences. 26 (3): 362—391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000. Архів оригіналу (PDF) за 14 травня 2015. Процитовано 18 травня 2015.
• ↑ Daniel D. Sleator and Robert E. Tarjan (1985). Self-adjusting binary search trees (PDF). Journal of the ACM. New York, New York, U.S.: ACM Press. 32 (3): 652—686. doi:10.1145/3828.3835. ISSN 0004-5411. Архів оригіналу (PDF) за 5 березня 2015. Процитовано 18 травня 2015.
• Eugene Lawler (2001). 4. Network Flows. Combinatorial Optimization: Networks and Matroids. Dover. с. 109—177. ISBN 0486414531.

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.