Алгоритм нахождения максимального потока. Максимальный поток
Пусть задан ориентированный граф G=
Обозначим через x(v) величину потока, движущегося по дуге v . Очевидно, что
0£ x(v) £ d(v) , vÎV . (6. 1)
В каждой вершине iÎE\{t,s} объем потока входящего равен объему потока выходящего, т.е. справедливо равенство
{x(v )|i Î V + (i)}= {x(v)| iÎ V - (i)}
{x(v)| iÎV + (i)} - {x(v)| iÎV - (i)}=0. (6.2)
Для вершины t
{x(v)| iÎV + (i)} -{x(v)¦ iÎV - (i)}=-Q, (6.3)
для вершины s
{x(v)| iÎ V + (i)} -{x(v)¦ i Î V - (i)}= Q. (6.4)
Величина Q является величиной потока, который выходит из вершины t и входит в вершину s .
Требуется определить
Q ® max (6.5)
при ограничениях (6.1-6.4).
Величины Q, x(v) , vÎV, удовлетворяющие ограничениям (6.1-6.4) будем называть потоком в сети, и если они максимизируют величину Q , то максимальным потоком. Нетрудно видеть, что значения Q=0, x(v)=0, vÎV , являются потоком в сети.
Задача (6.1-6.5) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.
Разобьем множество вершины Е на две непересекающиеся части Е1 и Е2 таким образом, чтобы tÎE1, sÎE2 . Разрезом V(E1,E2) , разделяющим t и s будем называть множество V(E1,E2)ÌV такое, что для каждой дуги v Î V(E1,E2) либо h1(v)ÎE1 и h2(v)ÎE2 , либо h1(v)ÎE2 и h2(v)ÎE1 .
Разобьем множество V(E1,E2) на две части V(E1,E2,+),V(E1,E2,-) следующим образом:
V(E1,E2,+)={vÎV(E1,E2)| h1(v)ÎE1 и h2(v)ÎE2}
V(E1,E2,-)= { vÎV(E1,E2)| h2(v)ÎE1 и h1(v)ÎE2}
Пропускной способностью разреза будем называть
Q(E1,E2) = {x(v)| vÎV(E1,E2,+)}-{x(v)| vÎV(E1,E2,-)}
Справедлива следующая
Теорема 1 . (О максимальном потоке и минимальном разрезе).
В любой сети величина максимального потока из источника t в сток s равна минимальной пропускной способности Q(E1,E2) среди всех разрезов V(E1,E2) , разделяющих вершины t и s .
Заметим, что в максимальном потоке
x(v)=d(v) , vÎV(E1,E2,+),
x(v)=0 , vÎV(E1,E2,-).
Пусть Q, x(v), vÎV, - некоторый поток в сети, последовательность
t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,
является цепью, соединяющих вершины t и s . Зададим на этой цепи направление движения от вершины t к s . Дуга v(j) из этой цепи называется прямой, если ее направление совпадает с направлением движения от t к s , и обратной в противном случае. Эту цепь будем называть путем увеличения потока , если для прямых дуг v цепи x(v) < d(v) и для обратных x(v) > 0 . По этой цепи можно пропустить дополнительный поток q из t к s величиной q = min (q1,q2), где q1=min (d(v) -x(v)) , минимум берется по всем прямым дугам цепи, q1=min (x(v)) , минимум берется по всем обратным дугам цепи.
Теорема 2 .
Поток Q, x(v) , vÎV , максимальный тогда и только тогда, когда не существует пути увеличения потока.
Предлагаемый алгоритм решения задачи о максимальном потоке в сети, основан на поиске пути увеличения потока из t в s , который в свою очередь основан на процессе расстановки пометок вершин. Будем говорить, что
вершина i помечена пометкой q(i)>0 , а также известна дуга прямая дуга v(i) , через которую поступил этот поток, либо помечена пометкой , если до нее дошел некоторый дополнительный поток величиной q(i)>0 , а также известна обратная дуга v(i) , через которую поступил этот поток;
вершина i просмотрена, если помечены все соседние с ней вершины.
Если помечена вершина s, то найден путь увеличения потока величиной q , который пропускается по этому пути. Для описания алгоритма нам понадобится также массив SPW , в который помещаются номера помеченных вершин в порядке их пометки. С1 - номер в массиве SPW просматриваемой вершины, С2 - номер последней помеченной вершины в этом массиве.
Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда-Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
- исток сети; - сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.
r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20
1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток - это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим 
и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.
4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим 
и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.
5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.
6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.
2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки (красные круги)
Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы - в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети 
Вычисление величины максимального потока
При планировании рационального распределения продукции в сети распределения необходимо согласовывать пропускную способность каналов с потребностями клиентов и с мощностью производственного предприятия. Данный класс задач решается методом нахождения максимального потока.
Рассмотрим сеть распределения (рис. 4.21), в которой выделены пункты 0 (вход, например, склад готовой продукции производителя) и п (выход, распределительные центры, склады оптовых и розничных организаций, потребитель) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij > 0, называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество материального потока, которое может проходить по соответствующей дуге в единицу времени.
Рис. 4.21.
Количество продукции, проходящее по дуге от i до j , будем называть потоком по дуге (i ,j ) и обозначать через . Очевидно, что
Если учесть, что весь материальный поток, вошедший в промежуточный пункт сети, должен полностью выйти из него, получим
Из естественного требования равенства потоков на входе и на выходе имеем
Величину Z назовем величиной потока в сети и поставим задачу максимизации Z при соблюдении обозначенных выше условий.
Поиск максимального потока сводится к поиску пропускной способности минимального разреза.
Рассмотрим универсальный алгоритм поиска в матричной форме.
Начальный этап алгоритма состоит в построении матрицы D 0, в которую заносятся значения пропускных способностей (для неориентированной дуги берем симметричные значения элементов матрицы ).
Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.
При поиске пути используем процесс отмечаний. Метим символом * нулевые строку и столбец матрицы (вход сети). В 0-й строке отыскиваем , метим соответствующие столбцы индексами
и переносим метки столбцов на строки. Затем берем ί-ю отмеченную строку, ищем в ней непомеченный столбец с , которому сопоставляем метки-индексы
Метки столбцов переносим на строки, и этот процесс продолжаем до тех пор, пока не будет отмечен п-й столбец.
Затем "обратным ходом" по индексам выясняем путь, приведший к η-й вершине, уменьшаем пропускные способности дуг пути (элементы матрицы) на V n и увеличиваем симметричные элементы на эту же величину.
Такая процедура продолжается до тех пор, пока отмечание n -й вершины не станет невозможным.
Максимальный поток может быть найден вычитанием из исходной матрицы D 0, получаемой после приведенной выше корректуры матрицы пропускных способностей:
Пример 4.4
Производство размещено в Москве. Для распределения продукции предприятие привлекает посредников, которые работают с предприятием через распределительные центры различных уровней. В европейской части России работает оптовое предприятие 1, обслуживаемое центральным распределительным центром. Оптовое предприятие 2 работает в ближайшем зарубежье (Украина, Белоруссия) и обслуживается региональным распределительным центром. Есть у предприятия на местном рынке (Москва и Московская область) свои клиенты – ритейлеры, которые получают продукцию с городского распределительного центра. Запасы регионального и городского распределительных центров пополняются с центрального распределительного центра.
Выделим фрагмент распределительной сети:
- склад готовой продукции производственного предприятия;
- центральный распределительный центр;
- региональный распределительный центр;
- городской распределительный центр;
- два оптовых предприятия;
- розничная точка, принадлежащая компании;
- потребители.
Рис. 4.22.
Каждое звено сети распределения обозначим цифрой, а над дугами проставим пропускную способность. Пропускная способность в зависимости от вида звена может быть выражена через объем производственной мощности, плановую потребность (спрос) потребителей и емкость рынка.
Граф сети распределения продукции представлен на рис. 4.23. Построим матрицу D 0, в которую занесем значения пропускных способностей звеньев распределительной сети (рис. 4.24).
Рис. 4.23.
Рис. 4.24.
Из нулевой строки отметим вершины (строки-столбцы) 1, 2 и 3 индексами μ = 0 и V, равными 30,10 и 10.
Из помеченной строки 1 отметим вершины 4 и 5 индексами μ = 1 и V4 = min (30,15) = 15, V5 = min (30,10) = 10.
Из строки 3 отметим вершину 6 и, наконец, из строки 4 – вершину 7 (рис. 4.25).
Рис. 4.25.
Обратным ходом по μ обнаруживаем путь: к вершине 7 от 4, к вершине 4 от 1, к вершине 1 от 0; корректируем элементы D 0 на величину потока V7 = 15.
Очередной шаг дает путь с потоком 5 (рис. 4.26).
Рис. 4.26.
Последующий шаг дает результат, представленный на рис. 4.27.
Рис. 4.27.
Дальнейшее отмечание невозможно. Отсюда получаем матрицу максимального потока (рис. 4.28).
Рис. 4.28.
В результате применения алгоритма нахождения максимального потока в сети получены результаты, представленные на рис. 4.29. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.
Добавим фиктивные исток и сток. От истока ко всем белым вершинам проведем ребра, весом в B (цена перекраски в черный). От черных вершин ко стоку проведем ребра, весом в W (цена перекраски в белый). И между всеми соседними вершинами (будь они одного или разных цветов) - ставим ребро весом в G (серая линия). Величина максимального потока будет ответом на задачу.
Источник: Всеукраинская школьная олимпиада по информатике, 2007, День 1
Решение
Все, что нам надо - это разделить каждую вершину на две, и между ними поставить ребро, весом в ограничение пропускной способности данной вершиныРешение
В классической задаче о минимальном разрезе удалять нужно ребра. Не проблема! Разобьем вершины на 2, и поставим между ними ребро, весом в 1. Тогда ответ к задаче - нахождение минимального разреза в графе (что и есть максимальным потоком).Источник: Харьковская зимняя школа по программированию, 2009, День 3
После перехода по автомату из i в j по ребру k, стираются все переходы из i по ребру k, а также все переходы в j по ребру k. Требуется вывести количество путей из A в B по такому автомату.
Решение
Задача сводится к нахождению максимального количества путей, причем из одной вершины не выходят более одного ребра одного цвета. Сведем задачу к нахождения максимального потока. Для каждой вершин создадим k+1 вершину в перестроенной сети. Первая вершина будет входом, остальные вершины будут представлять цвета. Из вершины входа проведем по ребру пропускной способностью 1 в каждую из k вершин, соответствующих цвету. Из вершины соответствующих цвету i проведем все ребра цвета i во входы концов ребер. Найдя максимальный поток в такой сети, получим максимальное количество путей удовлетворяющих требуемому свойству.Решение
Построим сеть. Создадим для каждого типа монет по одной вершине. Эти вершины будут соответствовать Вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности 1 в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у Вас.Для каждого члена клуба (кроме 1, тоесть Вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать
не более k-1 монеты, которых у него k (k > 1). Естественно, член клуба отдает одну монету взамен одной полученной.
Таким образом, в каждую такую вершину нужно провести ребро пропускной способности 1 из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью k i - 1 в вершину i, соответствующую монетам, которых у члена клуба больше одной.
Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны Вами.
Источник: Харьковская зимняя школа по программированию, 2009, День 4
Дано описание системы охлаждения. Нужно выяснить, каким образом можно пустить жидкость по трубам, чтобы выполнялись все указанные условия.
