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

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

УПРАЖНЕНИЕ 6.4.1

1. Для сети, показанной на рис. 6.29, проведите еще два разреза и найдите их пропускные способности.

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

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

Рассмотрим ребро (i, у) с (начальной) пропускной способностью (С..С ). В процессе выполнения алгоритма части этих пропускных способностей забираются потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Будем использовать запись (сц, с\,) для представления остаточных пропускных способностей. Сеть, в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла у, получающего поток от узла i, определим метку [ау, Л, где а - величина потока, протекающего от узла у к узлу i. Чтобы найти максимальный поток, выполним следующие действия.

Этап 1. Для всех ребер (£, у) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем (cijt с\,) = (С,С;,) . Назначим а1 = оо и пометим узел 1 меткой [оо, -]. Полагаем i = 1 и переходим ко второму этапу.

Этап 2. Определяем множество Sl как множество узлов у, в которые можно перейти из узла i по ребру с положительной остаточной пропускной способностью (т.е. с, > 0 для всех у 6 St). Если S, Ф 0, выполняем третий этап, в противном случае переходим к п. 4.

Этап 3. В множестве Sl находим узел к, такой, что

Положим ак = с1к и пометим узел к меткой [ак, i]. Если последней меткой помечен узел стока (т.е. если к = п), сквозной путь найден,

и мы переходим к пятому этапу. В противном случае полагаем i = к и возвращаемся к п. 2.

Этап 4. Откат назад. Если i = 1, сквозной путь невозможен, и мы переходим к п. 6. Если находим помеченный узел г, непосредственно предшествующий узлу I, и удаляем узел i из множества узлов, смежных с узлом г. Полагаем i = г и возвращаемся ко второму этапу.

Этап 5. Определение остаточной сети. Обозначим через N = {1, kv k2, п) множество узлов, через которые проходит р-й найденный сквозной путь от узла источника (узел 1) до узла стока (узел п). Тогда максимальный поток, проходящий по этому пути, вычисляется как

/, = min{o o ,oH> ...,а }.

Остаточные пропускные способности ребер, составляющих сквозной путь, уменьшаются на величину / в направлении движения потока и увеличиваются на эту же величину в противоположном направлении. Таким образом, для ребра (i,j), входящего в сквозной путь, текущие остаточные пропускные способности (ct/, cjt) изменятся следующим образом:

a) (c,t - fp, с + fp), если поток идет от узла i к узлу

b) (сч + f , c/t - fp), если поток идет от узлаj к узлу L

Далее восстанавливаем все узлы, удаленные в п. 4. Полагаем i - 1 и возвращаемся ко второму этапу для поиска нового сквозного пути.

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

a) При т найденных сквозных путях максимальный поток вычисляется по формуле

F = fl+f2 + ...+fm.

b) Имея значения начальных {Cv,Cji) и конечных (с,., с.,) пропускных способностей ребра (i, /), можно вычислить оптимальный поток через это ребро следующим образом. Положим (а,р) = (С(/-с,у,Су1-с>,). Если а > 0, поток, проходящий через

ребро (i, j), равен а. Если же Р > 0, тогда поток равен р. (Случай, когда одновременно а > 0 и р > 0, невозможен.)

Процесс отката назад на четвертом этапе выполняется тогда, когда алгоритм должен убить промежуточный узел до момента реализации сквозного пути. Коррекцию пропускных способностей, выполняемых в п. 5, можно пояснить на примере простой сети, показанной на рис. 6.30. На рис. 6.30, а найден первый сквозной путь Лг1 = {1, 2, 3, 4} с максимальным потоком /, = 5. После этого остаточные пропускные способности ребер (1, 2), (2, 3) и (3, 4) изменятся соответственно с (5, 0) на (0, 5). На рис. 6.30, б показан второй сквозной путь N2 = {1, 3, 2, 4} с максимальным потоком /2 = 5. После коррекции пропускных способностей получаем сеть, показанную на рис. 6.30, в, где уже невозможно построить сквозной путь. Почему так получилось? При вычислении остаточных пропускных способностей в п. 5 при переходе от сети б к сети в невозможна организация потока в направлении 2 -> 3. Получается, что алгоритм как бы помнит , что поток в направлении 2 -> 3 уже был в предыдущих сквозных путях, и поэтому снова (на пятом этапе) изменяет пропускную способность с 0 до 5 в направлении от узла 3 к узлу 2.

Пример 6.4.2

Найдем максимальный поток в сети из примера 6.4.1 (рис. 6.29). На рис. 6.31 предлагается графическая иллюстрация выполнения алгоритма. Считаем полезным сравнить описание выполняемых алгоритмом вычислительных итераций с их графическим представлением.

Итерация 1. Положим остаточные пропускные способности (ci;, cJt) всех ребер равными первоначальным пропускным способностям (Q,C-j) .

Шаг 1. Назначаем я, = оо и помечаем узел 1 меткой [оо, -]. Полагаем ( = 1. Шаг 2. S, = {2, 3, 4} (* 0).

Шаг 3. к = 3, поскольку cl3 = тах{с12, с13, си) = тах{20, 30, 10} = 30. Назначаем а3 = с13 = 30 и помечаем узел 3 меткой [30, 1]. Полагаем ; = 3 и возвращаемся к шагу 2.

Шаг 4. £,= {4,5}.

Шаг 5. к = 5 и аь = с35 = тах{10, 20} = 20. Помечаем узел 5 меткой [20, 3]. Получен сквозной путь. Переходим к шагу 5.

Шаг 6. Сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: (5) -> [20, 3] -> (3) -> [30, 1] -> (1). Таким образом, N, = {1, 3, 5} и /, = min{fl а3, я5} = {оо, 30, 20} = 20. Вычисляем остаточные пропускные способности вдоль пути /V,:

(с , с ) = (30 - 20, 0 + 20) = (10, 20),

(с , с53) = (20 - 20, 0 + 20) = (0, 20).

Итерация 2

Шаг 1. Назначаем а1 - оо и помечаем узел 1 меткой [оо, -]. Полагаем = 1. Шаг 2. 5, = {2, 3,4}.

Шаг 3. к =2, назначаем а2 = с]2 = тах{20, 10, 10} = 20 и помечаем узел 2 меткой [20, 1]. Полагаем i = 2 и возвращаемся к шагу 2.

Шаг 2. S2={3, 5}.

Шаг 3. к = 3 и а3 = с23 = 40. Помечаем узел 3 меткой [40, 2]. Полагаем / = 3 и возвращаемся к шагу 2.