Остов графа найменшої ваги, дискретна математика
Оскільки остов неориентированного графа визначено неоднозначно, виникає завдання вибору остова, оптимального в тому чи іншому сенсі. Наприклад, граф являє собою мережу доріг. Виникає запитання прокладки маршруту найменшої довжини, що проходить через дані населені пункти. Математично подібного роду завдання ставиться таким чином. Нехай дано розмічений (зважений) граф, тобто граф, кожному ребру якого приписана вага. Потрібно вибрати остов найменшої ваги.
Перш ніж розглядати конкретні алгоритми, уявімо собі завдання перерахування всіх кістяків зв'язкового графа. Процедуру можна уявити як послідовне нарощування ребер споруджуваного дерева. Якщо обрані k ребер вихідного графа, з яких не можна скласти циклу, ми отримуємо підграф, що є неорієнтованим лісом. До цього лісі можна додати ще одне ребро з решти, переконавшись, що нове ребро не породжує циклів з іншими. Процедура триває до тих пір, поки не набереться n - 1 ребро. В результаті ми отримаємо граф, що містить n - 1 ребро і не має циклів. Якщо це був би ліс, то кількість ребер в ньому було б дорівнює кількості вершин мінус кількість компонент. Кількість n - 1 може вийти тільки в тому випадку, коли підграф остовно і та має одну компоненту зв'язності, тобто є деревом.
На кожному кроці нарощування поддерева існує кілька можливостей додавання чергового ребра. В результаті на кожному кроці наше рішення розгалужується, і ми фактичними скі отримуємо так зване дерево рішень. Листя цього дерева, тобто вершини ступеня 1, являють собою конкретні рішення. Сукупність усіх листя є сукупність всіх кістяків розглянутого графа.
Пошук остова найменшого ваги можна уявити як оптимальний спуск з кореня дерева кістяків в лист. На кожному кроці слід приймати рішення, яке ребро з допустимих слід вибрати. Особливість цього завдання полягає в тому, що оптимальний вибір ребра на кожному кроці гарантує оптимальність остаточного результату.
У цій процедурі зручно вважати, що нарощуваний підграф спочатку включає всі вер- шини, а покрокова процедура полягає в послідовній склеюванні компонент подграфа-лісу за допомогою ребер вихідного графа. Тоді стартовий граф являє собою n ізольованих вершин. На кожному кроці процесу нарощування додається одне ребро і кількість компо- нент зменшується на одну. На кінцевому (n - 1) -му кроці кількість доданих ребер стане n - 1, а кількість компонент скоротиться до однієї.
Розглянемо два непересічних подграфа T1 = (V1. E1) і T2 = (V2. E2) графа G. Введемо для них характеристику
Теорема 6.3. Нехай підграф-ліс T, складається з компонент T1. T2. Tk і підпорядкований деякого остову найменшої ваги. З компонент T2. T3. Tk виберемо таку компоненту Tj. на якій Δ (T1, Tj) мінімально, причому ця величина реалізується на ребрі γ *, що з'єднує деяку вершину компоненти T1 з деякою вершиною компоненти Tj. Тоді підграф "T плюс γ *" підпорядкований деякого остову найменшої ваги.
◀ Розглянемо кістяк T 'найменшої ваги, що містить T. В T' є ланцюг α, що з'єднує кінці ребра γ *. Якщо саме це ребро не входить в T ', то його додавання до графа дає цикл γ + α. У ланцюзі α є перше ребро γ, що виходить за межі компоненти T1 (починаючи з того кінця ланцюга, який знаходиться в T1). За умовою вибору вага ребра γ не менш ваги ребра γ *. Видалення ребра γ розриває утворився цикл і зберігає зв'язність T '. Отже, заміна γ на γ * призводить до кістяк T '', що відрізняється від T 'всього одним ребром. Оскільки c (γ *) c (γ), вага кістяка T '' не перевищує вагу остова T 'і є найменшим, тобто T '' - остов найменшої ваги. ▶
Доведена теорема є теоретичною основою декількох алгоритмів вибору остова найменшої ваги. Відзначимо, що принцип вибору, сформульований в теоремі, володіє деякою свободою: як компоненти T1 можна вибирати будь-яку з наявних. Довільній такого вибору означає, що і конкретний алгоритм побудови кістяка можна реалізувати по-різному. Розглянемо два таких алгоритму.
Алгоритм Краскала. У цьому алгоритмі мінімізація виконується по обом компонентам T1 і T1. Насправді немає потреби перебирати всілякі пари компонент і визначати на якій парі величина Δ мінімальна. Можна просто перебрати всі ребра графа і серед них вибрати ребро найменшої ваги, яке, по-перше, не входить в T, а по-друге, не утворює циклу з вже наявними в T ребрами. Тоді це буде ребро, що з'єднує якісь два компоненти графа T.
Коротко алгоритм Краскала можна описати так.
1. Починаємо з остовного графа T без ребер.
2. Всі ребра графа упорядковуємо по зростанню ваги.
3. Вибираємо чергове ребро з упорядкованого списку і перевіряємо, чи утворює воно цикл з уже відібраними. Якщо так, пропускаємо його і повторюємо пункт. Якщо немає, переходимо до наступного пункту.
4. Перевіряємо, якщо відібрано n - 1 ребро, то процес припиняємо. Інакше повертаємося до попереднього пункту.
У викладеній стратегії два вузьких місця: сортування ребер по зростанню і перевірка на появу циклів при додаванні чергового ребра. Перша проблема зводиться до вибору ефективного алгоритму сортування. Відзначимо, що повна сортування всіх ребер насправді не потрібна. Відбиратися буде n - 1 ребро, в той час як повний граф містить набагато більше ребер: n (n - 1) / 2. Сортування можна звести до вибору на кожному кроці найкращого з решти ребер. Ця проблема показує, що алгоритм Краскала найбільш ефективний для графів з невеликим числом ребер (того ж порядку, що і число вершин).
Зазначену процедуру перевірки на цикли можна зробити більш ефективною, якщо в позначку вершин включати не тільки ранг, а й додаткову інформацію, що дозволяє по вершині відновити все поддерево.
Алгоритм Прима. У цьому алгоритмі дерево T1 фіксоване, інші компоненти до кінця залишаються поодинокими вершинами. Технічно цю стратегію можна реалізувати наступним чином. Кожній вершині x на поточному кроці відповідає мітка, що містить вершину y дерева T1. найближчу до x, і вага β ребра, що з'єднує y з x. Якщо вершина x не має ребер, що зв'язують її з T1. той йому приписується спеціальна мітка (0, ∞). На k-му кроці проглядаються всі вершини, що не належать до T1 і серед них вибирається вершина xk. для якої вага βk найменший. Ребро, що з'єднує xk з T1. заноситься в список відібраних ребер. Потім для всіх вершин x ∈ / T1 вага β порівнюється з вагою ребра і якщо останнє менше, мітка вершини x оновлюється. Процедура зупиняється, коли буде відібрано n-1 ребер або n вершин.