Алгоритм Краскала - побудова оптимального каркаса

На початку 19 століття геометр з Берліна Якоб Штейнер поставив завдання, як з`єднати три села так, щоб їх протяжність була найкоротшою. Згодом він узагальнив цю задачу: потрібно знайти на площині таку точку, щоб відстань від неї до n інших точок було найменшим. У 20 столітті продовжилася робота над цією темою. Було вирішено взяти кілька точок і з`єднати їх таким чином, щоб відстань між ними була найкоротшим. Це все є окремим випадком досліджуваної проблеми.

"Жадібні" алгоритми

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

Знаходження каркаса мінімальної ваги

Розглянутий алгоритм будує оптимальний каркас графа. Завдання про нього полягає в наступному. Дан неорієнтовані граф без кратних ребер і петель, і на безлічі його ребер задана вагова функція w, яка приписує кожному ребру e число – вага ребра – w (e). Вага кожної підмножини з безлічі ребер визначається сумою ваг його ребер. Потрібно знайти каркас самого малого ваги.

Опис

Алгоритм Краскала працює так. Спочатку всі ребра вихідного графа розташовуються в порядку зростання ваг. Спочатку каркас не містить жодного ребра, але включає всі вершини графа. Після чергового кроку алгоритму до вже побудованої частини каркаса, яка є остовне лісом, додається одне ребро. Воно вибирається не довільно. Всі ребра графа, які не належать каркасу, можна назвати червоними і зеленими. Вершини кожного червоного ребра знаходяться в одній компоненті зв`язності споруджуваного ліси, а вершини зеленого – в різних. Тому якщо додати туди червоне ребро, з`являється цикл, а якщо зелене – в отриманому після цього кроку ліс компонент зв`язності буде менше на одну. Таким чином, до отриманого побудови можна додати жодне червоне ребро, але будь-яке зелене ребро додати можна, щоб отримати ліс. І додається зелене ребро з мінімальною вагою. У підсумку виходить каркас найменшої ваги.

Реалізація

Позначимо поточний ліс F. Він розбиває множину вершин графа на області зв`язності (їх об`єднання утворює F, і вони попарно не перетинаються). У червоних ребер обидві вершини лежать в одній частині. Part (x) – функція, яка для кожної вершини x повертає ім`я частини, до якої належить x. Unite (x, y) – це процедура, яка будує нове розбиття, що складається з об`єднання частин x і y і всіх інших частин. Нехай n – число ребер графа. Всі ці поняття включені в алгоритм Краскала. Реалізація:

1. Упорядкувати все ребра графа від 1-го до n-го по зростанню ваг. (ai, bi – вершини ребра з номером i).

2. for i = 1 to n do.

3. 
   
   
   

   x: = Part (ai).

4. y: = Part (bi).

5. If x не дорівнює y then Unite (x, y), включити в F ребро з номером i.

Коректність

Нехай T – каркас вихідного графа, побудований за допомогою алгоритму Краскала, а S – його довільний каркас. Потрібно довести, що w (T) не перевищує w (S).

Нехай M – безліч ребер S, P – безліч ребер T. Якщо S не дорівнює T, то знайдеться ребро et каркаса T, що не належить S. Приєднаємо et до S. Утворюється цикл, назвемо його C. Видалимо з C будь ребро es, що належить S. Вийде новий каркас, тому що і ребер, і вершин у ньому стільки ж. Його вага не перевершує w (S), так як w (et) щонайбільше w (es) в силу алгоритму Краскала. Цю операцію (заміну ребер S на ребра T) будемо повторювати до тих пір, поки не отримаємо Т. Вага кожного наступного отриманого каркаса не більш ваги попереднього, звідки випливає, що w (T) максимум, ніж w (S).

Також коректність алгоритму Краскала випливає з теореми Радо-Едмондса про матроід.

Приклади застосування алгоритму Краскала

Дан граф з вершинами a, b, c, d, e і ребрами (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (d, e). Ваги ребер показані в таблиці і на малюнку. Спочатку споруджуваний ліс F містить всі вершини графа і не містить жодного ребра. Алгоритм Краскала спочатку додасть ребро (a, e), так як вага у нього найменший, і вершини a і e знаходяться в різних компонентах зв`язності лісу F (ребро (a, e) є зеленим), потім ребро (c, d), тому що у цього ребра найменшу вагу з ребер графа, що не належить F, і воно є зеленим, потім з тих же причин додається ребро (a, b). А ось ребро (b, e) пропускається, хоч у нього і найменшу вагу з решти ребер, тому що воно червоне: вершини b і e належать одній компоненті зв`язності лісу F, тобто якщо додати до F ребро (b, e), утворюється цикл. Потім додається зелене ребро (b, c), пропускається червоне ребро (c, e), а потім d, e. Таким чином, послідовно додаються ребра (a, e), (c, d), (a, b), (b, c). З ніхера і складається оптимальний каркас вихідного графа. Так працює в даному випадку алгорітмКраскала. Приклад це показав.

На малюнку показаний граф, що складається з двох компонент зв`язності. Жирними лініями показані ребра оптимального каркаса (зелені), побудованого за допомогою алгоритму Краскала.

На верхньому малюнку зображений вихідний граф, а на нижньому – каркас мінімальної ваги, побудований для нього за допомогою розглянутого алгоритму.

Послідовність доданих ребер: (1,6) - (0,3), (2,6) або (2,6), (0,3) – значення не має- (3,4) - (0,1), (1,6) або (1,6), (0,1), також байдуже (5,6).

Алгоритм Краскала знаходить практичне застосування, наприклад, для оптимізації прокладок комунікацій, доріг у нових мікрорайонах населених пунктах кожної країни, а також в інших випадках.