Задача о максимальном потоке

Максимальный поток в транспортной сети. Числа обозначают потоки и пропускные способности.

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

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

История

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

В 1951 году Джордж Данциг впервые сформулировал задачу в общем виде.^[6]

В 1955 году, Лестер Форд и Делберт Фалкерсон (англ. Delbert Ray Fulkerson) впервые построили алгоритм, специально предназначенный для решения этой задачи. Их алгоритм получил название алгоритм Форда-Фалкерсона.^[7][8]

В дальнейшем решение задачи много раз улучшалось.

В 2010 году исследователи Джонатан Кёлнер (Jonathan Kelner) и Александер Мондры (Aleksander Mądry) из МТИ вместе со своими коллегами Дэниелем Спилманом (en:Daniel Spielman) из Йельского университета и Шень-Хуа Тенем (en:Shang-Hua Teng) из Южно-Калифорнийского университета продемонстрировали очередное улучшение алгоритма, впервые за 10 лет.^[3][9][10]

Определение

Дана транспортная сеть ${\displaystyle N=(V,E)}$ с источником ${\displaystyle s\in V}$, стоком ${\displaystyle t\in V}$ и пропускными способностями ${\displaystyle c}$.

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

Задача о максимальном потоке заключается в нахождении такого потока, где величина потока максимальна.

Решения

Следующая таблица перечисляет некоторые алгоритмы решения задачи.

Метод	Сложность	Описание
Линейное программирование	Зависит от конкретного алгоритма. Для симплекс-метода экспоненциальна.	Представить задачу о максимальном потоке как задачу линейного программирования. Переменными являются потоки по рёбрам, а ограничениями — сохранение потока и ограничение пропускной способности.
Алгоритм Форда-Фалкерсона	Зависит от алгоритма поиска увеличивающего пути. Требует ${\displaystyle O(\max |f|)}$ таких поисков.	Найти любой увеличивающий путь. Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей. Повторять, пока увеличивающий путь есть. Алгоритм работает только для целых пропускных способностей. В противном случае он может работать бесконечно долго, не сходясь к правильному ответу.
Алгоритм Эдмондса-Карпа	${\displaystyle O(|V||E|^{2})}$	Выполняем алгоритм Форда-Фалкерсона, каждый раз выбирая кратчайший увеличивающий путь (находится поиском в ширину).
Алгоритм Диница	${\displaystyle O(|V|^{2}|E|)}$ или ${\displaystyle O(|V|\surd |E|)}$ для единичных пропускных способностей ${\displaystyle O(|V||E|\log(|V|))}$ с использованием динамических деревьев Слетора и Тарьяна[11]	Усовершенствование алгоритма Эдмондса-Карпа (но хронологически был найден раньше). На каждой итерации, используя поиск в ширину, определяем расстояния от источника до всех вершин в остаточной сети. Строим граф, содержащий только такие рёбра остаточной сети, на которых это расстояние растёт на 1. Исключаем из графа все тупиковые вершины с инцидентными им рёбрами, пока все вершины не станут нетупиковыми. (Тупиковой называется вершина, кроме источника и стока, в которую не входит ни одно ребро или из которой не исходит ни одного ребра.) На получившемся графе отыскиваем кратчайший увеличивающий путь (им будет любой путь из s в t). Исключаем из остаточной сети ребро с минимальной пропускной способностью, снова исключаем тупиковые вершины, и так пока увеличивающий путь есть.
Алгоритм проталкивания предпотока	${\displaystyle O(|V|^{2}|E|)}$	Вместо потока оперирует с предпотоком. Отличие в том, что для любой вершины u, кроме источника и стока, сумма входящих в неё потоков для потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной. Эта сумма называется избыточным потоком в вершину, а вершина с положительным избыточным потоком называется переполненной. Кроме того, для каждой вершины алгоритм сохраняет дополнительную характеристику, высоту, являющуюся целым неотрицательным числом. Алгоритм использует две операции: проталкивание, когда поток по ребру, идущему из более высокой в более низкую вершину, увеличивается на максимально возможную величину, и подъём, когда переполненная вершина, проталкивание из которой невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно, когда ребро принадлежит остаточной сети, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен, когда поднимаемая вершина переполнена, но ни одна из вершин, в которые из неё ведут рёбра остаточной сети, не ниже её. Он совершается до высоты на 1 большей, чем минимальная из высот этих вершин. Изначально высота источника V, по всем рёбрам, исходящим из источника, течёт максимально возможный поток, а остальные высоты и потоки нулевые. Операции проталкивания и подъёма выполняются до тех пор, пока это возможно.
Алгоритм «поднять в начало»	${\displaystyle O(|V|^{3})}$ или ${\displaystyle O(|V||E|\log(|V|^{2}/|E|))}$ с использованием динамических деревьев	Вариант предыдущего алгоритма, специальным образом определяющий порядок операций проталкивания и подъёма.
Алгоритм двоичного блокирующего потока [1]	${\displaystyle O(|E|\min\{|V|^{2/3},\surd {|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}}$.

Ограничение пропускной способности рёбер снизу

В данном варианте постановки задачи значение потока каждого ребра дополнительно ограничено снизу функцией ${\displaystyle c'\colon E\to \mathbb {N} ^{+}}$. Таким образом величина потока для любого ребра не может превысить его пропускную способность, но и не может быть меньше заданного минимума, т.е. ${\displaystyle c'(e)\leqslant f(e)\leqslant c(e)}$. Для решения задачи необходимо преобразовать исходную транспортную сеть ${\displaystyle G=(V,E,s,t,c,c')}$ в транспортную сеть ${\displaystyle G'=(V',E',s',t',c'')}$ следующим образом:

1. Добавь новые источник ${\displaystyle s'}$ и сток ${\displaystyle t'}$.
2. Для каждого ребра ${\displaystyle (v,w)}$:
   1. Создай две новые вершины ${\displaystyle x}$ и ${\displaystyle y}$.
   2. Установи ${\displaystyle c''(v,x)=c(v,w)}$ и ${\displaystyle c''(y,w)=c(v,w)}$.
   3. Установи ${\displaystyle c''(x,y)=c(v,w)-c'(v,w)}$.
   4. Установи ${\displaystyle c''(s',y)=c'(v,w)}$ и ${\displaystyle c''(x,t')=c'(v,w)}$.
3. Установи ${\displaystyle c''(t,t')=c''(s,s')=\sum _{e\in E}c(e)}$.

В ${\displaystyle G}$ определён поток, удовлетворяющий условию об ограничении пропускной способности ребёр снизу, тогда и только тогда, когда в ${\displaystyle G'}$ определен максимальный поток, в котором все рёбра вида ${\displaystyle (s',y)}$ и ${\displaystyle (x,t')}$ "насыщены". Благодаря такому построению алгоритм нахождения потока, ограниченного снизу будет следующим:

1. Из ${\displaystyle G}$ построй ${\displaystyle G'}$.
2. Найди поток ${\displaystyle f'}$ графа ${\displaystyle G'}$, предпочитая рёбра вида ${\displaystyle (s',y)}$ и ${\displaystyle (x,t')}$.
3. Если ${\displaystyle f'<f''+\sum _{e\in E(G)}c'(e)}$, где ${\displaystyle f''}$ - поток графа ${\displaystyle G}$, в котором опущена пропускная способность рёбер снизу, то решения не существует.
4. Иначе вычисли поток ${\displaystyle f}$ из потока ${\displaystyle f'}$, т.е. ${\displaystyle f(a,b)=f(a,x)}$.

Ограничение пропускной способности рёбер снизу с альтернативой

Такой вариант задачи идентичен предыдущему с той разницей, что значение потока для каждого ребра может быть также равно ${\displaystyle 0}$, т.е. ${\displaystyle c'(e)\leqslant f(e)\leqslant c(e)}$ или ${\displaystyle f(e)=0}$. Несмотря на незначительное изменение условия, не существует полиноминального решения данной проблемы, если классы P и NP не равны. В качестве доказательства утверждения можно привести полиноминальную редукцию к проблеме Exact-3-SAT.

См. также

• Поток минимальной стоимости
• Транспортная сеть

Примечания

1. Джон Дж. О’Коннор и Эдмунд Ф. Робертсон. George Dantzig (англ.) — биография в архиве MacTutor.
2. Cottle, Richard; Johnson, Ellis; Wets, Roger, «George B. Dantzig (1914—2005)» Архивная копия от 7 сентября 2015 на Wayback Machine, Notices of the American Mathematical Society, v.54, no.3, March 2007. Cf. p.348
3. Hardesty, Larry, «First improvement of fundamental algorithm in 10 years» Архивная копия от 28 марта 2014 на Wayback Machine, MIT News Office, September 27, 2010
4. Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas, «Alcuin’s Transportation Problems and Integer Programing» Архивная копия от 7 августа 2011 на Wayback Machine, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, Germany, November 1995. Cf. p.3
5. Powell, Stewart M., «The Berlin Airlift», Air Force Magazine, June 1998.
6. Dantzig, G.B., «Application of the Simplex Method to a Transportation Problem» Архивная копия от 19 июля 2010 на Wayback Machine, in T.C. Koopman (ed.): Activity Analysis and Production and Allocation, New York, (1951) 359—373.
7. Ford, L.R., Jr.; Fulkerson, D.R., «Maximal Flow through a Network», Canadian Journal of Mathematics (1956), pp.399-404.
8. Ford, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962).
9. Kelner, Jonathan, «Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs» Архивная копия от 24 июня 2011 на Wayback Machine, talk at CSAIL, MIT, Tuesday, September 28 2010
10. Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs Архивная копия от 29 ноября 2010 на Wayback Machine, by Paul Cristiano et al., October 19, 2010.
11. Алгоритм Диница  (неопр.). Дата обращения: 28 октября 2010. Архивировано 7 мая 2015 года.

Литература

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