и мы переходим к пятому этапу. В противном случае полагаем 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.

[Ю, 3]

д)/5 = 10 е) Сквозных путей нет

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

Шаг 2. = {4} (отметим, что с35 = 0, поэтому узел 5 не включается в S3).

Шаг 3. k = 4, назначаем я4 = с34 = 10 и помечаем узел 4 меткой [10, 3]. Полагаем / = 4 и возвращаемся к шагу 2.

Шаг 2. ШагЗ.

4= {5} (поскольку узлы 1 и 3 уже помечены, они не включаются в 54).

к - 5 и а& = с45 = 20. Помечаем узел 5 меткой [20, 4]. Получен сквозной путь. Переходим к шагу 5.