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. Орграф приращений:

  1. Те
  2. Ша
  3. Сособственники имеют не реальные части общего имущества, а доли в праве на него, то есть "идеальные
  4. Право на принятие наследства может перейти к другим лицам в порядке так называемой
  5. Удержание и задаток как способы обеспечения исполнения обязательств.
  6. Кондоминиум может находиться в управлении только одного физического (управляющий - индивидуальный
  7. Как только численность населения на данной территории достигала определенной величины (обычно 5 тыс. чел.),
  8. 2. Системология и борьба с преступностью.
  9. §4. Содержание и специфика объективной стороны преступлений, предусмотренных ст. 176 УК РФ
  10. Синтаксическое поле предложения (СПП) как синтаксическая парадигма, в первую очередь, внутримодельных преобразований, связанных с приращением определенного типа смыслов. Структура СПП.
  11. Титул II. О приращении узуфрукта (De usu fructu adcrescendo)
  12. Первоначальное приобретение вещей другихлиц § 139. а. Соединение (приращение)
  13. Содержание дисциплины
  14. Полное приращение и полный дифференциал.