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

Дуга сети называется ориентиро­ванной, если узлы, которые она соединяет, упорядочены — один из них принят за начальный, а другой за конечный. На рисунках и схемах ориентированная дуга обозначается стрел­кой, которая показывает, из какого узла выходит эта дуга и в какой узел входит (рис. 20). Сеть называется ориентированной, если ориентированы нее ее дуги

Рис. 20.

Узел сети, который является начальным для всех своих дуг (все эти ду­ги являются выходящими), называют источником, а узел, который явля­ется конечным для всех своих дуг (все эти дуги являются входящими), — стоком. Все другие узлы такой сети называются промежуточными. Припишем каждой дуге (1;2)ориентированной сети неотрицательное целое число

c_ij=c(i.j)

которое будем называть пропускной способностью этой дуги, интуитивно представляя пропускную способность c_ij как максимально возможное количество продукта (например, жидкости или газа в трубопроводе), которое может быть доставлено из узла А_i, в узел А_j в единицу времени.

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

Замечание. Это ограничение кажущееся: наличие нескольких источ­ников легко сводится к одному виртуальному источнику, питающему все реально заданные. Так же можно поступить и с несколькими стоками — виртуальный сток будет питаться ото всех реально заданных стоков. Итак, рассмотрим транспортную сеть с одним источником и од­ним стоком (рис. 21); — промежуточные узлы.

Будем говорить, что в сети задан поток величины v, если каждой дуге (i,j)сети приписано неотрицательное целое число.

Рис. 21

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

(9 и 10)

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

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

Введем понятие суммарного потока па конечных дугах Ф сети отличное от понятия потока по дуге φ(и), которое рассматривалось ранее. Из (10) следует, что сумма потоков, исходящих из началь­ной вершины (истока) х₀(рис. 18), равна сумме потоков, входя­щих в конечную вершину (сток) z, т. е.

(11)

Следует заметить, что в работах по теории потоков очень часто используется термин «величина потока Ф» вместо принятого в данной книге «величина сум­марного потока на конечных дугах». Однако применение первого термина вносит определенную путаницу, так как в теории потоков имеется совершенно другое понятие «величина потока Ф», которое представляет собой множество значении по­тока на дугах графа.

Рассмотрим сеть из (n + 1) вершины. Пусть каждой дуге поставлено в соответствие число c_ij, называемое пропускной способностью дуги (i; j).

Потоком x в сети называется совокупность чисел {x_ij}, где x_ij – поток по дуге (i; j), удовлетворяющих условиям 0 £ x_ij £ c_ij, i, j = , = , i ¹ 0, n. Величиной потока x называется F(x) = = .

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

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

Теорема 5 [8, 37]. Величина любого потока не превышает пропускной способности любого разреза.

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

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

Рассмотрим алгоритм получения максимального потока из лю­бого начального потока. Эта процедура состоит из двух операций: операции А — процесса расстановки пометок у вершин и операции В — изменения потока. Имеется несколько модификаций метода пометок, у которых идея одна и та же: путем определенной системы пометок выделяются цепи (пути), которые не содержат насыщенных дуг. Пометка начинается с истока х₀, который помечается индексом 0, т. е. . Пусть задана уже помеченная вершина x_i (рис. 22). Если для какой-нибудь помеченной вершины x_i имеется смежная вер­шина x_j, соединенная с ней насыщенной дутой, то эта последняя не помечается (рис. 22, а). Если последующая вершина соединена с помеченной вершиной x_i дугой со значением потока φ(x_i,x_j)< с(x_i,x_j), то вершина х_j помечается знаком + i, т. е. (рис. 22,6). Если смежная предыдущая вершина x_j соединена с помеченной вер­шиной x_i дугой с положительным (ненулевым) значением по­тока φ(x_i,x_j)> 0, то вершина х_j помечается знаком —i, то есть (см. рис. 22в). Таким образом, не помечаются такие вершины, которые соединены с помеченной смежной вершиной i исходящей из нее насыщенной дугой или входящем в нее дугой с нулевым потоком (рис. 22),

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

Рис. 22. Пояснение к методу пометок вершин

Допустим, что при этом будет помечен сток. Иногда такая ситуа­ция называется термином прорыв (по одному из путей «прорва­лись» к стоку). В противном случае говорят о непрорыве. Это означает, что между истоком х_п и стоком z имеется путь вершины которого помечены индексами предшествующих вершин. Таким образом, в соответствии со следствием, рассмотренным ра­нее, найден путь, который может увеличить поток. В самом деле, так как найденный путь не содержит ни одной прямой насыщен­ной дуги, то можно изменить значения потоков на всех дугах этого пути на величину минимальной пропускной способности причем поток по дуге увеличивается на h, если ориентация дуги совпадает с направлением движения от х, до z, и уменьшается на это же значение, если это направление противоположно. После такого изменения получается новый поток, увеличенный на h, так как в случае прорыва на дуге (x_i z⁺ⁱ), входящей в конечную точку, поток увеличен на h. После этого старые пометки стираются и снова повторяются операции А и В. Так поступают до тех пор, пока нельзя пометить точку z (непрорыв). В этом случае получим максимальный ноток.

Данный результат был сформулирован в виде следующей теоремы:

Теорема 6 [8, 37]. Если, применяя пометки обоих типов, вершину n пометить не удалось, то полученный поток имеет максимальную величину.

Процедуру получения максимального потока рекомендуется начинать с нулевого потока.

Пример 1. Определим максимальный поток в сети, представленной на рис. 23. Около каждой дуги указаны значения се пропускной способности. Последовательный процесс решения дастся в табл. 2.

Таблица 2. Определение максимального потока в сети

Рис. 23. Пояснения к примеру 1.

В данном простом примере без особого труда можно найти путь из х₀ в z, не содержащий насыщенных дуг. Таким является путь [x₀, x₄, x₃, z]. Увеличиваем значения потока на дугах этого пути на 2, тогда дуга (х₄, x_з) становится насыщенной (в табл. 2 это отмечено чертой сверху). Соответствующие значения потока приведены в третьем столбце табл. 2. На второй итерации выбираем второй путь [х₀, х₄, х₂, z], свободный от насыщенных дуг. Изменяем (увеличиваем) значения потока на 3. Результирующий поток приведен в четвертом столбце. На третьей итерации выбирается путь [х₀, х₁, х₂, z] по­ток увеличивается на 2. Результаты приведены в пятом столбце. Прорыв в точку zбольше осуществить нельзя. Полученный поток является макси­мальным со значением Ф = 7.

Пример 2. Продемонстрируем метод пометок вершин на примере сети, представленной на рис. 24, а. Истоку х₀ присваиваем метку (+0).

1,1 3,0

1,1 1, 0

1,1

3,0

Рис. 24а. Исходная сеть к примеру 2.

Шаг 1. Далее вершине х₂ присваиваем метку +0, так как это единст­венная вершина, которую можно пометить, начиная из х₀, (в связи с тем, что дуга (х₀, х₁)

насыщена). Продолжая процесс из х₂ , можем пометить вершину х₁ индексом +2. Далее из х₁ помечаем сток z индексом +1. Произошел прорыв (рис. 24, б соответствующие индексы стоят у вершин). Вдоль рассмотренного пути [х₀, х₂, x₁, z]увеличить поток по дугам, причем учитывая пропускные способности дуг, входящих в рассматриваемый путь величина такого увеличения должна равняться 1.

+2

1,1 3,1

+0 +1

1,1 1, 0

1,1

3,0

+0+

Рис. 24б

Изменяем на это значение потоки на дугах.

Шаг 2. Получаем новый поток со значением суммарного потока на конечных дугах равным 2 (вместо исходного, равного 1), который представлен на рис. 24, в. Далее снова происходит прорыв вдоль пути [x₀ (x₀x₂)x₂(x₁x₂)x₁(x₁z)z].

-2

1,1 3,1

+0

1,1 1, 1 +1

1,1

3,1

+0

Рис. 24в

После изменения потоков вдоль этого пути на 1 получаем поток, представлен­ный на рис. 24, г. Пометка вершин по этому потоку не дает прорыва. Этот поток является максимальным со значением суммарного потока на конечных дугах, равным 3. Минимальный разрез состоит из дуг (x₀, x₁), (x₂, x₁), (x₂, z).

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

