Міністрерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра математичних
методів в інженерії
ЗВІТ
до лабораторної роботи №3
з курсу «Сучасні методи розв’язку дискретного програмування»
Мінімальне остовне дерево зв’язного графа
Виконав:
ст. гр.
.
Перевірила:
Крива Н.Р.
Тернопіль
Тема:
Мінімальне остовне дерево зв’язного графа
Мета:
Побудова остовного дерева за допомогою програмного пакету MatLab
Текст програми:
%Лабораторна робота №3
%
%Варіант
clear all
V=[1 2; 1 1; 2 2; 2 1; 3 2; 3 1; 4 2; 4 1];
E=[1 2 1; 1 3 2; 1 4 3; 2 4 4; 4 3 5; 3 5 6; 3 6 7; 4 6 8; 5 6 9; 6 8 10; 5 7 11; 5 8 12; 7 8 13];
grPlot(V(:,1:2),E,'d');
set(get(gcf,'CurrentAxes'),...
'FontName','Times New Roman Cyr','FontSize',10) % шрифт
title('\bfВихідний граф зі зваженими ребрами')
nMST=grMinSpanTree(E(:,1:2)); % остовне дерево
fprintf('Кількість ребер в остовному дереві = %d\n',length(nMST));
fprintf('Загальна вага = %d\n',sum(E(nMST,3)));
grPlot(V,E(nMST,:));%остовне дерево
set(get(gcf,'CurrentAxes'),'FontName','Times New Roman Cyr','FontSize',10)% шрифт
title('\bfОстовне дерево')
Результати роботи програми:
Рисунок 1- Результат роботи програми
Рисунок 2 – Вихідний граф зі зваженими вершинами
Рисунок 3 – Остовне дерево
Кількість ребер в остовному дереві = 7
Загальна вага = 40
Висновок: Виконавши дану лабораторну роботу, я розглянув поняття остовного дерева і відобразив його у програмі MatLab