Добавим фиктивные исток и сток. От истока ко всем белым вершинам проведем ребра, весом в 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
Дано описание системы охлаждения. Нужно выяснить, каким образом можно пустить жидкость по трубам, чтобы выполнялись все указанные условия.
Решение
Это задача на нахождение циркуляции в сети с заданными нижними ограничениями на ребра. Если по ребру (u, v) должен проходить поток в отрезке , то в перестроенной сети будет три ребра (откуда, куда, вес): (u, v, r - l), (S, v, l), (u, T, l). S, T - дополнительно введенные сток и исток соответственно. Фактически мы пропускаем по ребру необходимый минимальный поток, после чего балансируем его так, чтобы получить циркуляцию.Идея этого алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.
Рассмотрим ребро (i, j) с (начальной) пропускной способностью. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись - остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.
Для произвольного узла j, получающего поток из узла i, определим метку, где - величина потока, протекающего от j узла к узлу i. Чтобы найти максимальный поток, выполняем следующие действия.
Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем =. Назначим и пометим узел 1 меткой. Полагаем i=1.
Множество узлов j, в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью >0 для всех j. Если, выполняем 3 этап, в противном случае переходим к 4.
В находим узел k, такой, что. Положим и пометим узел k меткой. Если k=n, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i=k и возвращаемся к 2 этапу.
Откат назад. Если i=1, сквозной путь не возможен, и переходим к 6. Если, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем его из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко 2 этапу.
Определение остаточной сети. Обозначим через множество узлов, через которые проходит p_й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n).тогда максимальный поток, проходящий по этому пути
Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину в направлении движения потока и увеличиваются на эту же величину в противоположном направлении.
Т.о. для ребра (i, j), входящего в сквозной путь, текущие остаточные пропускные способности изменяются:
1) , если поток идет от узла i к j,
2) , если поток идет от узла j к i.
а) при m найденных сквозных путях максимальный поток выражается
б) Имея значения начальных и конечных пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим. Если >0, поток, проходящий через ребро (i, j) равен. Если >0, тогда поток равен. (случай, когда одновременно >0 и >0, невозможен).
Пример 1. Найти максимальный поток в сети рис. 1
Итерация 1. =
3) k=3, так как. Назначаем и помечаем узел 3 меткой. i=3 и возвращаемся к 2)
5) k=5 и. Помечаем узел 5 меткой. Получаем сквозной путь.
6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: . и. Вычисляем остаточные пропускные способности вдоль пути:
Итерация 2.
1) и помечаем узел 1 меткой. i=1
2») (, поэтому узел 5 не включается в
3») k=4, и помечаем узел 4 меткой. i=4 и возвращаемся к 2)
2""") (так как узлы 1 и 3 помечены, они не включаются в)
3""") k=5 и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)
Итерация 3.
1) и помечаем узел 1 меткой. i=1
3) k=2, и помечаем узел 2 меткой. i=2 и возвращаемся к 2)
3") k=3 и. Помечаем узел 3 меткой. i=3 и возвращаемся к 2)
2») (так как) переходим к 4)
4) метка узла 3 показывает номер предшествующего узла. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. и возвращаемся к 2)
2""") (так как узел 3 удален из возможного сквозного пути)
3""") и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)
5) и. Вычисляем остаточные пропускные способности вдоль пути:
Итерация 4. на этой итерации получен путь с
Итерация 5. на этой итерации получен путь с
Итерация 6. новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к 6) для определения решения
6) максимальный объем потока в сети равен единиц.
Значения потоков по различным ребрам вычисляются путем вычитания последних значений остаточных пропускных способностей из первоначальных значений пропускных способностей.
Результаты вычислений: табл. 1
|
Величина потока |
направление |
||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(30,0) - (0,30)=(30, - 30) |
|||
|
(10,0) - (0,10)=(10, - 10) |
|||
|
(40,0) - (40,0)=(0,0) |
|||
|
(30,0) - (10,20)=(20, - 20) |
|||
|
(10,5) - (0,15)=(10, - 10) |
|||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(20,0) - (0,20)=(20, - 20) |
Графическое последовательное выполнение алгоритма нахождения максимального потока (пример 1)
д) е) Сквозных путей нет
Рис.
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).
Табл.2. Исходные данные к задаче о максимальном потоке
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)
Табл.3. Решение задачи о максимальном потоке
|
Пункт отправления |
Пункт назначения |
План перевозок |
Пропускная способность |
Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М. Согласно рис. 2 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM, а именно, Х 01, Х 02, Х 03, Х 12, Х 13, Х 14, Х 23, Х 24, Х 34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:
Х 01 + Х 02 + Х 03 = F (0)
Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)
Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)
Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)
Х 14 - Х 24 - Х 34 = - F (4)
Х КМ? 0, К, М = 0, 1, 2, 3, 4
Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) - это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).
При планировании рационального распределения продукции в сети распределения необходимо согласовывать пропускную способность каналов с потребностями клиентов и с мощностью производственного предприятия. Данный класс задач решается методом нахождения максимального потока.
Рассмотрим сеть распределения (рис. 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. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.
Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда-Фалкерсона, и построить разрез сети 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 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки (красные круги)
Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы - в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети 
Вычисление величины максимального потока
Сумма потоков через дуги, инцидентные v , равна сумме потоков через дуги, инцидентные w ; эта сумма называется величиной потока. Будем в первую очередь интересоваться потоками, имеющими наибольшую возможную величину, - так называемыми максимальными потоками. В общем случае сеть может иметь несколько различных максимальных потоков, однако их величины должны совпадать. (4)
Изучение максимальных потоков через сеть N = (V,D,a) тесно связано с понятием разреза, т.е. такого множества A дуг орграфа D, которое обладает тем свойством, что любая простая цепь из v в проходит через дугу, принадлежащую A. Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг. Разрезы, обладающие наименьшей возможной пропускной способностью, называются минимальными разрезами.
Величина любого потока не превышает пропускной способности любого разреза, и, следовательно, величина любого максимального потока не превышает пропускной способности любого минимального разреза. Однако сразу не ясно, что два последних числа всегда равны между собой; Этот результат был получен американскими математиками Фордом и Фалкерсоном в 1955 году и назван теоремой о максимальном потоке и минимальном разрезе.
Теорема (о максимальном потоке и минимальном разрезе) . Во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза.
Теорема о максимальном потоке и минимальном разрезе позволяет проверять, максимален данный поток или нет, но только для достаточно простых сетей. Разумеется, на практике приходится иметь дело с большими и сложными сетями, и в общем случае трудно найти максимальный поток простым подбором. Опишем один алгоритм нахождения максимального потока в любой сети с целочисленными пропускными способностями.
Шаг 1 . Сначала подберем поток, обладающий ненулевой величиной (если такой поток существует). Например, если N – сеть, представленная на рис. 29.3, то подходящим будет поток, изображенный на рис. 29.4. Стоит отметить, что чем больше величина выбранного нами начального потока , тем проще будут последующие шаги.
Шаг 2 . Исходя из N, строим новую сеть N’ путем изменения направления потока на противоположное. Более точно, любая дуга a, для которой(a) = 0, остается в N’ со своей первоначальной пропускной способностью, а любая дуга a, для которой , заменяется дугой a с пропускной способностью и противоположно направленной дугой с пропускной способностью (a). Сеть N’ в нашем примере показана на рис. 29.5. Вершина v уже не является источником,а – стоком.
Шаг 3 . Если в сети N’ мы сможем найти ненулевой поток из v в, то его можно добавить к первоначальному потокуи получить в N новый поток’большей величины. Теперь можно повторить шаг 2, используя при построении сети N’ новый поток’ вместо. Повторяя эту процедуру, мы в конце концов придем к сети N’ , не содержащей ненулевых потоков; тогда соответствующий потокбудет максимальным потоком. Например, на рис. 29.5 существует ненулевой поток, в котором потоки через дуги (v,u ), (u,z ), (z,x ), (x,y ) и (y, ) равны единице, а потоки через остальные дуги равны нулю. Добавляя этот поток к потоку на рис. 29.4, получим поток, изображенный на рис. 29.6; повторяя шаг 2, легко показать, что это и есть максимальный поток.
Используемая литература:
(1) http://pgap.chat.ru/zap/zap264.htm#0
(2) Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы матроиды, алгоритмы
(3) Басакер Р., Саати Т. Конечные графы и сети.
(4) Уилсон Р. Введение в теорию графов