Задача 18.1

Найдите дерево кратчайших расстояний для следующей сети службы пожарной безопасности (рис. 18.5).

1. Какова минимальная длина связного дерева?

Задача 18.2

В Москве возможно строительство нового парка. Дизайнеры определили идеальные места расположения павильонов, торговых палаток, пикников, лодочных станций, открытых сцен и т.д. Эти места представлены узлами на сети, приведенной ниже (рис. 18.6). Дуги сети отражают возможные альтернативы дорожек в парке. Дизайнеры хотят минимизировать общую протяженность дорожек, которые требуется провести в парке, и при этом обеспечить доступ ко всем узлам. Какое решение вы им предложите?

Рис. 18.6

Какова минимальная общая протяженность дорожек?

Задача 18.3

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

общая длина и трассировка конвейерной системы, которая позволит посылать образцы продукции со всех участков в лабораторию?

Лаборатория ( 1

'-<

\<У

Рис. 18.7 Какова минимальная общая протяженность конвейера?

Задача 18.4

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

Рис.18.8

Какова минимальная общая протяженность сети связи?

Задача 18.5

Фирма "Маманин & Ко" получила заказ на прокладку кабеля для кабельного телевидения в районе Ясенево (Москва). Узлы сети, приводимой ниже, отражают точки, к которым должна быть подведена кабельная сеть (рис. 18.9). Дуги сети показывают количество километров между точками подвода кабеля. Предложите решение, которое позволит обеспечить доступ кабельной сети ко всем точкам, но при этом общая протяженность кабельных линий будет минимально возможной.

Рис. 18.9 Какова минимальная общая протяженность кабельной сети?

Задача 19.1

Система автодорог "Север—Юг", проходящих через Псковскую область, может обеспечить пропускные, способности, показанные на приводимом ниже рисунке (тыс.автомашин в час) (рис. 19.9).

1. Каков максимальный поток через эту систему ( тыс. автомашин в час)?

Существуют ли еще пути от узла 1 до узла 7, которые имеют в направлении потока мощности, превышающие О? Попробуйте 1— 4—6—3—5—7 с потоком р(=!, определяемым дугой 3—5. Это увеличивает поток до 14 тыс. автомобилей в час. Однако из приводимой ниже пересмотренной сети вы можете видеть, что больше не существует путей из узла 1 в узел 7 с мощностью, превышающей нуль на всем пути; таким образом, 14 тыс. — это максимальный поток через сеть (рис. 19.6).

Обратите внимание на то, что поток в 1000 автомобилей в час в направлении 6-3 стал разрешен на итерации 6. Однако из начальной сети мы знаем, что мощность потока в направлении 6—3 равна нулю; таким образом, 1 тыс. единиц в час в направлении 6—3 представляет собой фиктивный поток. Реальный же эффект этого потока состоит в том, что 1 тыс. единиц потока, первоначально отданного дуге 3—6 на итерации 1, теперь предназначается дуге 3—5, чтобы сделать возможным добавить к общему потоку через сеть эту 1 тыс. единиц. Давайте теперь определим величину и направление потока на каждой дуге — так, чтобы достичь общей величины в 14 тыс. автомобилей в час.

Потоки по дугам для достижения максимального общего потока могут быть найдены путем сравнения конечных мощностей потоков по дугам с первоначальными мощностями. Если конечная мощность потока меньше первоначальной мощности потока, поток происходит по дуге с величиной, равной разнице между первоначальной и конечной мощностями потока. Рассмотрим, например, дугу 3—6 с первоначальной и конечной мощностями, показанными ниже.

Поскольку конечная мощность потока в направлении 3—6 меньше первоначальной мощности потока, дуга имеет величину

Въезд в Псковскую область

Рис.19.9

2. Сколько автомашин в час должно проехать по дороге 5—6, чтобы обеспечить максимальный поток?