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

Выделим для заданной транспортной сети 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, либо ¥. Пример 91.

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

Решение.

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

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

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.4.2. Орграф приращений: