1 Постановка завдання
Нехай заданий зв'язний неорієнтований граф [math] G = (V, E) [/ math] з вагами ребер [math] f (e) [/ math]. Подграф, що є деревом і проходить через всі вершини [math] G [/ math]. називається основним деревом. Кістяк називається мінімальним. якщо сумарна вага його ребер є мінімальним серед всіх остовних дерев.
2 Варіанти завдання
Якщо вихідний граф [math] G [/ math] незв'язних, то набір мінімальних остовних дерев для всіх компонент зв'язності називається мінімальним остовне лісом (Minimum Spanning Forest, MSF).
Для графа з цілочисельними вагами можливе використання спеціальних прийомів, таких як сортування за розрядами. що призводить до алгоритмів, вирішальним завдання за лінійний час.
У розподіленої задачі може бути присутнім додаткова вимога, що обмін даними відбувається тільки уздовж ребер графа.
3 Властивості завдання
Ваги. Рішення завдання залежить не від значень ваг, а від їх порядку. Таким чином, замість завдання ваг можна задати порядок - предикат «менше або дорівнює» на безлічі пар ребер графа. З цієї причини можна без обмеження спільності вважати, що все ваги ребер різні - для цього слід упорядкувати ребра спочатку за вагою, а потім за номером. Крім того, до вихідних ваг можна застосувати будь-яку зростаючу функцію і це не призведе до зміни рішення. Як наслідок, можна вважати, що всі ваги знаходяться в заданому інтервалі, наприклад, [math] [0, 1] [/ math].
Існування і єдиність. Мінімальний опорний ліс завжди існує, а якщо все ваги ребер різні, то він єдиний. Як уже зазначалося, завжди можна зробити ваги ребер різними. Якщо умова різних ваг не виконується, легко побудувати приклад, в якому буде існувати більш одного мінімального остовного дерева.
Схлопування фрагментів. Нехай [math] F [/ math] - фрагмент мінімального остовного дерева графа [math] G [/ math]. а граф [math] G '[/ math] отримано з [math] G [/ math] склеюванням вершин, що належать [math] F [/ math]. Тоді об'єднання [math] F [/ math] і мінімального остовного дерева графа [math] G '[/ math] дає мінімальне кістяк вихідного графа [math] G [/ math].
Мінімальна ребро фрагмента. Нехай [math] F [/ math] - фрагмент мінімального остовного дерева і [math] e_F [/ math] - ребро найменшої ваги, що виходить з [math] F [/ math] (тобто рівно один його кінець є вершиною з [math] F [/ math]). Якщо ребро [math] e_F [/ math] єдино, то воно належить мінімального остовного дерева. На цій властивості засновані алгоритм Борувка і алгоритм Прима.
Мінімальна ребро графа. Якщо [math] e ^ * [/ math] - єдине ребро графа з мінімальною вагою, то воно належить мінімального остовного дерева. На цій властивості заснований алгоритм Круськала.
Асоціативність по ребрах. Нехай [math] MSF (E) [/ math] - мінімальний кістяк ліс графа з ребрами [math] E [/ math]. тоді
[Math] MSF (E_1 \ cup E_2 \ cup \ dots \ cup E_k) = MSF (MSF (E_1) \ cup MSF (E_2) \ cup \ dots \ cup MSF (E_k)). [/ Math]
Кількість ребер остовного лісу для графа з [math] n [/ math] вершинами і [math] c [/ math] компонентами зв'язності одно [math] n-c [/ math]. Це властивість може використовуватися для більш швидкого завершення роботи алгоритмів, якщо число компонент зв'язності відомо заздалегідь.
4 Опис вхідних та вихідних даних
Вхідні дані. зважений граф [math] (V, E, W) [/ math] ([math] n [/ math] вершин [math] v_i [/ math] і [math] m [/ math] ребер [math] e_j = ( v ^ _, v ^ _) [/ math] з вагами [math] f_j [/ math]).
Обсяг вхідних даних. [Math] O (m + n) [/ math].
Вихідні дані. список ребер мінімального остовного дерева (для незв'язного графа - список мінімальних остовних дерев для всіх компонент зв'язності).
Обсяг вихідних даних. [Math] O (n) [/ math].
5 Алгоритми рішення задачі
Існує три класичні підходи до вирішення завдання:
У всіх випадках послідовна складність алгоритму [math] O (m \ ln m) [/ math] при використанні звичайних структур даних. (Позначення: [math] m [/ math] - число ребер, [math] n [/ math] - число вершин.)
Всі інші алгоритми, як правило, є варіацією на тему одного з трьох перерахованих, або їх комбінацією.
- Алгоритм GHS (Gallager, Humblet, Spira) [6] і його наступні версії [7] [8] є розподіленим варіантом алгоритму Борувка. Це алгоритм зазвичай використовується для автоматичного розподіленого побудови остовного дерева мережею комутаторів.
- Алгоритм Габова і ін. [9] використовує фібоначчійовий купу для упорядкування ребер в алгоритмі Борувка. Складність [math] O (m \ ln \ beta (m, n)) [/ math].
- Алгоритм Фредман і Уилларда [10] призначений для графів з цілочисельними вагами і має лінійну оцінку складності [math] O (m) [/ math]. Використовується алгоритм Прима в поєднанні зі спеціально розробленим алгоритмом купи (AF-heap).
- Алгоритм Каргера і ін. [11] переймається тим в середньому за лінійний час [math] O (m) [/ math]. (Існування детермінованого алгоритму з лінійної оцінкою складності є відкритим питанням.)
Слід зазначити, що алгоритми, які мають асимптотичну складність кращу, ніж [math] O (m \ ln n) [/ math]. як правило, на практиці працюють повільніше класичних алгоритмів: константа в оцінці настільки велика, що виграш від кращої асимптотиці буде помітний тільки на графах дуже великих розмірів.
6 Ресурс паралелізму
- Властивості схлопування фрагментів і мінімального ребра фрагмента дозволяють обробляти фрагменти незалежно. Заснований на цих властивостях алгоритм Борувка володіє найбільшим ресурсом паралелізму серед трьох класичних алгоритмів.
- Асоціативність по ребрах може бути використана для паралелізації алгоритмів Круськала і Прима, які спочатку є суттєво послідовними.
- Використання паралельних алгоритмів сортування ребер графа, або паралельна сортування ребер у кожної вершини або у кожного фрагмента.