Пояснювальна записка
до курсового проекту
тема: Побудова мінімального остовного дерева графа методом Прима
Введення
При проектуванні залізниць, ліній електропередачі та інших ліній комунікації виникає проблема побудови мережі з мінімальними витратами. В теорії графів така задача успішно вирішується шляхом побудови мінімального остовного дерева неорієнтованого графа. Дана задача має кілька методів рішення. Один з них - алгоритм Прима. Суть цього методу полягає в послідовному додаванні до остову мінімального, В«безпечногоВ» ребра (ребра, яке не утворює циклу). У даній роботі представлена ​​програма, що базується на алгоритмі Прима, яка обчислює мінімальне остовне дерево неорієнтованого графа і робить візуалізацію графа.
1. Історична довідка
Відомий алгоритм побудови мінімального остовного дерева сходить до Войтех Ярніку (Vojtech Jarnik) [1930]. Він більше відомий під ім'ям алгоритму Прима (Robert Prim). Р. Прим незалежно від Ярніка придумав його в 1956 і представив більш докладний і детальний опис, ніж першовідкривач. Ще раз цей алгоритм відкрив Едсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 році, але назва залишилася за приймемо, т. к. у Дейкстри вже був алгоритм з його ім'ям (пошук найкоротших шляхів в орієнтованому графі). Цей алгоритм можна віднести до групи алгоритмів, побудованих на нарощуванні дерева: існує тільки одна нетривіальна компонента (інші представляють собою одиночні вершини), і вона поступово нарощується додаванням В«безпечнихВ» ребер. Час роботи алгоритму Джарніка-Прима може досягати O (E + VlogV) при використанні фібоначчіевих куп.
2. Побудова мінімального остовного дерева
Розглянемо загальну схему роботи алгоритмів побудови мінімального остовного дерева з використанням жадібної стратегії. Отже, нехай дано зв'язний неорієнтовані граф G ( V ; E ) c n вершинами і вагова функція w : < i> E в†’ R .
Бажаємий остов будується поступово. Алгоритм використовує деякий ациклічний підграф А вихідного графа G , який називається проміжним Остовним лісом . Спочатку G складається з n вершин-компонент, не з'єднаних один з іншому ( n дерев з однієї вершини). На кожному кроці в A додається одне нове ребро. Граф A завжди є подграфом деякого мінімального кістяка. Чергове добавляемое ребро e = ( u , v ) вибирається так, щоб не порушити цієї властивості: A в€Є { e } теж повинно бути подграфом мінімального. Таке ребро називається безпечним .
Ось як виглядає загальний алгоритм побудови мінімального остовного дерева:
MST-GENERIC (G, w)
1: A в†ђ 0
2: while (Поки) A не є остовом
3: do знайти безпечне ребро ( u , v ) в€€ E для A
4: A в†ђ A в€Є {( u , v )}
5: return A
За визначенню A , він повинен залишатися подграфом деякого мінімального остову після будь-якого числа ітерацій. Звичайно, головне питання полягає в тому, як шукати безпечне ребро на кроці 3. Зрозуміло, що таке ребро завжди існує, якщо A ще не є мінімальним остовом (будь ребро остова, не входить до A ). Зауважимо, що оскільки A не може містити циклів, то на кожному кроці ребром з'єднуються різні компоненти зв'язності (спочатку всі вершини в окремих компонентах, в кінці A - одна компонента). Таким чином цикл виконується (n-1) раз.
Далі наводиться загальне правило відшукання безпечних ребер. Для цього доведена теорема, яка допоможе знаходити безпечні ребра. Попередньо доведемо маленьку лему:
Лемма: нехай Т - мінімальне остовне дерево. Тоді будь-яке ребро е з T - безпечне.
Док-во: в Т - (N-1) ребро. На кожному кроці Generic-MST ми додавали одне безпечне ребро. Всього виконано (n-1) кроків, отже, всі ребра в T - безпечні по визначенню.
Теорема: Нехай G (V; E) - зв'язний неорієнтовані граф і на безлічі Е визначена вагова функція w. Нехай А - деякий підграф G, що є в той же час подграфом деякого мінімального остовного дерева T. Розглянемо компоненту зв'язності До з А. Розглянемо безліч E (K) ребер графа G, тільки один кінець яких лежить в К. Тоді ребро мінімальної ваги з E (K) буде безпечним.
Док-во: Нехай e = ( u , v ) - мінімальне по вазі ребро з E ( K ). Нехай мінімальний остов T не містить e (в іншому випадку доказуване твердження очевидно з наведеної вище лемі). Т.к. T зв'язний, у ньому існує деякий (єдиний) ациклічний шлях p з u в v , і e замикає його в цикл. Оскільки один з кінців e лежить в K , а інший в V K , в дорозі p існує хоча б одне ребро e ' = ( x , y ), яке володіє тим же властивістю. Це ребро не лежить в A , т. к. в A поки що немає ребер між K і V K . Видалимо з T ребро e ' і додамо e . Так як w ( e ') < w ( e ), ми отримаємо остовне дерево T ', сумарна вага якого менше сумарного ваги T . Таким чином, T не є мінімальним остовом. Суперечність. Отже, T містить e .
У зв'язку з наведеної теоремою введемо наступне
Визначення. Безпечним ребром e щодо деякої компоненти зв'язності До з А назвемо ребро з мінімальною вагою, рівно один кінець якого лежить в К.
3. Алгоритм Прима
Як і алгоритм Краскала, алгоритм Прима відповідає загальній схемі алгоритму побудови мінімального остовного дерева: на кожному кроці ми додаємо до споруджуваного остову безпечне ребро. Алгоритм Прима відноситься до групи алгоритмів нарощування мінімального кістяка: на кожному кроці існує не більше однієї нетривіальною (не складається з однієї вершини) компоненти зв'язності, і кожен до неї додається ребро найменшої ваги, що з'єднує вершини компоненти з рештою вершинами. По теоремі таке ребро є безпечним.
При реалізації треба вміти на кожному кроці швидко вибирати безпечне ребро. Для цього зручно скористатися чергою з пріоритетами (купою). Алгоритм отримує на вхід граф G і його корінь r - вершина, на якій буде нарощуватися мінімальний остов. Всі вершини G , ще не потрапили в дерево, зберігаються в черзі з пріоритетом О©. Пріоритет вершини v визначається значенням key [ v ], яке дорівнює мінімальному вазі ребер, з'єднують v з вершинами мінімального кістяка. Поле p [ v ] для вершин дерева вказує на батька, а для вершин з черги, вказує на ноду дерева, в якою веде ребро з вагою key [ v ] (одне з таких ребер, якщо їх декілька).
Тоді алгоритм Прима виглядає наступним чином:
MST-PRIM ( G , w , r )
1: О© в†ђ V [ G ]
2: foreach (для кожної) вершини u в€€ О©
3: do key [ u ] в†ђ в€ћ
4: key [ r ] в†ђ 0
5: p [ r ] = NIL
6: while (поки) О© в‰ 0
7: do u в†ђ EXTRACT-MIN (О©)
8: foreach (для кожної) вершини v в€€ Adj ( u )
9: do if v в€€ О© і w ( u , v ) v ] then
10: p [ v ] в†ђ u
11: key [ v ] в†ђ w ( u , v )
На малюнках 1-8 показана схема роботи алгоритму Прима з коренем r.
Рисунок 1 - Початкова фаза. Мінімальний покриває ліс складається з кореня і порожнього безлічі ребер
Малюнок 2 - Ребро з вагою 6 є мінімальним ребро, що з'єднує корінь з рештою...
