Задание 1 Алгоритм построения минимального остовного дерева
1.1 Теоретическая часть
Рассмотрим вкратце
алгоритм построения минимального
остовного дерева. Обозначим через
множество узлов сети и введем новые
обозначения:
— множество узлов
сети, соединенных алгоритмом после
выполнения
-й
итерации этого алгоритма,
—
множество узлов
сети, не соединенных с узлами множества
после выполнения
-й
итерации этого алгоритма.
Этап 0.
Пусть
и
.
Этап 1.
Выбираем любой узел
из множества
и определяем
,
тогда
.
Полагаем
.
Основной этап
.
В множестве
выбираем узел
который соединен самой короткой дугой
с каким-либо узлом из множества
.
Узел
присоединяется к множеству
и удаляется из множества
.
Таким образом,
.
Если множество
пусто, то выполнение алгоритма
заканчивается. В противном случае
полагаем
и повторяем последний этап.
1.2 Пример выполнения задания
В институте прокладывают компьютерную сеть. В каждом корпусе установлено по одному маршрутизатору. Институт планирует соединить компьютерной сетью шесть корпусов. На рис. 1.1 показана структура планируемой сети и расстояния (в км.) между корпусами. Необходимо спланировать наиболее экономичную компьютерную сеть затратив минимум кабеля.
Этап 0.
Пусть
и
.
Этап 1.
Выберем узел 1 как начальный узел, внесем
его в множество
и исключим из множества
.
Тогда
.
Делаем
.
Рисунок 1.1 – Компьютерная сеть института
Этап 2. В
множестве
находим такой узел, который соединен
самой короткой дугой с узлами из множества
(рис 1.2а). Отыскиваем
,
т.к.
.
Таким образом
получаем
и дугу
,
которую выделяем жирным цветом, т.е.
прокладываем в этом направлении кабель.
Затем исключаем узел 2 из множества
и добавляем его в множество
(рис 1.2б). Получаем
.
Делаем
.
Этап 3. В
множестве
находим такой узел, который соединен
самой короткой дугой с узлами из множества
(рис 1.2б). Ищем
,
т.к.
.
Таким образом
получаем
и дугу
,
по которой прокладываем кабель (рис.
1.2б). Затем исключаем узел 5 из множества
и добавляем его в множество
.
Получаем
.
Делаем
.
Этап 4. В
множестве
находим такой узел, который соединен
самой короткой дугой с узлами из множества
(рис 1.2в). Находим
,
т.к.
.
Таким образом
получаем
и дугу
(рис.
1.2в). Затем исключаем узел 4 из множества
и добавляем его в множество
.
Получаем
.
Делаем
.
Этап 5. В
множестве
находим такой узел, который соединен
самой короткой дугой с узлами из множества
(рис 1.2г). Находим
,
т.к.
.
Таким образом
получаем
и дугу
добавляем к сети (рис. 1.2г). Затем исключаем
узел 6 из множества
и добавляем его в множество
.
Получаем
.
Делаем
.
Этап 6. В
множестве
находим такой узел, который соединен
самой короткой дугой с узлами из множества
(рис 1.2д). Находим
а) Этап 2 б) Этап 3
в) Этап 4 г) Этап 5
д) Этап 6 е) Этап 7
Рисунок 1.2 – Последовательные итерации выполнения алгоритма построения минимального остовного дерева
,
т.к.
.
Таким образом
получаем
и из двух подходящих дуг
и
выберем одну по желанию, к примеру
выберем
т.к. у нее меньше номер вершины в множестве
.
Добавляем выбранную дугу к сети (рис.
1.2д). Затем исключаем узел 3 из множества
и добавляем его в множество
.
Получаем
.
Делаем
.
Этап 7. Т.к.
множество
,
следовательно выполнение алгоритма
закончено. Ответ представлен на рисунке
1.2е. Минимальная длина кабеля для
построения такой сети равна 1+3+4+3+5=16 км.