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 изображен орграф приращений, соответствующий данному потоку в исходной транспортной сети.
Еще по теме 3.4.2. Орграф приращений:
- Полное приращение и полный дифференциал.
- Титул II. О приращении узуфрукта (De usu fructu adcrescendo)
- Эвиденциальное приращение при других глаголах
- §7 Процессы с независимыми приращениями.
- Первоначальное приобретение вещей другихлиц § 139. а. Соединение (приращение)
- Синтаксическое поле предложения (СПП) как синтаксическая парадигма, в первую очередь, внутримодельных преобразований, связанных с приращением определенного типа смыслов. Структура СПП.
- 3.2.3. Нахождение минимального пути в нагруженном графе
- 3.4.3. Алгоритм построения максимального потока в транспортной сети
- Достижимость и связность.
- 28. Частные производные.
- 3.2.1. Поиск путей (маршрутов) с минимальным числом дуг (ребер)
- § 19, Производная функции в точке, её геометрический и механический смысл
- Матрицы графов.
- § 25- Дифференциал функции