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

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

т.е. орграф I(D, ) является нагруженным. При этом, очевидно, что длинна любого пути из v₁ в v_n орграфе I(D, ) равна либо 0, либо .

Пример 1.21.

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

Решение.

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

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

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

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

Шаг 3. Находим простую цепь _i, являющуюся минимальным путем из v₁ в v_nв нагруженном орграфе I(D, _i) (например, используя алгоритм Форда - Беллмана). Если длина этой цепи равна , то поток _i максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи _i на максимально допустимую величину a_i> 0, где a_iZ(прибавляя ее для каждой дуги xX, через которую проходит цепь _i, к уже имеющейся величине потока по дуге x, если направления x и _i совпадают, и, вычитая, если направления x и _i противоположны).

Пример 1.22.

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

Решение.

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

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

Таблица 1.4

	v₁	v₂	v₃	v₄	v₅	v₆
v₁			0				0	0	0	0	0	0
v₂	0				0				0	0	0	0
v₃	0	0		0	0			0	0	0	0	0
v₄		0	0			0						0
v₅		0	0			0				0	0	0
v₆				0	0						0	0

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

Получаем, что k₁ = 4. Таким образом, минимальное число дуг в пути среди всех нулевых путей из v₁вv₆ в орграфе приращений равняется 4. Определим теперь последовательность номеров i₁, i₂, i₃, i₄, i₅,где i₁ = 6.

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

Тогда v₁v₃v₂v₅v₆ – искомый нулевой путь из v₁вv₆ . Дуги, совпадающие по направлению с дугами исходной транспортной сети помечаем знаком «+», не совпадающие – знаком «-».

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

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

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

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

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

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

Таблица 1.5