Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Побудова мінімального кістякового дерева
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Теорія алгоритмів
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “ Львівська політехніка ”
Кафедра САП
/
Звіт
до лабораторної роботи № 12
Побудова мінімального кістякового дерева
з курсу «Теорія алгоритмів»
Мета роботи
Мета роботи – отримати навики використання алгоритмів побудови мінімального кістякового дерева в графах.
Теоретичні відомості
2.1. Мінімальне кістякове дерево (або мінімальне покриваюче дерево)
у зв’язаному, зваженому неорієнтованому графі – це кістякове дерево цього графу, яке має мінімально можливу вагу, де під вагою дерева розуміється сума ваг його вхідних ребер.
В загальному випадку, задачу можна сформулювати так: маємо зв’язний, неорієнтований граф з вагами на ребрах G(V, E), у якому V – множина вершин (контактів), а E – множина усіх можливих попарних з’єднань (ребер). Нехай для кожного ребра (U, V) однозначно визначено деяке дійсне число W(u, v) – його вага (довжина або вартість з’єднання). W – називається ваговою функцією. Задача полягає у знаходженні такого зв’язного ациклічного графу T є G , яке містить усі вершини, у яких сумарна вага ребер буде мінімальною.
Властивості мінімальних кістякових дерев:
Максимальне кістякова дерево можна знайти, використовуючи алгоритм Прима (наприклад, замінивши ваги усіх ребер на протилежні: алгоритм не потребує, щоб ваги ребер були тільки додатними величинами).
Мінімальне кістякове дерево є єдиним, якщо вага усіх ребер є різною. Інакше може існувати декілька мінімальних кістякових дерев (вибір одного з них за алгоритмом Прима, залежить від порядку перегляду ребер (вершин) з однаковими вагами).
Мінімальне кістякове дерево є кістяковим деревом з мінімальною вагою найважчого ребра. Цю властивість використовують при застосуванні алгоритму Крускала.
Критерій мінімального кістякового дерева: кістяк є мінімальним тоді і тільки тоді, коли для будь-якого ребра, яке не належить кістяку, цикл, утворений цим ребром, яке додається до кістяку, не містить ребер, важчого за це ребро.
Загальновідомими є наступні алгоритми для знаходження мінімального кістякового дерева:
алгоритм Прима;
алгоритм Крускала;
алгоритм Борувки.
2.2. Алгоритм Прима
Алгоритм Прима — алгоритм побудови мінімального кістякового дерева зваженого зв’язного неорієнтованого графу. Алгоритм вперше був відкритий у 1930 році чеським математиком Войцехом Ярником, потім був перевідкритий Робертом Примом у 1957 році, і незалежно від них, Е. Дейкстрою у 1959 році.
Алгоритм Прима володіє властивістю, що ребра в множині А завжди утворюють єдине дерево. Дерево починається з довільної кореневої вершини і росте до того часу, доки не охопить всі вершини V. На кожному кроці, до дерева А додається “легше” ребро, яке з’єднує дерево і окрему вершину з частин графу, які залишилися. Це правило додає тільки найлегші для А ребра; тобто, по завершенню алгоритму, ребра в А утворюють мінімальне кістякове дерево. Дана стратегія є жадібною, оскільки на кожному кроці до дерева додається ребро, яке вносить мінімально можливий вклад в загальну вагу.
2.3. Алгоритм Крускала
Алгоритм Крускала об’єднує вершини графу у декількох зв’язних компонентах, кожна з яких є деревом. На кожному кроці з усіх ребер, які з’єднують з різних компонент зв’язності, вибирається ребро з найменшою вагою. Необхідно перевірити, чи воно є безпечним. Безпечність ребра гарантується теоремою про безпечність ребра. Так як ребро є найлегшим з усіх ребер, виходячи з даної компоненти, воно буде безпечним. У алгоритмі Крускала вибір на кожному кроці безпечного ребра реалізується таким чином: усі ребра графу G перебираються за зростанням ваги. Для чергового ребра перевіряється, чи не лежать кінці ребра в різних компонентах зв’язності, і якщо так, то ребро додається і компоненти об’єднуються.
2.4. Алгоритм Борувки
Нехай дано зв’язний неорієнтований G(V;E) і на ньому задана вагова функція. Нехай А – проміжний кістяковий ліс для графу V. На першому кроці A складається з усіх вершин G і пустої множини ребер. Спочатку, на кожній фазі алгоритму Борувки, для кожної компоненти зв’язності проміжного кістякового лісу, вибирається лідер («leader» node) або корінь – вершина, яка співставляється кожній компоненті. У найпростішому випадку, це можна зробити за допомогою обходу А в глибину: вершина, з якої починається обхід наступних компонент, буде її лідером.
3. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Що таке мінімальне кістякове дерево?
Це дерево яке має мінімально можливу вагу і включає всі вершини вихідного дерева
2. Що таке алгоритм Прима?
Алгоритм Прима — алгоритм побудови мінімального кістякового дерева зваженого зв’язного неорієнтованого графу
3. Правила виконання алгоритму Прима.
На кожному кроці, до дерева А додається “легше” ребро, яке з’єднує дерево і окрему вершину з частин графу, які залишилися.
4. Як працює алгоритм Прима?
Дерево починається з довільної кореневої вершини і росте до того часу, доки не охопить всі вершини V. На кожному кроці, до дерева А додається “легше” ребро, яке з’єднує дерево і окрему вершину з частин графу, які залишилися. Це правило додає тільки найлегші для А ребра; тобто, по завершенню алгоритму, ребра в А утворюють мінімальне кістякове дерево.
5. Що потребує в якості вхідних даних алгоритм Прима?
1) масив, матриця суміжності
2) бінарна піраміда, списки суміжності
3) піраміда фібоначі, списки суміжності
6. Яка складність алгоритму Прима?
Спосіб представлення графу і пріорітетної черги
Асимптотика
Масив d, списки суміжності (матриця суміжності)
O(V2)
Бінарна піраміда, списки суміжності
O((V + E) log V) = O(E log V)
Піраміда Фібоначчі, списку суміжності
O(E + V log V)
7. Яка складність алгоритму Борувки?
O(E) – кількість ребер
4. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ (варіант 17)
Побудувати граф на основі карти обласного центру України. Вершинами позначити районні центри, ваги ребер проставити у відповідності до відстані (км). Виконати алгоритм Прима.
Рівненьська область
Рис. 1. Граф
Табл1. Матриця ваг графа на рис.1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
A
0
64,7
102
0
0
0
0
0
0
0
0
0
0
0
0
0
B
64,7
0
54,8
33,5
85,7
0
0
0
0
0
0
0
0
0
0
0
C
102
54,8
0
67,8
0
109
98,3
151
0
0
153
0
0
0
0
0
D
0
33,5
67,8
0
52
48
0
0
0
0
0
0
0
0
0
0
E
0
85,7
0
52
0
75,3
0
0
0
122
0
0
0
0
0
0
F
0
0
109
48
75,3
0
30,2
0
30,8
72,4
0
0
0
0
0
0
G
0
0
98,3
0
0
30,2
0
36,2
62,4
0
0
0
0
0
0
0
H
0
0
151
0
0
0
36,2
0
33,6
0
55,7
13,7
0
0
0
0
I
0
0
0
0
0
30,8
62,4
33,6
0
39,3
0
42,4
0
0
35,5
0
J
0
0
0
0
122
72,4
0
0
39,3
0
0
0
0
0
72,3
0
K
0
0
153
0
0
0
0
55,7
0
0
0
0
25,1
20,1
0
0
L
0
0
0
0
0
0
0
13,7
42,4
0
0
0
0
51,5
36,8
0
M
0
0
0
0
0
0
0
0
0
0
25,1
0
0
30
0
49,5
N
0
0
0
0
0
0
0
0
0
0
20,1
51,5
30
0
76,5
53,7
O
0
0
0
0
0
0
0
0
35,5
72,3
0
36,8
0
76,5
0
117
P
0
0
0
0
0
0
0
0
0
0
0
0
49,5
53,7
117
0
Застосовую алгоритм прима для побудови мінімального кістякового дерева.
За корінь вибираю вершину А.
Крок
Опис кроку
Вага ребра
1
A – B
64.7
2
B – C
54.8
3
B – D
33.5
4
D – E
52
5
D – F
48
6
F – G
30.2
7
F – I
30.8
8
I – H
33.6
9
I – J
39.3
10
I – O
35.5
11
H – L
13.7
12
H – N
45.2
13
N – K
20.1
14
K – M
25.1
15
M – P
49.5
Результат роботи алгоритму можна побачити на рис. 2.
Рис. 2. Мінімальне кістякове дерева графа на рис. 1.
ВИСНОВОК: на основі лабораторної роботи я отримав навики використання алгоритмів побудови мінімального кістякового дерева в графах.
29.09.2014 20:09-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора