Задача 2.2

Вариант 1

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

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

Вариант 2

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

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

Вариант 3

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

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

Вариант 4

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