Побудова мінімального остового дерева

Міністерство освіти і науки України

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

Інститут комп’ютерних наук та інформаційних технологій

Кафедра САПР

[pic 1]

Лабораторна робота №1.

з дисципліни: “Дискретні моделі в САПР”

на тему:

“Побудова мінімального остового дерева”.

Варіант - 5

Виконав:

Ст. групи КН-407

Габовський Р. А.

Прийняв:

Викл. Кривий Р. З.

Львів-2022р.

Лабораторна робота №1.

Тема: “Побудова мінімального остового дерева”.

Мета: вивчення алгоритмів рішення задач побудови остових дерев.

Github: https://github.com/Habovskyi/DM_CAD_LAB1

Теоретичні відомості.

Графом G називають скінчену множину V з нерефлексивним симетричним відношенням R на V. Визначим E як множину симетричних пар в R. Кожний елемент V називають вершиною. Кожний елемент Е називають ребром, а E множиною ребер G.

Граф називається зв’язним, якщо в ньому для будь-якої пари вершин знайдеться ланцюг, який їх з’єднує, тобто, якщо по ребрах (дугах) можна попасти з будь-якої вершини в іншу. Цикл - це ланцюг, в якого початкова і кінцева точки співпадають. Дерево - це зв’язний граф без циклів.

Остовним деревом графа називається будь-яке дерево, яке утворене сукупністю дуг, які включають всі вершини графа. Будь-який зв’язний граф має остовне дерево.

Представлення графів в ЕОМ, в більшості випадків, здійснюється з допомогою матриць: суміжності, зв’язності, інцидентності i ваг.

Побудова максимального остового дерева алгоритмом Прима.

Сам алгоритм має дуже простий вигляд. Шуканий максимальний кістяк будується поступово, додаванням до нього ребер по одному. Спочатку остов покладається складається з єдиної вершини (її можна вибрати довільно). Потім вибирається ребро максимальної ваги, що виходить з цієї вершини, і додається в максимальне остове дерево. Після цього остов містить уже дві вершини, і тепер шукається і додається ребро максимальної ваги, що має один кінець в одній з двох обраних вершин, а інший - навпаки, у всіх інших, крім цих двох. І так далі, тобто щоразу шукається максимальне по вазі ребро, один кінець якого - вже взята в остов вершина, а інший кінець - ще не взята, і це ребро додається в остов (якщо таких ребер кілька, можна взяти будь-яке). Цей процес повторюється до тих пір, поки остов не стане містити всі вершини (або, що те ж саме, ребро).

У результаті буде побудований остов, що є максимальним . Якщо граф був спочатку не зв'язний, то остов знайдений не буде (кількість вибраних ребер залишиться менше).

Індивідуальне завдання.

Реалізувати алгоритм Прима.

Результати виконання.

Для демонстрації спершу буде показано ручний варіант розв’язку алгоритму покроково.

Оскільки дані задано у файлі вигляді ваг, то нижче наведемо матрицю ваг.

На основі матриці ваг відобразимо граф (рис. 1).