Алгоритм построения максимального потока в транспортной сети.

Пример 91.

Орграф приращений.

Выделим для заданной транспортной сети D и допустимого потока jв этой сети орграф приращений I(D, j), имеющий те же вершины, что и сеть D. Каждой дуге x = (v, w)ОX транспортной сети D в орграфе приращений I(D, j) соответствуют две дуги: x и x` = (w,v) - дуга, противоположная по направлению дуге x. Припишем дугам x = (v, w)ОX, x` = (w, v)орграфа приращений I(D, j) длину l:

т.е. орграф I(D, j) является нагруженным. При этом, очевидно, что длинна любого пути из v1 в vn орграфе I(D, j) равна либо 0, либо Ґ.

Построить орграф приращений для данной транспортной сети и построенного полного потока в этой сети.

Решение.

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

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

Алгоритм построения максимального потока в транспортной сети D:

Шаг 1. Полагаем i = 0. Пусть j0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: j0 (x), x О X).

Шаг 2. По сети D и потоку ji строим орграф приращений I(D, ji).

Шаг 3. Находим простую цепь hi, являющуюся минимальным путем из v1 в vnв нагруженном орграфе I(D, ji)(например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна Ґ, то поток ji максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи hi на максимально допустимую величину ai > 0, где ai О Z (прибавляя ее для каждой дуги x О X, через которую проходит цепь hi, к уже имеющейся величине потока по дуге x, если направления x и hi совпадают, и, вычитая, если направления x и hi противоположны).

Пример 92.

Выяснить является ли полный поток максимальным (рис. 51), если нет, то дополнить его до максимального.

Решение.

Для решения используем алгоритм Форда-Беллмана нахождения минимального пути в нагруженном орграфе.

Построим матрицу длин дуг C(D) и l-матрицу (табл. 69).

Таблица 69

Поскольку , то существует нулевой путь из источника v1 в сток v6. Значит, полный поток не является максимальным. Дополним его до максимального. Для этого найдем путь нулевой длины:

Получаем, что k1 = 4. Таким образом, минимальное число дуг в пути среди всех нулевых путей из v1 вv6 в орграфе приращений равняется 4. Определим теперь последовательность номеров i1, i2, i3, i4, i5,где i1 = 6.

Получаем, что в качестве такой последовательности надо взять номера 1, 3, 2, 5, 6, так как

Тогда v1v3v2v5v6 – искомый нулевой путь из v1 в v6 . Дуги, совпадающие по направлению с дугами исходной транспортной сети помечаем знаком «+», не совпадающие – знаком «-».

Получаем, Теперь необходимо найти величину, которую будем перемещать по полученному контуру. Для этого, каждому ребру в контуре поставим в соответствие число a(i, j), которое находим по следующему правилу: если направление ребра (i, j) в контуре совпадает с направлением ребра x в транспортной сети, то a(i,j)=с(х)-j(х); если направление ребра в контуре не совпадает с направлением ребра в транспортной сети, то a(i, j)=j(х). Итак, из чисел a(i, j) найдем минимальное:

min{8-2=6, 2, 6-2=4, 9-4=5}=2.

Перемещаем по контуру 2.

В результате получаем поток, изображенный на рисунке 52.

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 11. Проверим, является ли он максимальным.

Построим матрицу длин дуг C(D) и l-матрицу (табл. 70).

Таблица 70

Так как , то нулевого пути из v1 в v6 не существует. Значит, поток является максимальным.