Задача про кістякове дерево екстремальної ваги. Лабораторна робота з Дискретна математика. Робота № 527776

Задача про кістякове дерево екстремальної ваги

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра СКС

Інформація про роботу

Рік:

2016

Тип роботи:

Лабораторна робота

Предмет:

Дискретна математика

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки Національний університет “Львівська політехніка” Кафедра СКС / Звіт з лабораторної роботи № 2 з дисципліни: “Дискретна математика” на тему: “Задача про кістякове дерево екстремальної ваги” Теоретичні відомості При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі. Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто перевіряти наявність циклів в графі, що виникає. Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда). Крок 1. Присвоєння початкових значень. S'={Xα}, Xα - довільна вершина графа (скажімо, перша за номером). S''= S\S', V' = Ø Крок 2. Оновлення даних. Знаходимо таке ребро (Xi, Xj), що Xi ϵ S', Xj ϵ S'' та W(Xi, Xj)= min{ W(Xα, Xβ)| Xα ϵ S', Xβ ϵ S''} Покладаємо S' = S' U { Xi }, S'' = S\S', V' = V'U{(Xi, Xj)} Крок 3. Перевірка на завершення. Якщо S' = S, то G' = (S', V') - шуканий граф. В іншому випадку переходимо на Крок 2. Далі наведено приклад виконання алгоритму Пріма. Граф задано списком ребер з вказанням їх ваг. (1,4|1), (4,1|1), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,4|5), (4,2|5), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (4,5|2), (5,4|2). Відповідний цьому списку граф / Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування. (1,4|1), (4,1|1), (4,5|2), (5,4|2), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (2,4|5), (4,2|5). Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги). S = {1,2,3,4,5} Крок 1. S' = {1} S'' = {2,3,4,5} V' = Ø Крок 2 . V' = V'U{(1,4|1)}={(1,4|1)} S' = {1,4} S'' = {2,3,5} Крок 3. S'≠S Крок 2. V' = V'U{4,5|2} = {(1,4|1), (4,5|2)} Крок 3. S'≠S Крок 2. V' = V'U {(5,2|4)} = {(1,4|1), (4,5|2), (5,2|4)} S' = {1,2,4,5} S'' = {3} Крок 3. S'≠S Крок 2. V' = V'U {(2,3|3)} = {(1,4|1), (4,5|2), (5,2|4), (2,3|3)} S' = {1,2,3,4,5} S'' = Ø Крок 3. S'=S Таким чином, отримали таке кістякове дерево мінімальної ваги для початкового графа. / Вага отриманого кістякового дерева дорівнює 10. Індивідуальне завдання Знайти мінімальну вагу кістякового дерева. Результат виконання програми /

Лабораторна робота Дискретна математика

fake_fake

27.03.2016 18:55

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись