Что такое максимальный поток в графе

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

Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.

При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.

Постановка задачи

Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.

Исходный граф

Исходный граф

Как работает сам алгоритм?

Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:

Отправлять определенное количество потока из текущей вершины в соседние.

Возвращать определенное количество потока из соседних вершин в текущую.

В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.

Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.

Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.

Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.

А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.

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

Разбор конкретного примера

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

Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.

Сколько потока можем провести по этому пути.
— Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:

Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.

Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .

Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:

Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:

На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:

Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

На 4-ой итерации находим следующий путь в остаточной сети:

Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:

Итоговая остаточная сеть

Итоговая остаточная сеть

На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.

Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!

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

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

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

Содержание

История

После вступления США во Вторую мировую войну в 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]

Определение

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

Величиной потока (value of flow) называется сумма потоков из источника \scriptstyle |f| = \sum_<v \in V>f_<sv>» width=»» height=»» />. В статье «Транспортная сеть» доказано, что она равна сумме потоков в сток <img decoding=с использованием динамических деревьев Слетора и Тарьяна [11]

Усовершенствование алгоритма Эдмондса-Карпа (но хронологически был найден раньше). На каждой итерации, используя поиск в ширину, определяем расстояния от источника до всех вершин в остаточной сети. Строим граф, содержащий только такие рёбра остаточной сети, на которых это расстояние растёт на 1. Исключаем из графа все тупиковые вершины с инцидентными им рёбрами, пока все вершины не станут нетупиковыми. (Тупиковой называется вершина, кроме источника и стока, в которую не входит ни одно ребро или из которой не исходит ни одного ребра.) На получившемся графе отыскиваем кратчайший увеличивающий путь (им будет любой путь из s в t). Исключаем из остаточной сети ребро с минимальной пропускной способностью, снова исключаем тупиковые вершины, и так пока увеличивающий путь есть. Алгоритм проталкивания предпотока O(V²E) Вместо потока оперирует с предпотоком. Отличие в том, что для любой вершины u, кроме источника и стока, сумма входящих в неё потоков для потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной. Эта сумма называется избыточным потоком в вершину, а вершина с положительным избыточным потоком называется переполненной. Кроме того, для каждой вершины алгоритм сохраняет дополнительную характеристику, высоту, являющуюся целым неотрицательным числом. Алгоритм использует две операции: проталкивание, когда поток по ребру, идущему из более высокой в более низкую вершину, увеличивается на максимально возможную величину, и подъём, когда переполненная вершина, проталкивание из которой невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно, когда ребро принадлежит остаточной сети, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен, когда поднимаемая вершина переполнена, но ни одна из вершин, в которые из неё ведут рёбра остаточной сети, не ниже её. Он совершается до высоты на 1 большей, чем минимальная из высот этих вершин. Изначально высота источника V, по всем рёбрам, исходящим из источника, течёт максимально возможный поток, а остальные высоты и потоки нулевые. Операци проталкивания и подъёма выполняются до тех пор, пока это возможно. Алгоритм «поднять в начало» O(V³)
O(VE log(V²/E)) с использованием динамических деревьев Вариант предыдущего алгоритма, специальным образом определяющий порядок операций проталкивания и подъёма. Алгоритм двоичного блокирующего потока * \scriptscriptstyle O(E\min(V^<2/3>,\sqrt<E>)\log(V^2/E)\log<\max<|f|>>)» width=»» height=»» /></td> </tr> </table> <h3>Теорема о целом потоке</h3> <p><b>Если пропускные способности целые, максимальная величина потока тоже целая.</b></p> <p>Теорема следует, например, из теоремы Форда—Фалкерсона.</p> <h3>Обобщения, сводящиеся к исходной задаче</h3> <p>Некоторые обобщения задачи о максимальном потоке легко сводятся к исходной задаче.</p> <h4>Произвольное число источников и/или стоков</h4> <p>Если источников больше одного, добавляем новую вершину S, которую делаем единственным источником. Добавляем рёбра с бесконечной пропускной способностью от S к каждому из старых источников.</p> <p>Аналогично, если стоков больше одного, добавляем новую вершину T, которую делаем единственным стоком. Добавляем рёбра с бесконечной пропускной способностью от каждого из старых стоков к T.</p> <h4>Неориентированные рёбра</h4> <p>Каждое неориентированное ребро (u, v) заменяем на пару ориентированных рёбер (u, v) и (v, u).</p> <h4>Ограничение пропускной способности вершин</h4> <p>Каждую вершину v с ограниченной пропускной способностью   alt=»c_v» width=»» height=»» />расщепляем на две вершины v<sub>in</sub> и v<sub>out</sub>. Все рёбра, до расщепления входящие в v, теперь входят в v<sub>in</sub>. Все рёбра, до расщепления исходящие из v, теперь исходят из v<sub>out</sub>. Добавляем ребро (v<sub>in</sub>,v<sub>out</sub>) с пропускной способностью   alt=»c_v» width=»» height=»» />.</p> <h3>См. также</h3> <h3>Примечания</h3> <ol> <li><b>↑</b><i>Джон Дж. О’Коннор</i> и <i>Эдмунд Ф. Робертсон</i>. George Dantzig  (англ.) в архиве MacTutor.</li> <li><b>↑</b> Cottle, Richard; Johnson, Ellis; Wets, Roger, «George B. Dantzig (1914—2005)», <i>Notices of the American Mathematical Society</i>, v.54, no.3, March 2007. Cf. p.348</li> <li>↑ <i><b>1</b></i><i><b>2</b></i> Hardesty, Larry, «First improvement of fundamental algorithm in 10 years», MIT News Office, September 27, 2010</li> <li><b>↑</b> Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas, «Alcuin’s Transportation Problems and Integer Programing», <i>Konrad-Zuse-Zentrum für Informationstechnik</i>, Berlin, Germany, November 1995. Cf. p.3</li> <li><b>↑</b> Powell, Stewart M., «The Berlin Airlift», <i>Air Force Magazine</i>, June 1998.</li> <li><b>↑</b> Dantzig, G.B., «Application of the Simplex Method to a Transportation Problem», in T.C. Koopman (ed.): <i>Activity Analysis and Production and Allocation</i>, New York, (1951) 359—373.</li> <li><b>↑</b> Ford, L.R., Jr.; Fulkerson, D.R., «Maximal Flow through a Network», <i>Canadian Journal of Mathematics</i> (1956), pp.399-404.</li> <li><b>↑</b> Ford, L.R., Jr.; Fulkerson, D.R., <i>Flows in Networks</i>, Princeton University Press (1962).</li> <li><b>↑</b> Kelner, Jonathan, «Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs», talk at CSAIL, MIT, Tuesday, September 28 2010</li> <li><b>↑</b>Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs, by Paul Cristiano et al., October 19, 2010.</li> <li><b>↑</b>Алгоритм Диница</li> </ol> <h3>Литература</h3> <ul> <li>Schrijver, Alexander, «On the history of the transportation and maximum flow problems», <i>Mathematical Programming</i> 91 (2002) 437—445</li> <li><i>Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К.</i> Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М .: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4 . Глава 26. Максимальный поток.</li> <li><b>↑</b>   Andrew V. Goldberg and S. Rao (1998). «Beyond the flow decomposition barrier». <i>J. Assoc. Comput. Mach.</i><b>45</b>: 753–782. DOI:10.1145/290179.290181.</li> <li><b>↑</b>   Andrew V. Goldberg and Robert E. Tarjan (1988). «A new approach to the maximum-flow problem». <i>Journal of the ACM</i> (ACM Press) <b>35</b> (4): 921–940. DOI:10.1145/48014.61051. ISSN0004-5411.</li> <li><b>↑</b>   Joseph Cheriyan and Kurt Mehlhorn (1999). «An analysis of the highest-level selection rule in the preflow-push max-flow algorithm». <i>Information Processing Letters</i><b>69</b> (5): 239–242. DOI:10.1016/S0020-0190(99)00019-8.</li> <li><b>↑</b>   Daniel D. Sleator and Robert E. Tarjan (1983). «A data structure for dynamic trees». <i>Journal of Computer and System Sciences</i><b>26</b> (3): 362–391. DOI:10.1016/0022-0000(83)90006-5. ISSN0022-0000.</li> <li><b>↑</b>   Daniel D. Sleator and Robert E. Tarjan (1985). «Self-adjusting binary search trees». <i>Journal of the ACM</i> (ACM Press) <b>32</b> (3): 652–686. DOI:10.1145/3828.3835. ISSN0004-5411.</li> <li><i>Eugene Lawler</i> 4. Network Flows // Combinatorial Optimization: Networks and Matroids. — Dover, 2001. — P. 109–177. — ISBN 0486414531</li> </ul> <ul> <li>Алгоритмы на графах</li> </ul> <p> <em>Wikimedia Foundation . 2010 .</em> </p> <h4>Полезное</h4> <h4>Смотреть что такое «Задача о максимальном потоке» в других словарях:</h4> <p><strong>Поток минимальной стоимости</strong> — Задача о потоке минимальной стоимости состоит в нахождении самого дешёвого способа передачи определённого количества потока через транспортную сеть. Содержание 1 Определения 2 Отношение к другим задачам … Википедия</p> <p><strong>ПОТОК В СЕТИ</strong> — функция, сопоставляющая дугам данной сети (ориентированного графа) нек рые числа. Каждое число интерпретируется как интенсивность потока нек рого груза по данной дуге. П. в с. являются удобной моделью при исследовании ряда проблем в транснорте,… … Математическая энциклопедия</p> <p><strong>Метод минимального элемента</strong> — Транспортная задача задача об оптимальном плане перевозок продукта ( ов) из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является… … Википедия</p> <p><strong>Метод наименьшего элемента</strong> — Транспортная задача задача об оптимальном плане перевозок продукта ( ов) из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является… … Википедия</p> <p><strong>Транспортная сеть</strong> — В теории графов транспортная сеть   ориентированный граф , в котором каждое ребро имеет неотрицательную пропускную способность и поток . Выделяются две вершины: источник и сток такие, что любая другая вершина сети лежит на пути из … Википедия</p> <p><strong>Boost</strong> — Тип библиотека (программирование) Написана на С++ Операционная система Кроссплатформенный Последняя версия Boost 1.52.0 (05.11.2012) … Википедия</p> <p><strong>Линейное программирование</strong> — Линейное программирование  математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование… … Википедия</p> <p><strong>ГРАФОВ ТЕОРИЯ</strong> — область дискретной математики, особенностью к рой является геометрич. подход к изучению объектов. Основной объект Г. т. граф и его обобщения. Первые задачи Г. т. были связаны с решением математических развлекательных задач и головоломок (задача о … Математическая энциклопедия</p> <p><strong>Дуайт Дэвид Эйзенхауэр</strong> — (Dwight David Eisenhower) Биография Дэвида Эйзенхауэра, карьера и достижения Биография Дэвида Эйзенхауэра, карьера и достижения, личная жизнь Содержание Содержание Определение Биография Первая мировая Военная карьера Вторая мировая война Оверлорд … Энциклопедия инвестора</p> <p><strong>Ту-4</strong> — (сер. № 2805103), построенный на Куйбышевском авиазаводе в 1952 году единственный сохранившийся Ту 4 в России. Музей ВВС, Монино. Тип тяжёлый бомбардировщ … Википедия</p>

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *