Алгоритм Фарбала – побудова оптимального каркасу
На початку 19 століття геометр з Берліна Якоб Штейнер поставив завдання, як з'єднати три села так, щоб їхня довжина була найкоротшою. Згодом він узагальнив це завдання: потрібно знайти на площині таку точку, щоб відстань від неї до n інших точок була найменшою. У 20 столітті продовжилася робота над цією темою. Було вирішено взяти кілька точок і з'єднати їх таким чином, щоб відстань між ними була найкоротшою. Це все є окремим випадком досліджуваної проблеми.
"Жадібні" алгоритми
Алгоритм Краскала відноситься до "жадібних" алгоритмів (їх ще називають градієнтними). Суть таких – найбільший виграш щокроку. Не завжди "жадібні" алгоритми дають найкраще рішення поставленого завдання. Існує теорія, що показує, що з їх застосуванні до певних завдань вони дають оптимальне рішення. Це теорія матроїдів. Алгоритм Краскала відноситься до таких завдань.
Знаходження каркасу мінімальної ваги
Розглянутий алгоритм будує оптимальний каркас графа. Завдання про нього полягає у наступному. Даний неорієнтований граф без кратних ребер і петель, і на його ребер задана вагова функція w, яка приписує кожному ребру e число – вага ребра – w(e). Вага кожної підмножини з множини ребер визначається сумою ваг його ребер. Потрібно знайти каркас найменшої ваги.
Алгоритм Краскала працює так. Спочатку все ребра вихідного графа розташовуються у порядку зростання ваг. Спочатку каркас не містить жодного ребра, але включає всі вершини графа. Після чергового кроку алгоритму до вже побудованої частини каркаса, яка є кістяковим лісом, додається одне ребро. Воно вибирається не довільно. Усі ребра графа, які не належать каркасу, можна назвати червоними та зеленими. Вершини кожногочервоного ребра знаходяться в одній компоненті зв'язності лісу, що будується, а вершини зеленого - в різних. Тому, якщо додати туди червоне ребро, з'являється цикл, а якщо зелене – в отриманому після цього кроку лісі компонент зв'язності буде менше на одну. Таким чином, до отриманої побудови не можна додати жодне червоне ребро, але будь-яке зелене ребро можна додати, щоб отримати ліс. І додається зелене ребро із мінімальною вагою. У результаті виходить каркас найменшої ваги.
Реалізація
Позначимо поточний ліс F. Він розбиває безліч вершин графа області зв'язності (їх об'єднання утворює F, і вони попарно не перетинаються). У червоних ребер обидві вершини лежать у одній частині. Part(x) – функція, яка кожної вершини x повертає ім'я частини, куди належить x. Unite(x,y) – це процедура, яка будує нове розбиття, що з об'єднання частин x і y та інших частин. Нехай n - Число ребер графа. Всі ці поняття включені до алгоритму Краскала. Реалізація:
Упорядкувати всі ребра графа від 1-го до n-го за зростанням ваг. (ai, bi – вершини ребра із номером i).
для i = 1 to n do.
Якщо f не дорівнює 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).
Алгоритм Краскала знаходить практичне застосування, наприклад для оптимізації прокладок комунікацій, доріг у нових мікрорайонах населених пунктах кожної країни, а також в інших випадках.