Как найти потоки в сети

Методы применения алгоритма нахождения максимального потока в сети

Введение

Задача о максимальном потоке является классической и имеет множество применений. Напомню постановку проблемы. Дан взвешенный ориентированный граф с неотрицательными весами (пропускными способностями). Выделены две вершины: исток S и сток T такие, что любая другая вершина лежит на пути из S в T. Потоком назовем функцию F: V x V с такими свойствами

1. Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.
2. Антисимметричность. Для каждого ребра (u, v): F(u, v) = -F(v, u).
3. Сохранение потока. Для каждой вершины (кроме S и T), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного). Тоесть, алгебраическая сумма потоков для каждой вершины (кроме S и T) равна нулю.

В этом посте вы можете ознакомиться с реализацией поставленной проблемы.

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

Задачи

1. Задача о максимальном паросочетании. На вход дается N — количество мальчиков, M — количество девочек и список, какой мальчик с какой из девочек хочет танцевать (таких может быть несколько). Надо определить максимальное количество одновременно танцующих пар.
   

   Решение

   Для решения этой задачи можно использовать алгоритм Куна, но раз уж мы взялись сводить все к потоку — давайте это сделаем. Для этого не хватает истока и стока. Давайте их добавим! «Слева» добавим фиктивную вершину и проведем ребра ко всем мальчикам весом в 1. От мальчиков к девочкам уже есть ребра проставим им тоже цену 1. И от девочек ребра к стоку тоже ценой 1. Ответом к задаче является величина максимального потока между истоком и стоком.

2. Испорченный паркет. У паркета NxM, некоторые клетки могут быть испорчены. Их необходимо закрыть новыми плитками. Плитки бывают размером 2х1 (можно поворачивать, но нельзя разрезать) ценой А, и 1х1 ценой B. Спрашивается, какую минимальную сумму нужно потратить, что бы заложить испорченные плитки паркета. Естественно, новые плитки не должны перекрывать никакие другие плитки.
   

   Решение

   Для начала, убедимся, что 2*B>A. Иначе, все выгодней замостить только плитками 1х1 и больше нечего считать. Далее наша задача максимизировать количество плиток ценой А.
   Раскрасим наш паркет по принципу шахматной доски. Очевидно, что тогда один конец плитки 2х1 будет лежать на черной клетке, другой — на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая — черные. Ребра весом в 1 проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в бесконечность (довольно распространенный прием) и сток с ребрами из черных клеток весом тоже в бесконечность. Пускай f — величина найденного максимального потока между истоком и стоком. Тоесть мы нашли количество плиток 2х1. Ответом к задаче будет величина f*A+(K-f)*B, где K — общее количество испорченных клеток.
   Источник: Харьковская зимняя школа по программированию, 2009, День 3

3. Задача живопись. Дана матрица N*M с клетками, покрашенными либо в черный, либо в белый цвета. W — цена перекраски черного квадрата в белый, B — белого в черный. После перекраски, между всеми соседними квадратами разных цветов нужно провести серую линию, ценой G. Надо так отпимально перекрасить матрицу (или ничего не делать), что бы потратить минимальную сумму.
   

   Решение

   Крайний случай: если матрица вся одного цвета — ответ 0.
   Добавим фиктивные исток и сток. От истока ко всем белым вершинам проведем ребра, весом в B (цена перекраски в черный). От черных вершин ко стоку проведем ребра, весом в W (цена перекраски в белый). И между всеми соседними вершинами (будь они одного или разных цветов) — ставим ребро весом в G (серая линия). Величина максимального потока будет ответом на задачу.
   Источник: Всеукраинская школьная олимпиада по информатике, 2007, День 1

4. Задача с ограничением на вершины. Пусть надо найти величину максимального потока и на вершины наложено ограничение, сколько они могут пропустить.
   

   Решение

   Все, что нам надо — это разделить каждую вершину на две, и между ними поставить ребро, весом в ограничение пропускной способности данной вершины

5. Минимальный разрез. Дан граф. Сколько вершин надо удалить, что бы не существовало пути из A в B?
   

   Решение

   В классической задаче о минимальном разрезе удалять нужно ребра. Не проблема! Разобьем вершины на 2, и поставим между ними ребро, весом в 1. Тогда ответ к задаче — нахождение минимального разреза в графе (что и есть максимальным потоком).
   Источник: Харьковская зимняя школа по программированию, 2009, День 3

6. Сочинитель стихов. Имеется детерминированный конечный автомат с одним начальным состоянием A и одним конечным B. Каждый переход задается тройкой чисел (i, j, k), переход из состояния i в состояние j по ребру k.
   После перехода по автомату из i в j по ребру k, стираются все переходы из i по ребру k, а также все переходы в j по ребру k. Требуется вывести количество путей из A в B по такому автомату.

   Решение

   Задача сводится к нахождению максимального количества путей, причем из одной вершины не выходят более одного ребра одного цвета. Сведем задачу к нахождения максимального потока. Для каждой вершин создадим k+1 вершину в перестроенной сети. Первая вершина будет входом, остальные вершины будут представлять цвета. Из вершины входа проведем по ребру пропускной способностью 1 в каждую из k вершин, соответствующих цвету. Из вершины соответствующих цвету i проведем все ребра цвета i во входы концов ребер. Найдя максимальный поток в такой сети, получим максимальное количество путей удовлетворяющих требуемому свойству.
   Источник: Харьковская зимняя школа по программированию, 2009, День 4

7. Коллекционирование монет. Есть n коллекционеров и m видов монет. Для вступления в клуб, необходимо иметь не меньше одной монеты каждого типа. Вы (у Вас номер 1) можете меняться с коллекционерами имеющимися монетами. Любой коллекционер обменяет монету свою монету a на Вашу монету b, если у него больше одной монеты типа a и нету ни одной монеты типа b. Вы, в свою очередь, можете нарушать это правило. Нужно набрать как можно больше типов монет по известной ситуации у всех коллекционеров.
   

   Решение

   Построим сеть. Создадим для каждого типа монет по одной вершине. Эти вершины будут соответствовать Вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности 1 в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у Вас.
   Для каждого члена клуба (кроме 1, тоесть Вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать
   не более k-1 монеты, которых у него k (k > 1). Естественно, член клуба отдает одну монету взамен одной полученной.
   Таким образом, в каждую такую вершину нужно провести ребро пропускной способности 1 из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью k_i — 1 в вершину i, соответствующую монетам, которых у члена клуба больше одной.
   Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны Вами.
   Источник: Харьковская зимняя школа по программированию, 2009, День 4

8. Циркуляция. Система охлаждения реактора представляет собой набор труб, соединяющих узлы. По трубам течет жидкость, причем для каждой трубы строго определено направление, в котором она должна по ней течь. Узлы системы охлаждения занумерованы от 1 до N. Система охлаждения должна быть спроектирована таким образом, чтобы для каждого узла за единицу времени количество жидкости, втекающей в узел, было равно количеству жидкости, вытекающей из узла. У каждой трубы имеется пропускная способность c_ij. Кроме того, для обеспечения достаточного охлаждения требуется, чтобы по трубе протекало не менее l_ij единиц жидкости за единицу времени. То есть для трубы, ведущей из i-го узла в j-ый должно выполняться l_ij ≤ f_ij ≤ c_ij.
   Дано описание системы охлаждения. Нужно выяснить, каким образом можно пустить жидкость по трубам, чтобы выполнялись все указанные условия.

   Решение

   Это задача на нахождение циркуляции в сети с заданными нижними ограничениями на ребра. Если по ребру (u, v) должен проходить поток в отрезке [l, r], то в перестроенной сети будет три ребра (откуда, куда, вес): (u, v, r — l), (S, v, l), (u, T, l). S, T — дополнительно введенные сток и исток соответственно. Фактически мы пропускаем по ребру необходимый минимальный поток, после чего балансируем его так, чтобы получить циркуляцию.
   Источник: Харьковская зимняя школа по программированию, 2009, День 4

9. Снова танцы. На вечеринку приглашены n мальчиков и n девочек. Они хотят станцевать несколько раундов.
   В каждом раунде гости делятся на n танцующих пар. Каждый гость должен быть в некоторой паре, каждая пара должна состоять из одного мальчика и одной девочки. В каждом раунде каждый мальчик должен танцевать с другой девочкой. Некоторые мальчики и девочки не нравятся друг другу. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Аналогично каждая девочка может танцевать не более чем с k мальчиками, которые ей не нравятся.
   Имеется информация о том, нравятся ли друг другу i-ый мальчик и j-ая девочка (1 ≤ i, j ≤ n). Найти наибольшее количество раундов, которое можно станцевать на вечеринке.

   Решение

   Рассмотрим следующую задачу: могут ли танцы продолжаться в точности m раундов? Если мы сможем ответить на этот вопрос, то бинарным поиском найдем наибольшее m, для которого проведение танцев возможно.
   Построим граф, имеющий один исток и один сток (черные вершины). Красные вершины представляют мальчиков, серые – девочек. Если мальчик и девочка нравятся друг другу, то проведем между ними ребро единичной пропускной способности (на рисунке такими являются два ребра – верхнее и нижнее). Иначе добавим синие и зеленые вершины как показано на рисунке и установим пропускную способность ребер между соответствующими синими и зелеными вершинами равную 1.
   Синие и зеленые вершины образуют “защитный” уровень. Связь мальчиков с девочками, которые друг другу не нравятся, будет проходить по ребрам защитного уровня. Каждый мальчик может танцевать не более чем с k девочками, которые ему не нравятся. Установим пропускную способность ребер между красными и синими, зелеными и серыми вершинами равную k. Таким образом, между каждым мальчиком и каждой девочкой будет установлена связь через ребро либо напрямую, либо через вершины защитного уровня.
   Танцы должны продолжаться в точности m раундов. Установим пропускную способность ребер между истоком и красными вершинами, а также между серыми вершинами и стоком равную m.
   
   Находим максимальный поток в графе. Танцы могут продолжаться в точности m раундов тогда и только тогда, когда величина максимального потока будет равна n * m, где n – количество мальчиков.
   Источник: Севастопольская летняя школа по программированию, 2010, День 4

Заключение

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

Если на сети сформирован некоторый
поток, то для ответа на вопрос: будет ли
он максимальным, используют теорему
Форда-Фалкерсона.

Теорема 12.1. (Теорема Форда-Фалкерсона)

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

.

Алгоритм нахождения максимального потока на сети.

Этап 1. Насыщение потока.

Шаг 1. Сформировать произвольный
начальный поток.

Шаг 2. Найти оставшиеся возможные
пути из истока

в сток
,
имеющие только ненасыщенные дуги. Если
такой путь найден, то переходим к шагу
3. Если путь не найден, то переходим к
шагу 4.

Шаг 3. Увеличить поток по
найденному пути таким образом, чтобы
одна из дуг стала насыщенной.

Шаг 4. Получившийся поток насыщен.

Этап 2. Пометка вершин сети.
(Перераспределение потока.)

Шаг 5. Вершину

пометить «».

Шаг 6. Пусть

– любая из уже помеченных вершин;

– некоторая непомеченная вершина,
смежная с вершиной
.
Вершину

помечаем
,
если данные вершины соединены ненасыщенной
дугой
,
и помечаем
,
если соединены непустой дугой
.

После пометки вершин возможны два
случая: вершина

оказалась либо помеченной (шаг 7), либо
непомеченной (шаг 8).

Шаг 7. Вершина

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

к
.
В этой последовательности каждая
последующая вершина помечена буквой
предыдущей вершины. На дугах
последовательности определяем новый
поток. Увеличиваем на

единиц поток на дугах, имеющих направление
от

к

и уменьшаем на

единиц поток на дугах, имеющих обратное
направление. Число

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

единиц в вершину
.
Далее вновь переходим к пометке вершин
(шаг 5).

Этап 3. Определение максимального
потока.

Шаг 8. Вершина

осталась непомеченной. Пусть

– множество всех помеченных вершин,

– множество всех непомеченных вершин.
Тогда дуги, связывающие два подмножества
вершин

и
,
определяют разрез
.
Таким образом, найден поток

и разрез
,
для которого выполняется условие
.

Пример 2.
На сети из примера 1. сформировать
максимальный по величине поток,
направленный из истока

в сток
.
Выписать ребра, образующие на сети
разрез минимальной пропускной способности.

Решение. Этап 1.

Шаг 1. Воспользуемся тем, что в
примере 12.1. был уже сформирован некоторый
поток на сети.

Шаг 2. Путь

содержит насыщенную дугу
.
Больше нельзя добавить потока по этому
пути. Пути
,

и

содержат насыщенные дуги.

Но путь

имеет две дуги, которые еще ненасыщенные.

Шаг 3. Увеличиваем поток по
найденному пути:
.
Значит, на этом пути поток увеличиваем
на 1 единицу, и тем самым дуга

стала насыщенной.

Шаг 4. Таким образом, получаем
насыщенный поток, поскольку каждый
рассмотренный путь содержит хотя бы
одну насыщенную дугу.

Этап 2.

Выясним, является ли построенный поток
максимальным по величине. Строим сеть,
на которой отметим все вершины и
ненасыщенные дуги. На этой сети разность
пропускных способностей дуги и проходящего
по ней потока обозначим числом в
квадратных скобках.

Шаг 5, 6. Вершину

пометить
.
На шаге 6 предусматривается пометка
вершин, смежных с вершиной I,
соединенных ненасыщенными дугами. Но
на построенной сети таких вершин нет.

В результате вершина S
оказалась непомеченной.

Этап 3. Шаг 8. Так как
вершина S непомеченная,
то поток, сформированный на сети,
получился максимальным.

Строим разрез на сети. Разбиваем множество
вершин на два подмножества: A
и B. Так как только
одна вершина оказалась помеченной, то
множество A состоит
из одной вершины I, а
остальные образуют множество B:

.

Проводим разрез
,
который состоит из дуг

и
:

.

Определяем величину максимального
потока
:

(ед.) 

Пример 3.
На заданной сети в скобках указаны
пропускные способности дуг. Требуется
сформировать на сети максимальный
поток, направленный из истока

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

Решение. Этап 1.

Сформируем на сети какой-либо начальный
поток. Рассмотрим путь
.
Поскольку
,
по этому пути пропускаем поток в 2
единицы. На сети значение потока обозначим
числами без скобок. По пути

пропускаем поток в 4 единицы, так как
.
По пути

пропускаем поток в 3 единицы, так как
.
Таким образом, начальный поток имеет
вид:

,

,

.

Объём перевозки 2+4+3=9 ед.

Каждый из рассмотренных путей содержит
насыщенную дугу, поэтому эти пути
насыщенные. На сети есть еще пути, которые
содержат ненасыщенные дуги, а именно:
,

и
.
Для первого пути дополнительно увеличим
поток на 2 единицы, так как
.
Второй и третий пути содержат одну и ту
же дугу

с минимальной для них оставшейся
разностью
.
Поэтому для увеличения потока на 1
единицу выберем, например, путь
.

Теперь каждый из этих путей содержит
насыщенную дугу, следовательно, полученный
поток – насыщенный (объём 12 ед.).

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

Видим, что на сети исток I
и сток S связаны дугами.
Значит, можно добавить какое-то количество
потока по ненасыщенным дугам, при этом
придется перераспределить поток.

Этап 2.

На построенной
сети помечаем вершины. Вершину

пометим
.
Смежную ей вершину

помечаем
,
так как эти вершины соединяет ненасыщенная
дуга
.
Вершину

помечаем
,
так как вершины

и

соединяет ненасыщенная дуга
.
Вершину

помечаем
,
так как вершины

и

соединяет непустая дуга
.
Вершины

и

помечаем
,
так как они соединены с вершиной

ненасыщенными дугами

и
.
Вершина

смежная вершине
,
и эти вершины соединены ненасыщенной
дугой
,
поэтому вершину

помечаем
.
Вершина

смежная вершине
,
и эти вершины соединены ненасыщенной
дугой
,
поэтому вершину

помечаем
.

Вершина

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

к
:
.
В этой последовательности каждая
последующая вершина помечена буквой
предыдущей вершины. Перераспределим
поток на этом пути.

Определим число
:
 =
min{[3=7-4], [1=3-2], 3, 1, [3=6-3]}=
.
Увеличиваем на 1 единицу поток на дугах,
имеющих направление от

к
:
,
,
,
.
Уменьшаем на 1 единицу поток на дугах,
имеющих обратное направление:
.

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

Проверим, будет ли построенный поток
максимальным. Изобразим сеть, на которой
отметим все вершины и ненасыщенные
дуги, как сделали выше.

Вновь помечаем вершины. Вершину

пометим
.
Смежную ей вершину

помечаем
,
так как эти вершины соединяет ненасыщенная
дуга
.
Все остальные вершины, в том числе и
вершина
,
остаются непомеченными. Значит, поток
на сети максимальный.

Этап 3.

Как видно на
последней сети исток

и сток

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

Строим разрез на
сети. Разбиваем множество вершин на два
подмножества: A
и B.
Помеченные вершины образуют множество
,
непомеченные – множество
.

Проводим
разрез
,
который состоит из дуг
,
,
,
:

.

Определяем величину
максимального потока
:

(ед.)

Соседние файлы в папке Лекции_2

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Сведения к вычислению максимального потока

В этом разделе мы рассмотрим ряд задач, сводящихся к задаче вычислении максимального потока, и покажем, что алгоритмы из разделов 22.2 и 22.3 важны в более широком контексте. Мы можем снимать различные ограничения на сети и решать другие сетевые задачи, мы можем решать другие задачи обработки сетей и графов, и мы можем решать задачи, которые не относятся к сетевым. В этом разделе будут рассмотрены примеры такого использования — вычисление максимального потока в качестве общей модели решения задачи.

Мы также изучим взаимосвязь между вычислением максимального потока и более сложными задачами, чтобы сформировать контекст для рассмотрения этих задач в дальнейшем. В частности, задача о максимальном потоке представляет собой специальный случай задачи отыскания потока минимальной стоимости, о которой пойдет речь в разделах 22.5 и 22.6. Кроме того, мы покажем, как формулировать задачи вычисления максимального потока в виде задач линейного программирования, которые мы будем рассматривать в части 8. Задача отыскания потока минимальной стоимости и линейное программирование представляют собой более общие модели решения задач, чем модель максимального потока. И хотя обычно решение задач о максимальном потоке с помощью специальных алгоритмов, описанных в разделах 22.2 и 22.3, менее трудоемко, чем с помощью алгоритмов для решения более общих задач, важно знать о взаимосвязи между моделями решения задач при переходе к более сложным моделям.

Мы будем употреблять термин стандартная задача о максимальном потоке (standard maxflow problem) для версии задачи, которую мы изучали до сих пор (максимальный поток в st-сетях с ограниченной пропускной способностью ребер). Этот термин будет применяться исключительно для облегчения ссылок в данном разделе. Вначале мы рассмотрим сведения, на примере которых убедимся, что ограничения в стандартной задаче о максимальном потоке несущественны, т.к. к стандартной задаче сводятся или эквивалентны несколько других задач о потоках. Любую из эквивалентных задач можно принять в качестве » стандартной » задачи. Простым примером такой задачи, который уже упоминался как следствие из леммы 22.1, является задача отыскания циркуляции в сетях, позволяющая получить максимальный поток в заданном ребре. Затем мы рассмотрим другие способы постановки задачи, в каждом случае отмечая их связь со стандартной задачей.

Максимальный поток в сетях общего вида. Нужно найти поток в сети, который максимизирует суммарный отток из ее истоков (и, следовательно, приток в ее стоки). По соглашению, в сети, в которой нет истоков и/или стоков, поток считается нулевым.

В верхней сети имеются три истока (0, 1 и 2) и два стока (5 и 6). Чтобы найти поток, который максимизирует суммарный поток из истоков и в стоки, мы вычисляем максимальный поток в st-сети, представленной внизу. Это копия исходной сети, в которую добавлены исток 7 и сток 8. Из вершины 7 в каждый исходный исток проводим ребро, пропускная способность которого равна суммарной пропускной способности ребер, исходящих из этого истока. А в вершину 8 ведут ребра из каждого исходного стока сети, пропускная способность которых равна суммарной пропускной способности ребер, входящих в стоки исходной сети.

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

Чтобы решить задачу вычисления максимального потока в сети, показанной вверху, и чтобы поток через каждую вершину не превосходил пропускной способности, заданной в массиве capV, индексированном именами вершин, мы строим стандартную сеть, показанную внизу. Для каждого ребра u-v соединяем новую вершину u* (где u* означает v+V) с каждой вершиной u, добавляем ребро, пропускная способность которого равна пропускной способности вершины u, и включаем ребро u*-v. Пары u-u* обведены овалами. Любой поток в нижней сети непосредственно соответствует потоку в верхней сети, который удовлетворяет ограничениям на пропускные способности вершин.

Допуская наличие нескольких стоков и истоков или накладывая ограничения на пропускные способности, мы вроде бы обобщаем задачу о максимальном потоке; однако смысл лемм 22.14 и 22.15 в том, что эти задачи нисколько не сложнее стандартной задачи. Теперь рассмотрим версию задачи, которая поначалу кажется более легкой для решения.

Ациклические сети. Нужно найти максимальный поток в ациклической сети. Осложняет ли наличие циклов в транспортной сети задачу вычисления максимального потока?

Мы уже сталкивались со многими примерами задач обработки орграфов, которые существенно усложняются при наличии в орграфах циклов. Пожалуй, самый наглядный из них — задача вычисления кратчайших путей во взвешенных орграфах, когда веса ребер могут принимать отрицательные значения (см.
«Кратчайшие пути»
) — которая легко решается за линейное время при отсутствии циклов и NP-трудна, если циклы допускаются. Как ни странно, задача о максимальном потоке в ациклических сетях не становится проще.

Каждая вершина u верхней сети соответствует двум вершинам u и u* (где u* означает u+V) нижней сети, а каждое ребро u-v верхней сети соответствует ребру u-v* нижней сети. Кроме того, в нижней сети имеются ребра u-u* без пропускных способностей, источник s с ребрами, ведущими в каждую вершину, не отмеченную звездочкой, и сток t, в который ведут ребра из каждой вершины, помеченной звездочкой. Серые и белые вершины (и ребра, соединяющие серые вершины с белыми) иллюстрируют прямую взаимосвязь сечений в обеих сетях (см. текст).

В результате такого сведения мы получаем не только ациклическую сеть, но и простую двудольную структуру. Данное сведение означает, что эти сети с более простой структурой при желании можно принять в качестве стандартных вместо сетей общего вида. Может показаться, что такая специальная структура позволяет создать более быстрые алгоритмы вычисления максимального потока. Однако описанное сведение показывает, что любой алгоритм, разработанный для таких специальных ациклических сетей, можно использовать для решения задач о максимальном потоке в сетях общего вида ценой небольших дополнительных затрат. Вообще-то классические алгоритмы вычисления максимального потока используют гибкость общей сетевой модели: оба рассмотренных нами подхода — алгоритм расширения путей и проталкивания напора — используют концепцию остаточной сети, предусматривающий добавление циклов в сеть. Когда приходится решать задачу о максимальном потоке в ациклической сети, для ее решения обычно используется стандартный алгоритм, ориентированный на сети общего вида.

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

Максимальный поток в неориентированных сетях. Неориентированная транспортная сеть — это взвешенный граф с целочисленными весами ребер, которые интерпретируются как пропускные способности. Циркуляция в таких сетях — это назначение весов и

направлений ребрам, которое удовлетворяет условию: поток в каждом ребре не превышает его пропускную способность, а суммарный поток в каждую вершину равен суммарному потоку из этой вершины. Задача о неориентированном максимальном потоке (
рис.
22.34) состоит в том, чтобы найти циркуляцию, которая максимизирует поток в заданном направлении в заданном ребре (т.е. из некоторой заданной вершины s в другую заданную вершину t). Пожалуй, эта задача более естественно, чем стандартная задача, соответствует модели трубопровода для перекачки жидкостей: она позволяет протекать жидкости по трубам в обоих направлениях.

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

Это доказательство не утверждает, что задача о максимальном потоке в неориентированной сети эквивалентна стандартной задаче. То есть не исключено, что вычисление максимальных потоков в неориентированных сетях может иметь меньшую трудоемкость, чем вычисление максимальных потоков в стандартных сетях (см. упражнение 22.81).

Итак, мы можем обрабатывать сети с несколькими стоками и истоками, неориентированные сети, сети с ограниченными пропускными способностями вершин и многие другие виды сетей (см., например, упражнение 22.79), используя алгоритмы вычисления максимального потока для st-сетей, рассмотренные в двух предыдущих разделах. Более того, лемма 22.16 утверждает, что все эти задачи можно решить даже при помощи алгоритма, который работает только на ациклических сетях.

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

Допустимый поток. Предположим, что каждой вершине транспортной сети присвоен вес, который можно рассматривать как предложение (если он положителен) или как спрос (если отрицателен), а сумма весов всех вершин сети равна нулю. Будем считать поток допустимым (feasible), если разность между притоком и оттоком каждой вершины равна весу этой вершины (предложению, если разность положительна, и спросу, если отрицательна). Пусть дана такая сеть, и нужно определить, возможны ли допустимые потоки. На рис. 22.35
рис.
22.35 приведен пример задачи о допустимом потоке.

Вершины с предложением соответствуют складам в задаче о распределении товаров, вершины со спросом соответствуют розничным торговым точкам, а ребра соответствуют дорогам на маршрутах грузоперевозок. Задача о допустимом потоке отвечает на следующий основной вопрос: можно ли найти такой способ доставки товаров, при котором везде предложение соответствует спросу.

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

Разработка классов, которые реализуют сведения рассмотренного выше вида, может оказаться сложной задачей для программистов — главным образом потому, что обрабатываемые объекты представлены сложными структурами данных. Нужно ли строить новую сеть, чтобы свести еще одну задачу к стандартной задаче о максимальном потоке? Некоторые из задач требуют для своего решения дополнительных данных — таких как пропускные способности вершин или предложение или спрос — поэтому построение стандартной сети без этих данных может оказаться оправданным. Использование указателей на ребра играет здесь важную роль: если скопировать ребра сети, а затем вычислить максимальный поток, то что потом делать с результатом? Перенос вычисленного потока (вес каждого ребра) из одной сети в другую, когда обе сети представлены списками смежности — отнюдь не тривиальное действие. Когда используются указатели на ребра, новая сеть содержит копии указателей, а не ребер, что позволяет переслать значения потоков непосредственно в сеть клиента. Программа 22.6 представляет собой реализацию, которая демонстрирует некоторые из этих моментов в классе для решения задач поиска подходящего потока с помощью сведения согласно лемме 22.16.

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

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

Все задачи, рассмотренные в данном разделе, имеют одну и ту же цель (вычисление потоков в транспортной сети), поэтому не удивительно, что мы можем решать их с помощью модели, предназначенной для решения задач транспортной сети. Как утверждает теорема о максимальном потоке и минимальном сечении, алгоритмы вычисления максимального потока позволяют решать задачи обработки графов, которые с виду имеют мало общего с потоками. Теперь мы обратимся к примерам такого рода.

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

Для краткости мы будем далее называть эту задачу просто задачей двудольного сопоставления (bipartite matching), кроме случаев, в которых нужно отличить ее от других подобных задач. Она формализует задачу трудоустройства, которая была упомянута в начале данной главы. Вершины соответствуют соискателям и работодателям, а ребра — отношению » взаимной заинтересованности в трудоустройстве». Решение задачи двудольного сопоставления приводит к максимально возможному трудоустройству. На
рис.
22.37 показан двудольный граф, моделирующий задачу с
рис.
22.3.

Без графов очень трудно искать прямое решение задачи о двудольном сопоставлении. Например, эта задача сводится к следующей комбинаторной головоломке: » найти максимальное подмножество из множества пар целых чисел (взятых из непересекающихся множеств), чтобы ни в одной паре не было одинаковых чисел » . Пример, приведенный на
рис.
22.37, соответствует решению этой головоломки для пар 0-6, 0-7, 0-8, 1-6 и т.д. Эта задача на первый взгляд кажется простой, однако, как видно на примере задачи поиска гамильтонова пути из
«Виды графов и их свойства»
(и многих других задач), какой-либо примитивный систематический перебор пар до возникновения противоречия может потребовать экспоненциального времени. То есть существует слишком много подмножеств пар, чтобы можно было проверить все варианты; решение этой задачи должно быть достаточно разумным, чтобы использовать лишь немногие из них. Решение головоломок сопоставления вроде только что описанной или разработка алгоритмов, которые способны эффективно решать любую такую головоломку — очень непростые задачи, позволяющие продемонстрировать возможности и пользу модели сетевых потоков, которая предоставляет разумный способ построения двудольного сопоставления.

Программа 22.6. Решение задачи о допустимом потоке сведением к задаче о максимальном потоке

Данный класс решает задачу о допустимом потоке с помощью сведения ее к задаче о максимальном потоке, используя построение, представленное на
рис.
22.36. Конструктор принимает в качестве аргументов сеть и вектор sd, индексированный именами вершин. Если значение sd[i] положительно, то оно представляет предложение в вершине i, а если отрицательно, то спрос.

Как показано на
рис.
22.36, конструктор строит новый граф с теми же ребрами, но с двумя дополнительными вершинами s и t. Ребра из s ведут в узлы с предложением, а ребра из вершин со спросом ведут в вершину t. Затем он находит максимальный поток и проверяет, заполнены ли все дополнительные ребра до их пропускных способностей.

  #include "MAXFLOW.cc"
  template <class Graph, class Edge>
  class FEASIBLE
 { const Graph &G;
   void freeedges(const Graph &F, int v)
  { typename Graph::adjIterator A(F, v);
    for (EDGE* e = A.beg(); !A.end(); e = A.nxt())
   delete e;
  }
 public:
   FEASIBLE(const Graph &G, vector<int> sd) : G(G)
  { Graph F(G.V()+2);
    for (int v = 0; v < G.V(); v++)
   { typename Graph::adjIterator A(G, v);
     for (EDGE* e = A.beg(); !A.end(); e = A.nxt())
    F.insert(e);
   }
    int s = G.V(), t = G.V()+1;
    for (int i = 0; i < G.V(); i++)
   if (sd[i] >= 0)
     F.insert(new EDGE(s, i, sd[i]));
   else
     F.insert(new EDGE(i, t, -sd[i]));
    MAXFLOW<Graph, Edge>(F, s, t);
    freeedges(F, s); freeedges(F, t);
  }
 } ;
   

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

Например, на
рис.
22.38 алгоритм вычисления максимального потока с использованием расширяющих путей может использовать пути s-0-6-t, s-1-7-t, s-2-8-t, s-4-9-t, s-5-10-t и s-3-6-0-7-1-11-t для вычисления сопоставления 0-7, 1-11, 2-8, 3-6, 4-9 и 5-10. Следовательно, существует способ трудоустройства всех студентов в задаче, показанной на
рис.
22.3.

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

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

Пример №1. Лабиринт Минотавра

Сразу скажем, что выбраться за пределы поля эквивалентно тому, что Минотавр может дойти до какой-либо крайней клетки.

Решение и доказательство корректности

Переход к сети

Рассмотрим сеть, в которой вершинам будут соответствовать незакрашенные клетки поля, соседние незакрашенные клетки соединим ориентированными рёбрами с пропускной способностью . В качестве истока возьмём вершину, которой соответствует клетка Минотавр. Добавим в граф ещё одну вершину — сток, добавим рёбра из вершин, соответствующим крайним клеткам поля, в сток с пропускной способностью . Чтобы пути не пересекались по клеткам, раздвоим каждую вершину графа на вершины: в одну будут только входить рёбра, из другой — только выходить рёбра, и сами эти вершины соединим ребром с пропускной способностью .

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

Оценка времени работы

Время работы алгоритма Форда-Фалкерсона . Первое замечание: (это следует из того, что из каждой вершины исходит не более рёбер), т.е. . Второе замечание: ответ не превосходит , т.к. можно закрасить клетку слева, справа, сверху и снизу от позиции Минотавра и он не сможет никуда двигаться, поэтому можно считать константой. Итоговое время работы .

Пример №2. Испорченный паркет.

Решение

Сначала проверим, что . Если это условие не выполнено, то все выгодней замостить только плитками и больше нечего считать. Теперь на нужно максимизировать количество плиток ценой .
Раскрасим наш паркет по принципу шахматной доски, тогда один конец плитки будет лежать на черной клетке, другой – на белой. Итак, построим двудольный граф, одна доля которого будет содержать белые клетки, другая – черные. Ребра весом в проведем между граничащими клетками. Добавим исток с ребрами в белые вершины весом в 1 и сток с ребрами из черных клеток весом тоже в 1. Пускай – величина найденного максимального потока между истоком и стоком, это и будет количество плиток . Ответом к задаче будет величина , где – общее число испорченных клеток.

Доказательство корректности

Заметим следующее: мы ищем максимальное паросочетание в двудольном графе. Это означает, что белая вершина будет соединена не более чем с одной чёрной и наоборот – это именно то, что нам нужно, ведь соединяя чёрную клетку с белой, мы понимаем, что можем разместить здесь плитку размером и она не будет ни с чем пересекаться. Теперь мы ищем максимальное число таких рёбер. Это всё происходит также, как и в сведении задачи поиска максимального паросочетания к задаче о нахождении максимального потока.

Оценка времени работы

Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы , где – величина найденного максимального потока. Заметим, что , где – общее число испорченных клеток. Также заметим, что , т.к. рёбер исходят из истока и входят в сток и максимум ребра могут исходить из вершины в левой доле в правую. Из всего этого следует, что итоговое время работы будет

Пример №3. Коллекционер монет.

Решение

Построим сеть следующего вида: создадим для каждого типа монет по одной вершине, эти вершины будут соответствовать вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у вас. Для каждого члена клуба (кроме вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать не более монеты, которых у него . Естественно, член клуба отдает одну монету взамен одной полученной. Таким образом, в каждую такую вершину нужно провести ребро пропускной способности из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью в вершину , соответствующую монетам, которых у члена клуба больше одной. Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны вами.

Доказательство корректности

Как уже было сказано, построенная сеть отражает процессы обмена в клубе, пример можно посмотреть на картинке выше. Заметим следующее:

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

Всё вышесказанное подтверждает то, что построенная сеть корректно отображает процессы обмена монетами между участниками.

Оценка времени работы

Величину максимального потока можно искать с помощью алгоритма Форда-Фалкерсона, его время работы , где – величина найденного максимального потока. Заметим, что , где – количество типов монет. Также заметим, что , где – общее минимальное число монет, которые нужно получить все коллекционерам (кроме вас), чтобы вступить в клуб сумма типов монет, которых больше , по всем коллекционерам. Из всего этого следует, что итоговое время работы будет

См.также

• Схема алгоритма Диница
• Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину
• Алгоритм масштабирования потока

Источники информации

• The 2016 West Siberian Subregional Contest
• Зимняя школа по программированию, Харьков 2009
• Codeforces лекции Зимней Школы по Программированию