Задать вопрос юристу

3.4.1. Поток в транспортной сети

Определение. Функция j (x), определенная на множестве X дуг транспортной сети D, и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в транспортной сети D, если:

1) для любой дуги x Î X величина j(x), называемая потоком по дуге х, удовлетворяет условию 0 j(x) c(x);

2) для любой промежуточной вершины v выполняется равенство

т.е. сумма потоков по дугам, заходящими в v, равна сумме потоков по дугам, исходящими из v.

Определение. Величиной потока j в транспортной сети D называется величина j, равная сумме потоков по всем дугам, заходящим в vn, или, что то же самое, величина, равная сумме потоков по всем дугам, исходящим из v1, т.е.

Пусть j - допустимый поток в транспортной сети D.

Определение. Дуга x Î X называется насыщенной, если поток по ней равен ее пропускной способности, т.е. если j(x) = c(x). Поток j называется полным, если любой путь в D из v1 в vn содержит, по крайней мере, одну насыщенную дугу.

Определение. Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

Очевидно, что максимальный поток j обязательно является полным. Обратное неверно. Существуют полные потоки, не являющиеся максимальными. Тем не менее, полный поток можно рассматривать как некоторое приближение к максимальному потоку.

Алгоритм построения полного потока в транспортной сети D:

Шаг 1. Полагаем "x Î X j(x) = 0 (т.е. начинаем с нулевого потока). Кроме того, полагаем D` = D.

Шаг 2. Удаляем из орграфа D` все дуги, являющиеся насыщенными при потоке j в транспортной сети D.

Полученный орграф снова обозначаем через D`.

Шаг 3. Ищем в D` простую цепь h из v1 в vn. Если такой цепи нет, то j - искомый полный поток в транспортной сети D. В противном случае переходим к шагу 4.

Шаг 4. Увеличиваем поток j(x) по каждой дуге x из h на одинаковую величину a > 0 такую, что, по крайней мере, одна дуга из h оказывается насыщенной, а потоки по остальным дугам из h не превышают их пропускных способностей. При этом величина потока также увеличивается на a, а сам поток j в транспортной сети D остается допустимым (поскольку в каждую промежуточную вершину, содержащуюся в h, дополнительно вошло a единиц потока и из нее вышло также a единиц потока). После этого переходим к шагу 2.

Пример 90.

Построить полный поток в транспортной сети, изображенной на рисунке 43.

Решение.

Начинаем с нулевого потока (рис. 44). Пошагово выделяем простые цепи и увеличиваем поток по ним таким образом, чтобы хотя бы одна дуга в каждой из них стала насыщенной. Полученную насыщенную дугу помечаем пунктиром, помня, что по насыщенной дуге больше идти нельзя.

1. h 1 = v1v2v4v6, a1 = min{7, 3, 7} = 3 (рис. 45).

2. h 2 = v1v2v3v4v6, a2 = min{7-3, 2, 2, 7-3} = 2 (рис. 46).

3. h 3 = v1v3v5v6, a3 = min{8, 2, 9} = 2 (рис. 47).

4. h 4 = v1v2v5v6, a4 = min{7-5, 6, 9-2} = 2 (рис. 48).

Заметим, что в полученной транспортной сети не существует пути из источника в сток, по которому возможно пройти. Следовательно, построенный поток в транспортной сети является полным и j = 3+2+2+2=9.

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

Еще по теме 3.4.1. Поток в транспортной сети:

  1. 3.4.3. Алгоритм построения максимального потока в транспортной сети
  2. 1. Развитие эффективной транспортной инфраструктуры, обеспечивающей ускорение движения потоков пассажиров и товародвижения, снижение транспортных издержек.
  3. 3.4. Транспортные сети
  4. 2.4. Предоставление услуг информационно-транспортной сети
  5. Статья 279. Блокирование транспортных коммуникаций, а также захват транспортного предприятия
  6. Частные сети и сети по интересам
  7. § 2. Прокат (ст. 626-631). Комментария нет § 3. Аренда транспортных средств (ст. 632-649) 1. Аренда транспортного средства с предоставлением услуг по управлению и технической эксплуатации (ст. 632-641) 212. Какие отличительные признаки выделяет практика для договора аренды транспортных средств с экипажем?
  8. Стаття 279. Блокування транспортних комунікацій, а також захоплення транспортного підприємства
  9. 133. Контейнеризация мировой транспортной системы и «транспортные мосты»
  10. Лекция 4. Компоновка сети.Топология сети
  11. Блокування транспортних комунікацій, а також захоплення транспортного підприємства
  12. Интернет: правда и вымысел о заработках в Сети. Варианты заработка в Сети для владельца сайта.
  13. Ю. Г. Корухов. Транспортно-трасологическая спертиза по делам дорожно-транспортных, 1988
  14. Статья 794. Ответственность перевозчика за неподачу транспортных средств и отправителя за неиспользование поданных транспортных средств
  15. 214. Может ли арендная плата быть обусловлена скоростью эксплуатируемого транспортного средства или иными факторами, ставящими оплату в зависимость от проделанной транспортным средством работы?
  16. 2. Аренда транспортного средства без предоставления услуг по управлению и технической эксплуатации (ст. 642-649) 217. Возможно ли передать транспортное средство без экипажа в бессрочное пользование?
  17. 42. Транспортный комплекс России. География важнейших транспортных магистралей. Современные проблемы развития транспорта в условиях становления в условиях становления рынка.
  18. §3. Аренда транспортных средств 1. Аренда транспортного средства с предоставлением услуг по управлению и технической эксплуатации
  19. Транспортная обеспеченность страныПоказатели транспортной обеспеченности и доступности
  20. 2. Аренда транспортного средства без предоставления услуг по управлению и технической эксплуатации Статья 642. Договор аренды транспортного средства без экипажа