Graf4

Петербургский государственный университет путей сообщения

Императора Александра I

Кафедра «Математика и моделирование»

Расчётно-графическая работа №2

«Построение минимального остова для неориентированной сети»

Выполнил студент Д. А. Баранов

Факультет: АИТ

Группа: АР-709

Номер зачётной книжки: 01-709-02

Проверил: Ю.В. Боровских

Санкт-Петербург

2018

Задача. Представить графически неориентированную сеть , заданную весовой матрицей . Построить минимальный остов для сети с помощью алгоритма Прима.

Весовая матрица:

13

Рис. 1 – заданный остов

В алгоритме Прима искомое остовное поддерево строится в результате последовательного расширения исходного поддерева. На каждой итерации число вершин и рёбер поддерева увеличивается на 1.

Шаг 0. Присвоение начальных значений.

Разбиваем исходное множество узлов V = {v_1, v_2, v_3, v_4, v_5, v₆} на два непересекающихся подмножества:

Vʹ = {v₁}, Vʹʹ = V-Vʹ = {v_2, v_3, v_4, v_5, v₆}.

Исходное множество рёбер пустое: Eʹ =Ø.

1-ая итерация.

Шаг 1. Обновление данных.

Находим в разрезе Е(Vʹ, Vʹʹ) = {[v₁, v₂], [v₁, v₃], [v₁, v₄]} ребро минимального веса, соединяющего узел из Vʹ с узлом из Vʹʹ. Это ребро e* = [v₁, v₂], w(e*) = 5. Выбор на рисунке:

13

Обновляем подмножества узлов и рёбер:

Vʹ = {v₁, v₂}, Vʹʹ = {v₃, v₄, v₅, v₆}, Еʹ= {[v₁, v₂]}.

Шаг 2. Проверка на завершение построения минимального остова.

Так как полученное подмножество Vʹ = {v₁, v₂} не совпадает с исходным множеством V, то продолжаем итерации с шага 1.

2-ая итерация.

Шаг 1. Обновление данных.

Находим в разрезе Е(Vʹ, Vʹʹ) = {[v₁, v₄], [v₂, v₄], [v₂, v₃] , [v₁, v₃]} ребро минимального веса, соединяющего узел из Vʹ с узлом из Vʹʹ. Это ребро e* = [v₂, v₄], w(e*) = 7. Выбор на рисунке:

13

Обновляем подмножества узлов и рёбер:

Vʹ = {v₁, v₂, v₄}, Vʹʹ = {v₃, v₅, v₆}, Еʹ= {[v₁, v₂], [v₂, v₄]}.

Шаг 2. Проверка на завершение построения минимального остова.

Так как полученное подмножество Vʹ = {v₁, v₂, v₄} не совпадает с исходным множеством V, то продолжаем итерации с шага 1.

3-ая итерация.

Шаг 1. Обновление данных.

Находим в разрезе Е(Vʹ, Vʹʹ) = {[v₂, v₃], [v₃, v₄], [v₄, v₅], [v₃, v₅], [v₁, v₃]} ребро минимального веса, соединяющего узел из Vʹ с узлом из Vʹʹ. Это ребро e* = [v₃, v₄], w(e*) = 5. Выбор на рисунке:

13

Обновляем подмножества узлов и рёбер:

Vʹ = {v₁, v₂, v₃, v₄}, Vʹʹ = {v₅, v₆}, Еʹ= {[v₁, v₂], [v₂, v₄], [v₄, v₃]}.

Шаг 2. Проверка на завершение построения минимального остова.

Так как полученное подмножество Vʹ = {v₁, v₂, v₃, v₄} не совпадает с исходным множеством V, то продолжаем итерации с шага 1.

4-ая итерация.

Шаг 1. Обновление данных.

Находим в разрезе Е(Vʹ, Vʹʹ) = {[v₁, v₃], [v₁, v₄], [v₃, v₅], [v₃, v₆], [v₄, v₅]} ребро минимального веса, соединяющего узел из Vʹ с узлом из Vʹʹ. Это ребро e* = [v₃, v₆], w(e*) = 5.

Выбор на рисунке:

13

Обновляем подмножества узлов и рёбер:

Vʹ = {v₁, v₂, v₃, v₄, v₆}, Vʹʹ = {v₅}, Еʹ= {[v₁, v₂], [v₂, v₄], [v₄, v₃], [v₃, v₆]}.

Шаг 2. Проверка на завершение построения минимального остова.

Так как полученное подмножество Vʹ = {v₁, v₂, v₃, v₄, v₆} не совпадает с исходным множеством V, то продолжаем итерации с шага 1.

5-ая итерация.

Шаг 1. Обновление данных.

Находим в разрезе Е(Vʹ, Vʹʹ) = {[v₁, v₃], [v₂, v₃], [v₂, v₃], [v₄, v₅], [v₆, v₅], [v₃, v₅]} ребро минимального веса, соединяющего узел из Vʹ с узлом из Vʹʹ. Это ребро e* = [v₄, v₅], w(e*) = 7. Выбор на рисунке:

13

Обновляем подмножества узлов и рёбер:

Vʹ = {v₁, v₂, v₃, v₄, v₅, v₆}, Vʹʹ = Ø, Еʹ= {[v₁, v₂], [v₂, v₄], [v₄, v₃], [v₃, v₆], [v₄, v₅]}.

Шаг 2. Проверка на завершение построения минимального остова.

Так как полученное подмножество Vʹ = {v_1, v_2, v_3, v_4, v_5, v₆} совпадает с исходным множеством V, то процесс построения минимального остова закончен.

Минимальный остов приведён на рисунке:

13

Его вес w_min= 5+7+5+5+7=29.