Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Потоки в транспортных сетях




ТРАНСПОРТНЫЕ СЕТИ

Транспортной сетью Т называется совокуп­ность двух объектов:

1. Связного графа , обладающего следующими свой­ствами:

¨ в графе отсутствуют петли,

¨ в графе существует одна и только одна вершина такая, что обратное отображение для нее , т.е., вершина, которой инцедентны только выходящие дуги,

¨ в графе существует одна и только одна вершина , такая, отображение , т.е., вершина, которой инцедентны только входящие дуги.

 

2. Целочисленной неотрицательной функции , за­данной на множестве дуг графа .

Вершина называется входом сети, вершина вы­ходом. Значение функции на дуге называется про­пускной способностью дуги.

(а)

 
 


2

x0 •

5

 

(б)

1

z

 

6

 

 

Рисунок 4.6 – Вход (а) и выход (б) транспортной сети

Пусть — множество дуг, заходя­щих в вершину , a — множество дуг, выходящих из вершины . Целочисленная неотрицательная функция , заданная на множестве дуг графа , называется по­током, если она удовлетворяет следующим условиям:

1. ;

2. .

Эти свойства можно объяснить таким образом:

1. Поток в дуге не может превышать её пропускную способность.

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

Сколько потока вытекает из входной вершины , столько его втекает в выходную вершину .

Следствие: = φ z,

где φ zпоток транспортной сети.

Рассмотрим подмножество вершин графа , которое является подмножеством всех вершин таких, что , .

U - множество дуг, входящих в подмножество ;

U - множество дуг, выходящих из подмножества .

Разрезомтранспортной сети называется объединение этих множеств: .

 

Свойства разреза:

1. Так как разрез включает выход сети, то общий поток через разрез будет равен потоку транспортной сети:

φ z =. (4.1)

2. Пропускной способностью раз­реза является сумма пропускных способностей дуг, входящих в разрез:

. (4.2)

Так как φ (u) ≤ C (u) (4.3), то, заменив в (4.1) φ (u) на C (u), и учитывая (4.2), получим:

φzC (A) (4.4),

т.е., поток транспортной сети не превышает пропускную способность любого разреза.

 

3

1 2

x0 2 1 1 z

6 5

3

A

 

Рисунок 4.7 – Разрез транспортной сети

 

Лемма: Для любого потока и любого разреза справедливо соотношение .

Доказательство.

В силу того, что выход сети , для величины потока справедливы соотношения: .

Следствие. Если для некоторого потока и некоторого разреза выполняется равенство , то поток обладает наибольшей величиной.




Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 416; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.