Реферати українською » Математика » Побудова мінімального остовного дерева графа методом Прима


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

Страница 1 из 2 | Следующая страница

>Пояснительная записка

до курсовому проекту

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


Запровадження

Під час проектування залізниць, ліній електропередач та інших ліній комунікації виникають проблеми побудови мережі з мінімальними витратами. Теоретично графів таке завдання успішно вирішується через побудову мінімальногоостовного дереванеориентированного графа. Це завдання має низку методів рішення. Одне з них – алгоритм Прима. Сутність цього методу залежить від послідовному додаванні до кістяку мінімального, «безпечного» ребра (ребра, яке утворює циклу). У цьому роботі представлена програма, що базується на алгоритмі Прима, яка обчислює мінімальнеостовное деревонеориентированного графа і робить візуалізацію графа.


1. Історична довідка

Відомий алгоритм побудови мінімальногоостовного дерева перегукується зВойтехуЯрнику (>VojtechJarnik) [1930]. Він уже відомий під назвою алгоритму Прима (>RobertPrim). Р. прим незалежно відЯрника придумав їх у 1956 і представив більш докладний та детальне опис, ніж першовідкривач. Вкотре цей алгоритм відкривЭдсгерДейкстра (>EdsgerWybeDijkstra) в 1958 року, але назва залишилося заПримом, т. до. уДейкстри вже було алгоритм з іменем Тараса Шевченка (пошук найкоротших шляхів в орієнтованому графі). Цей алгоритм можна зарахувати до групі алгоритмів, побудованих на нарощуванні дерева: є тільки одна нетривіальна компонента (інші є одиночні вершини), і її поступово нарощується додаванням «безпечних» ребер. Час роботи алгоритмуДжарника-Прима може становитиO (>E+VlogV) під час використанняфибоначчиевих від куп.

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

Розглянемо загальну схему роботи алгоритмів побудови мінімальногоостовного дерева з допомогою жадібною стратегії. Отже, нехай дано зв'язнийнеориентированний граф G (V; E) з n вершинами і вагова функція w: ER.

Зазначений остов будується поступово. Алгоритм використовує певнийациклическийподграф А вихідного графа 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: AA ∪ {(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:dokey[u] ← ∞

4:key[>r] ← 0

5:p[>r] =NIL

6:while (поки) 0

7:do u EXTRACT-MIN()

8:foreach (кожної) вершини v Adj(u)

9:doif v і w (u, v) <key[v]then

10:p[v] ← u

11:key[v] ← w (u, v)

На малюнках 1–8 показано схема роботи алгоритму Прима з коренемr.


Малюнок 1 – Початкова фаза. Мінімальний покриває ліс складається з кореня і порожнього безлічі ребер

Малюнок 2 –Ребро із 6 є мінімальним ребро, що з'єднує корінь з іншими вершинами. Додаємо його до мінімального кістяку.

Малюнок 3 – Наступне безпечне ребро із 11. Додаємо його


>Рис. 4

Малюнок 5

Малюнок 6

Малюнок 7


Малюнок 8 –Ребра із 17, 19 і 25 – не безпечні. Їх кінці лежать у однієї компонентісвязности.Ребро із 21 – безпечне, тому додаємо його. Мінімальнаостовное дерево побудовано.

Час роботи алгоритму Прима залежить від цього, як реалізована чергу, з пріоритетами. Якщо двійкову купу, ініціалізацію в рядках 1–4 можна виконати під часO(V). Далі цикл виконується |V| разів, і кожна операціяEXTRACT-MIN займає часO(V>logV). Циклfor в рядках 8–11 виконується загаломO(E), оскільки сума ступенів вершин графа дорівнює 2|E|. Перевірку приналежності в рядку 9 можна виконати під часO(1), якщо зберігати стан ще як і бітовий вектор розміру |V|.Присваивание в рядку 11 він розуміє виконання операції зменшення ключа (>DECREASE-KEY), яка длядвоичной купи можуть виконати під часO(logV). Отже всього отримуємоO (V>logV+E>logV)=>O(E>logV).

Кращу оцінку можна було одержати, якщо використовуватифибоначчиеви купи. З допомогоюфибоначчиевих від куп можна виконати операціюEXTRACT-MIN за облікове часO(logV), а операціюDECREASE-KEY – за облікове часO(1). І тут сумарне час алгоритму Прима становитимеO (E+V>logV).


4. Упорядкування програми

алгоритмостовной дерево програма

Інтерфейс програми (додаток А, У) має бути таким. Спочатку користувач вводить порядок графа, щоб програма могла сформувати таблицю введення даних (матриця терезів) з певним кількістю рядків і шпальт. У цьому все кнопки, крім кнопки «Зробити таблицю» недоступні для користувача. Потім користувач виводить на таблицю дані, цьому він може залишати порожні осередки в таблиці. Програма буде інтерпретувати це як відсутність ребра між вершинами. Коли дані буде введено, потрібно натиснути кнопку «>Рассчитать дерево», що створення програмою таблиці стане активної. Програма розрахує матрицю терезів для мінімальногоостовного дерева і намалює шуканий граф (довжини ребер графа ні відповідати матриці терезів). У цьому таблиця введення і всі кнопки, крім кнопки «Продовжити», стануть недоступні для користувача. При натисканні з цього єдину активну кнопку програма піде на вихідне стан.

Тепер у тому, як програма реалізує алгоритм Прима.

Спочатку програма створює якийсь масивa[10] [10] (передбачається, що кількість вершин графа менше, або одно 10). Цей масивинициализируется: кожномуa[i] [j] присвоюється 1000 (передбачається, що максимальна довжина ребра менше 1000). Потім дані з таблиці введення копіюються в масив. У цьому тоді як осередку таблиці щось міститься у масив щось копіюється. Потім робиться цикл, який переривається тільки тоді ми, коли всі елементи масиву стануть знову рівні 1000. Як працює цикл? Спочатку перебуває мінімальний елемент масиву (в галузі вище головною діагоналі матриці введення). Він запам'ятовується (зміннаbuf) і його присвоюється 1000. Відповідно до алгоритму Прима, якщо ребро підходяще мінімальний елемент викреслюється, а цикл починається початку. Підходяще ребро чи ні? Відповідь це питання перебуває так. Складається масив в n елементів. Кожен елемент дорівнює 1 чи 0. Коли вершина входить у дерево, в елемент масиву з її номером записується 1 (спочатку всі елементи масиву, крім першого рівні 0). Щоб співаку визначити підходяще ребро чи ні, треба подивитися, містяться одиниці в масиві (номери елементів рівні номерам вершин ребра). Якщо номерам вершин ребра відповідають обидві одиниця, отже, ребро не підходяще. Якщо це основна умова не виконується – ребро підходяще. Алгоритм перестає працювати, коли всі вершини включені у новий граф.

Окремо можна назвати процедуру малювання графа. Програма створює двомірний масив координат вершин графа (>krug [2] [10]). Вершини розташовуються на окружності на рівній відстані друг від друга. Такий спосіб дуже зручний, бо ні треба тривожитися, що ребра будуть нашаровуватися одне інше.

 

5. Тестування програми

Тестування програми проводилося практично на всіх варіантах матриці терезів. У процесі тестування помилок нема.

Програма тестувалися наступних прикладах:

Матриця терезів

2 4
3

>Видан результат

2
3

Матриця терезів

2 3

>Видан результат

2 3

Матриця терезів

3 5
4
1

>Видан результат

3
4

Матриця терезів

6 5 3
2 5
6

>Видан результат

5 3
2

Матриця терезів

5 6 4 7 8 5
8 5 19 6 9
2 8 7 10
7 3 8
6 7
5

>Видан результат

5 4 5
2
3
6
Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація