Зміст
Введення
1. Постановка завдання
2. Методи вирішення даної проблеми
3. Опис алгоритму Краскала
4. Приклад роботи алгоритму Краскала
5. Код програми
6. Огляд роботи програми
Висновок
Список використаної літератури
Введення
Мінімальним Остовним деревом (МОД) зв'язкового зваженого графа називається його зв'язний подграф, що складається з усіх вершин вихідного дерева і деяких його ребер, причому сума ваг ребер максимально можлива. Якщо вихідний граф несвязен, то описувану нижче процедуру можна застосовувати по черзі до кожної його компоненті зв'язності, отримуючи тим самим мінімальні остовного дерева для цих компонент.
Задача про знаходження мінімального остовного дерева часто зустрічається в подібній постановці: є n міст, через які можна прокласти маршрут так, щоб можна було дістатися з будь-якого міста в будь-який інший (безпосередньо або через інші міста). Потрібно знайти такий маршрут, щоб вартість проїзду була максимальною.
Ця задача може бути сформульована в термінах теорії графів як задача про знаходження мінімального остовного дерева в графі, вершини якого являють міста, ребра - це пари міст, між якими є маршрут, а вага ребра дорівнює вартості проїзду по відповідному маршрутом.
Існує кілька алгоритмів для знаходження мінімального остовного дерева. Деякі найбільш відомі з них перераховані нижче:
В· Алгоритм Прима;
В· Алгоритм Краскала;
В· Алгоритм Борувкі.
1. Постановка завдання
Нехай є зв'язний неорієнтовані граф G, на ребрах якого задана вагова функція c (e). Зв'язний подграф графа G, що є деревом і містить всі його вершини, називають покриваючим деревом (spanning-tree) цього графа (іноді використовують термін остовне дерево або остов). Вагою остовного дерева будемо вважати суму ваг усіх його ребер. Тоді виникає задача про знаходження максимального покриває дерева, тобто такого, що його вага найбільший, або дорівнює вазі будь-якого з покриваючих дерев для даного графа. Будемо позначати найбільше покриває дерево графа G як MAX (G).
2. Методи вирішення даної проблеми
Остовним деревом графа називається дерево, що містить всі вершміни V графа. Вартість остовного дерева обчислюється як сума вартостей всіх ребер.
Ідея рішення:
Для остовного дерева вірно наступне властивість:
Нехай G = (V, E) - Свизний граф із заданою функцією вартості, визначеної на множині ребер. Позначимо через U підмножину множини вершин V. Якщо (u, v) - таке ребро найбільшої вартості, що u з U і v з V U, тоді для графа G існує остовне дерево максимальної вартості, що містить ребро (u, v)
На цій властивості заснований алгоритм Прима. У цьому алгоритмі будується множина вершин U, з якого "Виростає" остовне дерево. Нехай V = {1,2,. n}. Спочатку U = {1}. На кожному кроці алгоритму знаходиться ребро найменшої вартості (u, v) таке, що u з U і v з V U, потім вершина v переноситься з безлічі V U в безліч U. Процес триває до тих пір, поки безліч U не стане рівним безлічі V.
Деталі реалізації:
Зручно вибрати уявлення у вигляді списку дуг.
Припустимо, необхідно прокласти кабель по території університету, зв'язавши всі його будівлі, так, щоб з кожної будівлі кабель з якого-небудь шляху доходив до будь-якого іншого будівлі. Крім того, припустимо, що треба мінімізувати загальну довжину прокладається кабелю. Якщо розглядати будівлі як вершини, а кабелі між будівлями як ребра, то ця робота з прокладанням кабелю перетворюється в задачу визначення каркаса, що охоплює будівлі території університету, в якому загальна довжина прокладеного кабелю повинна бути мінімальною. Таку задачу називають знаходженням каркаса мінімальної ваги. В нашій роботі довжина прокладеного кабелю повинна бути максимальною.
Визначимо поняття каркаса більш формально. Якщо дана зв'язний неорієнтовані граф G = (V, E), то каркас (Також званий Остовним або стягивающим деревом) T = (V, E '), де E'ГЌE - це зв'язний граф без циклів. Іншими словами, каркас неорієнтованого графа G - це підграф графа G, дерево, містить всі вершини графа. Зрозуміло, що для того, щоб T мало той же набір вершин, що і зв'язний граф G, і щоб T не мало циклів, воно повинно містити рівно | V | -1 ребро.
Припустимо, що для кожного ребра eГЋE існує вагу w (e), причому таку вагу може виражати, наприклад, ціну, довжину або час, необхідний для проходу по ребру (у нашому прикладі - Довжину кабелю між будівлями). У зваженому графі вага подграфа - це сума ваг його ребер. Тоді каркас T максимальної ваги - це каркас G, в якому вага дерева максимальний щодо всіх остовних дерев G.
Якщо граф G незв'язний, він не може мати остовного дерева, але у нього є остовного ліс. Також можна змінити алгоритм знаходження остовного дерева максимальної ваги, щоб на виході отримувати мінімальний остовного ліс.
остовне дерево алгоритм Краскала
В алгоритмі Краскала використовується жадібний підхід до вирішення завдання, тобто в будь-який момент виконання даних алгоритмів існує безліч ребер E ', що представляє підмножину деякого мінімального остовного дерева графа G. На кожному кроці алгоритмів з решти ребер вибирається "найкращий" ребро, що має певні властивості, і додається до формованому каркасу максимальної ваги. Одним з важливих властивостей будь-якого ребра, додається до E ', є його безпека, тобто те, що оновлене безліч ребер E 'буде продовжувати представляти підмножина деякого мінімального остовного дерева.
3. Опис алгоритму Краскала
Алгоритм Краскала може будувати дерево одночасно для декількох компонент зв'язності, які в процесі вирішення об'єднуються в одне пов'язане дерево.
Повний граф задається списком ребер. Перед роботою список ребер сортується за зростанням довжини. На кожному кроці проглядається список ребер, починаючи з ребра, наступного за який увійшов в рішення на попередньому кроці, і до споруджуваного піддерево приєднують то ребро, яке не утворює циклу з ребрами, вже включеними в рішення.
Алгоритм складається з наступної послідовності дій:
1. Створюється список ребер R, що містить довжину ребра, номер вихідної вершини ребра (i), номер кінцевої вершини ребра (j), ознака включення даного ребра в дерево.
2. Даний список впорядковується в порядку зростання довжин ребер.
3. Проглядається список R і вибирається з нього ребро з максимальною довжиною, ще не включене в результуюче дерево і не утворить циклу з вже побудованими ребрами.
4. Якщо всі вершини включені в дерево і кількість ребер на одиницю менше кількості вершин, то алгоритм свою роботу закінчив. В іншому випадку здійснюється повернення до пункту 3.
Або в термінах теорії графів:
Дан граф з n вершинами; довжини ребер задані матрицею. Знайти остовне дерево максимальної довжини.
У задачі Прима-Краскала, яка не здається особливо простий, жадібний алгоритм дає точне оптимальне рішення.
Як відомо (Це легко довести по індукції), дерево з n вершинами має n-1 ребер. Виявляється, кожне ребро потрібно вибирати жадібно (лише б не виникали цикли). Тобто n-1 раз вибирати найкоротший ребро з ще не вибране ребро за умови, що воно не утворює циклу з вже обраними.
А як стежити, щоб нове ребро не утворювало циклу зі старими? Зробити це просто. До побудови дерева забарвимо кожну вершину i у відмінний від інших колір i. При виборі чергового ребра, наприклад (i, j), де i та j мають різні кольори, вершина j і все, пофарбовані в її колір (Тобто раніше з нею з'єднані) перефарбовуються в колір i. Таким чином, вибір вершин різного кольору забезпечує відсутність циклів. Після вибору n-1 ребер всі вершини отримують один колір.
Доведемо, що описаний алгоритм отримує в точно...
