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

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

На початку 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).

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