LK / Лекция 13
Баранов Виктор Павлович. Дискретная математика. Раздел 3. Графы и сети.
Лекция 13. Потоки в сетях
Лекция 13. ПОТОКИ В СЕТЯХ
Задача о максимальном потоке.
Определение сети, потока и разреза.
Задача о максимальном потоке
Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины 
графа (источника) к некоторой конечной вершине 
(стоку). При этом каждой дуге 
графа 
приписана некоторая пропускная способность 
, и эта пропускная способность определяет наибольшее значение потока, который может протекать по данной дуге. Эта задача и ее варианты могут возникать во многих практических приложениях, например при определении максимальной интенсивности транспортного потока между двумя пунктами на карте дорог, представленной графом. В этом примере решение задачи о максимальном потоке укажет также ту часть сети дорог, которая «насыщена» и образует «узкое место» в отношении потока между двумя указанными концевыми пунктами.
Метод решения задачи о максимальном потоке (от 
к 
) предложен Фордом и Фалкерсоном, и их «техника пометок» составляет основу других алгоритмов решения многочисленных задач, являющимися простыми обобщениями или расширениями указанной задачи. Рассмотрим возможные варианты задачи о максимальном потоке.
Задача нахождения допустимого потока минимальной стоимости. Допустим, что каждой дуге графа приписана не только пропускная способность 
, дающая верхнюю границу потока через дугу 
, но также пропускная способность 
, дающая нижнюю границу потока через эту дугу. В общем случае может существовать много потоков, удовлетворяющим требованиям о максимальной и минимальной пропускных способностях дуг. Если в дополнение к пропускным способностям заданы также стоимости единицы потока, протекающего по дуге, то возникает задача нахождения допустимого потока минимальной стоимости.
Задача о многопродуктовом потоке. Эта задача возникает, если в сети имеется несколько источников и стоков, между которыми протекают потоки различных продуктов. В этой задаче пропускная способность 
является ограничением для суммы всех потоков всех видов продукции через эту дугу.
Задача о потоках с выигрышами. Во всех рассмотренных выше случаях неявно допускалось, что поток на входе дуги такой же, как и на выходе. Если рассмотреть граф, в котором выходной поток дуги равен ее входному потоку, умноженному на некоторое неотрицательное число, то задачу о максимальном потоке называют задачей о потоках с выигрышами. В такой задаче потоки могут «порождаться» и «поглощаться» самим графом, так что поток, входящий в 
, и поток, покидающий 
, могут изменяться совершенно независимо.
Определение сети, потока и разреза
Граф, некоторые вершины которого выделены, называется сетью. Выделенные вершины называются полюсами сети. Например, дерево с корнем можно рассматривать как однополюсную сеть.
Вершины, отличные от полюсов, называются внутренними вершинами сети. Ребро, инцидентное хотя бы одному полюсу, называется полюсным ребром. Остальные ребра называются внутренними.
-полюсником называется сеть с 
полюсами, разбитыми на два класса: 
входных и 
выходных полюсов. (1,1)-полюсник называется также двухполюсной сетью.
Далее будут рассматриваться только двухполюсные сети, которые будем называть просто сетями. Будем называть также цепью (без указания концов) элементарную цепь между полюсами сети. В противном случае будем указывать концы цепи и называть ее цепочкой.
Транспортной называется двухполюсная сеть, в которой каждой дуге 
приписано целое неотрицательное число 
, называемое пропускной способностью дуги.
Можно дать различные интерпретации транспортной сети. Пусть, например, в полюсе 
имеется неограниченный запас некоторого продукта и нужно организовать доставку этого продукта в полюс 
по сети путей сообщения с некоторыми промежуточными вершинами. В этом случае пропускная способность дуги – количество груза, которое можно перевезти в единицу времени по данной дуге. Тогда возникает задача: организовать перевозки по сети таким образом, чтобы, не превышая пропускных способностей дуг, перевозить из 
в 
максимальное количество груза в единицу времени.
Для каждой вершины 
сети 
обозначим через 
множество всех дуг, входящих в 
, а через 
– выходящих из 
. Для источника 
и стока 
имеем 
.
Потоком в сети 
называется целочисленная функция 
, определенная на дугах сети и удовлетворяющая условиям:
, 
; (1)
, (
, 
, 
). (2)
Второе условие называют уравнением сохранения. Оно представляет собой для каждой внутренней вершины сети закон Кирхгофа, согласно которому сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины.
На рис. 1 приведен пример сети 
, в которой каждой дуге 
приписана двойка 
.
8,8 7,6
2,2 2,0
9,7
Рис. 1. Пример транспортной сети
Если сложить уравнения сохранения для всех вершин, то останутся только члены, соответствующие дугам 
и 
:
.
Таким образом, для любого потока величина груза, выходящего из источника 
равна величине груза, прибывающего в сток 
. Эту величину обозначают 
и называют величиной потока:
.
Поток в сети, имеющий наибольшую величину, называется максимальным.
Основная задача состоит в нахождении максимального потока для данной транспортной сети. Для ее решения используют специальные подмножества дуг сети, называемые разрезами или сечениями.
Разрезом сети называется множество ребер, при удалении которого сеть становится несвязной, причем полюсы попадают в разные компоненты связности. Очевидно, что любая цепь проходит через одно ребро разреза.
Пусть 
– некоторое подмножество вершин сети, для которого полюс 
, а другой полюс 
. Обозначим 
– дополнение множества 
до множества 
. Тогда 
, а 
. Множество дуг сети, имеющих начало в 
, а конец в 
, называется разрезом, порождаемым множеством вершин 
, и обозначается 
. Например, для сети на рис. 1 выберем 
. Тогда 
. Имеем разрез
.
Ребро разреза называется прямым, если оно ориентировано слева направо, и обратным – в противном случае. Сумма пропускных способностей всех прямых дуг разреза называется пропускной способностью разреза и обозначается 
. Разрезы, которые обладают наименьшей возможной пропускной способностью, называются минимальными.
Теорема Форда-Фалкерсона
В 1955 г. Форд и Фалкерсон доказали следующую теорему о максимальном потоке и минимальном разрезе.
Теорема. Максимальная величина потока 
в сети равна пропускной способности 
любого минимального разреза.
Доказательство. Докажем сначала, что величина любого потока не превосходит пропускной способности любого разреза:
. Просуммируем уравнения сохранения (2) по всем вершинам 
. Получим
, (3)
где значения коэффициентов 
зависят от расположения концов дуги 
относительно множеств 
и 
. На рис. 2 показаны шесть возможных вариантов такого расположения.
2
3
5 1
6 4
Рис. 2. Возможные расположения концов произвольной дуги 
1. 
. В этом случае 
в ходит в складываемые уравнения дважды: со знаком ”+” для вершины 
и со знаком ”–” для вершины 
. Следовательно, 
.
2. 
. В этом случае 
в ходит только в уравнение сохранения для вершины 
, поэтому 
.
3. 
. В этом случае 
в ходит только в уравнение сохранения для вершины 
, поэтому 
.
4. 
. В этом случае 
, т. к. 
нет в складываемых уравнениях.
5. 
. Результат аналогичен п. 3.
6. 
. Результат аналогичен п. 4.
Для дуг шестого типа в сумму (3) добавим и вычтем 
. Тогда 
для дуг, выходящих из источника (
), и дуг, идущих против разреза 
; 
для дуг разреза 
; 
для остальных дуг.
Перепишем уравнение (3) в виде
,
откуда для любого потока и любого разреза
. (4)
Отсюда следует, что максимальное значение потока в сети равно минимальному значению пропускных способностей разрезов этой сети:
.
Алгоритм Форда-Фалкерсона
Привет, Хабр!
В свободное от учебы время пишу статьи, которых мне не хватало несколько лет назад.
При решении задачи о максимальном потоке я столкнулся с тем, что во всех мне известных источниках было дано формальное описание самих алгоритмов, что очень сильно затрудняло понимание изложенного материала. И в этой статье я попробую на базовом уровне разобрать Алгоритм Форда-Фалкерсона на конкретном примере, чтобы после прочтения данной статьи, вы хотя бы понимали основную суть самого алгоритма.
Постановка задачи
Имеется следующий ориентированный граф, в котором вес ребра обозначает пропускную способность между вершинами. Нужно найти максимальный поток, который можно пропустить из истокав сток.
Исходный граф
Как работает сам алгоритм?
Следует понимать остаточную сеть как тот же граф, который имеется на входе, но в этом случае мы будем производить над ним некоторые операции:
Отправлять определенное количество потока из текущей вершины в соседние.
Возвращать определенное количество потока из соседних вершин в текущую.
В начальный момент времени поток, который мы хотим провести через нашу сеть, должен быть равен нулю. Остаточная сеть совпадает с исходной сетью.
Находим любой путь из истока в сток в остаточной сети. Если путь не находим, утверждается, что поток является максимальным.
Пускаем через найденный путь поток равный минимальному весу ребра, которое входит в множество рёбер найденного пути.
Из веса рёбер на этом пути высчитываем размер потока, который мы пустили.
А к весу обратных рёбер (будем считать, что они существуют в остаточной сети и равны 0) прибавляем размер потока. Другими словами, на предыдущем шаге мы отправили некоторое количество потока из текущей вершины в следующую, а теперь при желании можем вернуть это же количество потока обратно в текущую.
Возвращаемся обратно к нахождению пути в остаточной сети после модификации.
Разбор конкретного примера
Разобьем одну итерацию проведения потока по выбранному пути на маленькие шаги, чтобы визуально стало понятно, как меняется остаточная сеть после проталкивания очередного потока.
Допустим наш алгоритм нашел следующий путь из вершинывнашей остаточной сети, которая на момент начала, совпадает с исходным графом.
Сколько потока можем провести по этому пути.
— Больше 2 ед. мы никак не сможем пустить, пропускаем наш поток по этим рёбрам из истока в сток.
Получаем следующее:
Рёбра с нулевым весом можно удалять. Таким образом, на первой итерации мы смогли увеличить максимальный поток на 2 ед.
Теперь дело за малым, остается всего лишь итерироваться до тех пор, пока существует путь из в .
Допустим, на 2-ой итерации мы нашли такой путь в нашей остаточной сети:
Пропускаем 3 ед . потока по этому пути, и перестраиваем остаточную сеть.
Получаем следующее:
На 3-ей итерации нашли такой путь в нашей модифицированной остаточной сети:
Пускаем 1 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
На 4-ой итерации находим следующий путь в остаточной сети:
Пускаем 4 ед. потока по этому пути и перестраиваем нашу остаточную сеть.
Получим следующую картину:
Итоговая остаточная сеть
На этом этапе наш алгоритм прекратит выполнение из-за того, что пути из истока в сток не существует. И ответом к поставленной задаче будет служить сумма потоков всех найденных увеличивающихся путей.
Ответ: 10 ед.
Спасибо большое за внимание, надеюсь, был полезен!
Буду рад любым отзывам или поправкам для повышения доступности изложения материала!
Name already in use
alg-ds-snippets / max-flow.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Максимальный поток в сети
Как и большинство других алгоритмов нахождения максимального потока, алгоритм Форда-Фалкерсона работает на остаточной сети, построенной на основе исходного графа. Сам алгоритм заключается в нахождении раз за разом (увеличивающего) пути от источника к стоку и проталкивании максимального потока по этому пути с ограничением на пропускную способность ребер. Как только путь от источника к стоку перестает существовать, алгоритм завершается.
Запишем все вышесказанное в виде кода, где неуточненные места вынесены в функции, с которыми мы будем разбираться позднее. Итак, наше решение заключено в функцию max_flow , которая принимает две вершины s (источник) и t (сток). Очевидно, что если источник и сток совпадают, то алгоритм можно не запускать. Сам алгоритм работает на уже построенной остаточной сети и описан в функции ford_fulkerson . В ней мы в цикле пытаемся построить какой-нибудь путь от вершины s . Если при этом вершина t даже не была посещена, то пути не существует, и алгоритм завершится. Если же вершина t была посещена, то путь от s к t существует, и мы его восстанавливаем. Затем мы находим максимальную величину потока, который еще можно протолкнуть по найденному пути, и увеличиваем поток на эту величину по всем ребрам пути.
При эффективной реализации на списках смежности и с целочисленными пропускными способностями алгоритм может достигать времени работы O((n + m)f) , где f — величина максимального потока. Каждый найденный путь увеличивает поток хотя бы на 1 , а поиск пути может быть выполнен за O(m) . Обнуление массивов pred и visited выполняется за O(n) на каждой итерации.
Некоторые части алгоритма мы вынесли в отдельные функции. Теперь пора их реализовать.
Начнем с поиска пути. Воспользуемся для этого поиском в глубину, при этом будем запоминать ребро, по которому мы пришли в вершину, в массиве pred и помечать посещенные вершины в массиве visited . Одним отличием от обычного поиска в глубину является то, что мы не можем перейти по ребру, если оно заблокировано потоком (по ребру пущен поток величиной равной пропускной способности ребра).
Так как мы работаем не с исходным графом, а с остаточной сетью, то введем дополнительные функции для работы с ней: edges (получение исходящих ребер в остаточной сети), target (получение конечной вершины дуги), available (вычисление доступной пропускной способности).
Следующим этапом является восстановление пути по массиву pred . Начиная со стока t , будем по ребрам перемещаться все ближе к источнику s . В этой цепочке вершин s — единственная вершина, у которой нет ребра, по которому в нее пришли, так как с нее был начат обход. Именно по этому критерию мы завершим восстановление пути.
Введем еще одну функцию для работы с остаточной сетью source , которая возвращает начальную вершину дуги.
Максимальная величина потока, который можно протолкнуть по найденному пути, равна наименьшей остаточной пропускной способности среди ребер этого пути, поэтому пройдем по всем ребрам пути и найдем минимум. Воспользуемся фактом, что путь содержит хотя бы одно ребро (следует из условия, что s != t ), взяв за базовое значение остаточную пропускную способность первого ребра в пути.
Эта функция может быть также упрощена до одной строчки:
Проталкивание потока вдоль пути заключается увеличении потока вдоль каждого из ребер пути на указанную величину. Для этого введем функцию push , которая увеличивает поток вдоль одного ребра.
Возможная реализация остаточной сети
Остались не описаны следующие функции:
- build_network для построения остаточной сети на основе исходного графа
- source для получения начальной вершины ребра в остаточной сети
- target для получения конечной вершины ребра в остаточной сети
- available для получения остаточной пропускной способности ребра
- flow для получения величины потока, пропущенного по ребру
- edges для получения исходящих из вершины ребер в остаточной сети
- push для увеличения потока вдоль ребра в остаточной сети
Существуют разные подходы к предоставлению подобного интерфейса, и основная проблема при этом заключается в том, что в остаточной сети все ребра дублируются и изменение одного ребра влечет за собой изменение и второго ребра. При этом находить второе ребро нужно быстро и желательно за константное время. Мы разберем один из подходов при организации остаточной сети на списках смежности.
Для начала определим структуру ребра. Ребро характеризуется начальной и конечной вершинами, пропускной способностью и потоком, пропущенным по этому ребру.
Каждому ребру (v, cu, u) в графе ставится в соответствие два ребра в остаточной сети: (v, cu, u) и (u, 0, v) . При этом изначально по ним пропущен поток величины 0 . Будем хранить ребра остаточной сети в виде списка, причем каждая пара ребер будет занимать позиции 2i и 2i + 1 . Таким образом, по четности индекса легко определить индекс обратного ребра. Более того, эту операцию легко выразить через ^ 1 ( xor 1 ), так как (2i) ^ 1 = 2i + 1 и, соответственно, (2i + 1) ^ 1 = 2i .
Саму остаточную сеть будем, как и исходный граф, представлять в виде списков смежности, но с одним отличием: вместо пары (пропускная способность, вершина) будем хранить индекс ребра в списке ребер.
Таким образом, достаточно легко реализовать работающие за константу недостающие функции.
При увеличении потока по ребру в остаточной сети необходимо уменьшить поток в обратном ребре на ту же величину.
Исходя из кода можно заметить, что для любого ребра (прямого или обратного) всегда выполняется соотношение flow <= capacity . По прямым рёбрам течёт неотрицательный поток, по обратным — неположительный. Сумма потока по прямому и обратному ребру всегда равна нулю.
Предыдущий алгоритм не ограничивал выбор алгоритма для поиска увеличивающего пути. Алгоритм Эдмондса-Карпа, в свою очередь, предлагает использовать поиск в ширину, чтобы увеличивающий путь был всегда кратчайшим. Таким образом, необходимо изменить лишь одну функцию:
Сам каркас алгоритма при этом останется неизменным.
Каждая итерация алгоритма выполняется за O(n + m) . Каждый следующий найденный данным алгоритмом увеличивающий путь будет не короче предыдущего. При нахождении увеличивающего пути хотя бы одно ребро блокируется потоком и может стать вновь доступно лишь при проталкивании потока по обратному ребру, что может случиться лишь при более длинном увеличивающем пути. Так как увеличивающий путь кратчайший, его длина не превосходит n — 1 . Таким образом, число итераций составляет O(nm) . Получаем время работы алгоритма O((n+m)nm) .
Максимальный поток минимальной стоимости
В этой задаче ребрам графа ставится в соответствие не только пропускная способность, но и удельная стоимость потока (неотрицательная). Соответственно, наша цель найти такой поток среди максимальных потоков в этом графе, что его стоимость минимальна. При этом стоимость потока рассчитывается как сумма по всем ребрам произведений удельной стоимости потока ребра на величину потока в ребре (учитываются лишь ребра исходного графа).
Добавим удельную стоимость к представлению ребра, а также определим новую функцию cost к нашей абстракции, которая возвращает удельную стоимость для переданного ребра:
В связи с этим достроим нашу остаточную сеть, чтобы она поддерживала также удельные стоимости, при этом удельная стоимость для обратного ребра будет равна удельной стоимости усходного ребра со знаком минуса. Будем считать, что списки смежности g содержат тройки (пропускная способность, удельная стоимость, вершина) .
Существует несколько алгоритмов нахождения максимального потока минимальной стоимости. Мы рассмотрим два из них.
Строим сразу поток минимальной стоимости
Первый подход заключается в изначальном построении потока минимальной стоимости, с постепенным увеличением его величины, пока не получим максимальный поток. При этом на каждой итерации мы получаем поток минимальной стоимости для данной величины. Этот алгоритм называется алгоритмом Басакера-Гоуэна, и его тоже можно рассматривать как некоторую модификацию алгоритма Форда-Фалкерсона. Отличие опять же заключается в поиске увеличивающего пути. Алгоритм предлагает искать кратчайшие по удельной стоимости пути в остаточной сети.
Приведем сначала каркас алгоритма. Заметим, что теперь мы считаем не только величину потока, но и его стоимость. Также мы ввели новую функцию path_cost , которая вычисляет удельную стоимость потока для найденного пути.
Функция path_cost достаточно проста и очевидна, так что начнем с нее. Удельной стоимостью потока для пути является сумма удельных стоимостей ребер, входящих в этот путь.
Теперь вернемся к функции find_path . Как уже говорилось, мы должны огранизовать поиск кратчайшего по удельной стоимости пути. Так как обратные ребра имеют отрицательную стоимость, то мы можем использовать алгоритм Форда-Беллмана. Так как на каждом этапе мы находим поток наименьшей стоимости, то отрицательных циклов в остаточной сети не имеется, и алгоритм отработает корректно. Также нельзя забывать про то, что ребро в сети должно обрабатываться только при условии, если его остаточная пропускная способность положительна.
Так как Форд-Беллман работает со списком ребер, то добавим функцию его получения к абстракции:
Уменьшаем стоимость потока
Еще один подход заключается в построении любого максимального потока с дальнейшим уменьшением его стоимости. Первая часть выполняется любым из алгоритмов нахождения максимального потока, например алгоритмом Эдмондса-Карпа. Во второй части мы добавляем в сеть удельные стоимости. Если поток не обладает минимальной стоимостью, то в остаточной сети существуют отрицательные по удельной стоимости циклы. Соответственно, алгоритм заключается в нахождении и устранении отрицательных циклов в сети.
Сначала представим каркас нашего алгоритма:
Начнем с простой функции flow_cost , которая посчитает стоимость потока в сети. Напомним, что она равна сумме произведений удельных стоимостей ребер на велечину потока в них. При этом считать необходимо только ребра из исходного графа. Но при этом, эта же величина для обратных ребер будет одинакова за счет зеркальности величины потока и удельной стоимости, поэтому можно посчитать значение для всех ребер остаточной сети и разделить на два.
Теперь перейдем к функции remove_cycles . В ней мы будем в цикле искать отрицательные циклы, пропускать по ним поток, устраняя их и тем самым уменьшая стоимость потока. Как только отрицательный цикл не найден, алгоритм можно завершать. Также нельзя начинать поиск цикла из вершины s , так как в остаточной сети, по которой уже пропущен максимальный поток, некоторые вершины и, соответственно, циклы могут быть недостижимы из вершины s . Поэтому начнем алгоритм «одновременно» из всех вершин сети, присвоив им значение 0 в массиве dist (при этом физический смысл значений в массиве теряется).
Находить цикл отрицательной стоимости будем с помощью алгоритма Форда-Беллмана. Если на последней итерации алгоритма была найдена вершина, для которой проведена релаксация, то эта вершина достижима из искомого цикла, и именно ее мы вернем.
Теперь, когда у нас есть вершина u , достижимая из цикла, мы можем добраться до вершины v , принадлежащей циклу, следуя по массиву pred . Так как на n-й итерации алгоритма Форда-Беллмана мы построили кратчайшие пути длины не более n , то достаточно пройти назад по ребрам n раз, чтобы гарантированно попасть в цикл. Затем, начиная от вершины v , мы можем восстановить все ребра цикла, следуя по массиву pred , пока вновь не встретим вершину v .
Задача о максимальном потоке
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.
Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.
Содержание
История
После вступления США во Вторую мировую войну в 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]
Определение
Дана транспортная сеть 
с источником 
, стоком 
и пропускными способностями 
.
Величиной потока (value of flow) называется сумма потоков из источника 
с использованием динамических деревьев Слетора и Тарьяна [11]
O(VE log(V²/E)) с использованием динамических деревьев
Sata raid ahci что это за драйвер