1,1 3,2

1,0 1, 1

1,1

3,2

Рис. 24г. Результат решения

Рассмотрим еще один пример для сети, приведенной на рис. 19, в которой пропускные способности всех дуг равны единице.

Шаг 0. Берем произвольный поток (например, поток x₀₁ = x₁₂ = x₂₅ = 1). Помечаем начальную вершину индексом «0» (индексы на рис. 19 приведены в квадратных скобках).

Обозначим Z – множество помеченных вершин.

Общий шаг. Первое действие. Помечаем вершину j индексом +i, если, во-первых, существует дуга (i; j), и, во-вторых, i Î Z, x_ij < C_ij.

Если в результате этого типа пометок мы пометили выход, то поток можно увеличить хотя бы на единицу (если c_ij – целые числа). Двигаясь обратно, можно найти путь, поток по которому можно увеличить. Однако, как видно из примера, этого недостаточно для нахождения максимального потока.

Второе действие. Помечаем вершину i индексом -j, если, во-первых, существует дуга (i; j), и, во-вторых, j Î Z, x_ij > 0 (легко видеть, что пометки первого типа увеличивают поток по дуге, а пометки второго типа – уменьшают).

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

Рис. 25. Поиск максимального потока

Рассмотрим цепь m = (0; 3; 2; 1; 4; 5), приведенную на рис. 25. Полученные в результате второго действия потоки обозначены жирным шрифтом.

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

Сеть называется плоской, если ее можно начертить на плоско­сти так, чтобы все ее дуги пересекались только в узлах сети. Неориентированная плоская сеть называется (s, t)-плоской, если после добавления к ней дуги (s; t)она останется плоской. Напри­мер, плоская сеть, изображенная па рис. 26, не является (s, t)-плоской. Эта же сеть, но без дуги (2; 3), уже будет (s, t)-плоской. Рассмотрим (s, t)-плоскую сеть, которая получится, если из сети на рис. 26 удалить дугу (2; 3).

Рис. 26. Сеть, не являющаяся (s, t) – плоской

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

Эта задача, конечно, может быть решена посредством нахож­дения максимального потока с помощью метода расстановки поме­ток. Но, оказывается, ее можно решить проще: минимальный раз­рез в исходной сети соответствует кратчайшей цепи в сети, двой­ственной к ней. При этом необходимо учесть, что задача нахождении максимального потока в (s, t)-плоской сети проще, чем в общем случае, и эффективно решается за О (п²) действий без использования двойственной сети.

Алгоритм поиска кратчайшей цепи в двойственной сети будет не сложнее (по числу действий) алгоритма нахождения максимального потока в исход­ной сети, если число узлов в двойственной сети не превышает (по порядку) числа узлов в исходной цепи. Это действительно так: число узлов в двой­ственной сети равно числу граней f в исходной сети, а в плоской сети f ≤ 2п — 4.

Двойственная сеть строится следующим образом. Сначала чер­тится дуга (s, t)если в исходной сети этой дуги не было. Получится плоская сеть с п узлами. Плоскость чертежа окажется раз­деленной на грани (области, ограниченные ребрами и не содержа­щие внутри себя ни вершин, ни ребер). Дуга (s, t) будет разделять две грани, одна из которых является внешней. Поместим по одно­му узлу в каждую из этих граней и обозначим их через и . Аналогично, поместим по одному узлу в каждую из граней, раз­деленных дугой (i, j), и обозначим их через соответствующими буквенными обозначениями. Проведем в двойственной сети дуги, которые связывают узлы двойственной сети и при этом пересекают дуги исходной сети, как это показано на рис. 27.

Каждой дуге (i; j)исходной сети будет соответствовать дуга двойственной сети. Каждому разрезу, разделяющему вершины s и t в исходной сети, будет соответствовать некоторая цепь из в . При этом оказывается, что пропускная способность с_ij дуги (i; j)равна длине соответствующей дуги в двойственной сети. В этом случае кратчайшая цепь из в будет соответствовать минимальному разрезу, разделяющему s и t. Рис. 27 иллюстрирует описанное построение.

Рис. 27. Сеть, двойственная к исходной (s, t) – плоской сети