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 изображен орграф приращений, соответствующий данному потоку в исходной транспортной сети.