1. Побудова мінімального кістяка

Анотація: Побудова мінімального кістяка графа: алгоритм Круськала. Завдання про лабіринті і пошук в глибину на неорієнтованому графі. Знаходження найкоротших шляхів з одного джерела: алгоритм Дейкстри

Побудова мінімального кістяка

У багатьох задачах в заданому графі потрібно виділити деяку частину, що володіє тим чи іншим властивістю.

Визначення 11.1. Граф G1 = (V1, E1) називається подграфом графа G = (V, E), якщо і .

Для неорієнтованих зв'язкових графів одним з цікавих класів подграфов є дерева, що зберігають зв'язність вершин. Вони називаються остовами, кістяк, каркасами або скелетами графа.

Визначення 11.2. Кістяком (неорієнтованого) зв'язного графа G = (V, E) називається його підграф S = (V, T), що є деревом.

Нехай задана функція c: E -> R, що приписує кожному ребру його вартість (вага, довжину) (R - безліч дійсних чисел). Тоді вартість c (S) дерева S визначається як сума вартостей всіх його ребер, тобто .

Мінімальним остовом називається остов мінімальної вартості.

Таким чином, мінімальний остов - це найдешевша (коротка) система шляхів, що зв'язує всі вершини G.

Опишемо процедуру побудови мінімального кістяка, запропоновану Дж. Крускалом в 1956р.

алгоритм МінОстов

Вхід: зв'язний граф G = (V, E) і функція вартості ребер c: E -> R.

Вихід: мінімальний остов S = (V, T).

Етап 1. Нехай E містить m ребер. Впорядкуємо їх по зростанню вартостей:

Етап 2. Послідовно для кожного i = 1, ..., m визначимо безліч ребер Ti:

Покладемо T = Tm.

Видати в якості результату граф S = (V, T).

Доведемо, що цей алгоритм коректний.

Теорема 11.1. Алгоритм МінОстов будує мінімальний остов вхідного графа G = (V, E).

Доказ Нехай результатом роботи МінОстов на графі G = (V, E) є граф S = (V, T). Відзначимо спочатку, що S є деревом. Дійсно, відсутність циклів випливає з визначення множин Ti. Припустимо, що S не є зв'язковим. Тоді повинні існувати дві вершини , Які недосяжні одна з одної в S. Але граф G зв'язний, тому в ньому є шлях з u в v. Тоді на цьому шляху обов'язково є таке ребро , У якого один кінець a з'єднаний шляхом з u в графі S, а другий кінець b - немає. Але тоді на кроці i ребро ei має потрапити в Ti, так як його додавання не утворює циклу. Отже, граф S зв'язний.

Покажемо тепер, що дерево S має мінімальну вартість. Нехай T = {d1, ..., dk, ..., dn-1} - впорядкування всіх ребер T за вартістю.

Покажемо індукцією по k = 1, ..., (n-1), що існує мінімальний остов, який включає ребра d1, ..., dk.

Нехай S '= (V, T') - мінімальний остов, у якого (k-1) найменших за вартістю ребер збігаються з ребрами T, тобто впорядкування всіх його ребер має вигляд: T '= {f1 = d1, ..., fk-1 = dk-1, fk, ..., fn-1} і . Нехай dk = (u, v). В T 'є певний шлях p з u в v, який не містить ребро dk. На цьому шляху обов'язково є якийсь ребро f = (u ''), що не потрапило в T, інакше в T утворився б цикл. З побудови T випливає, що c (dk) <= c (f). Розглянемо граф . Очевидно, що цей граф є остовне деревом. Дійсно, зв'язок між u 'і v' збереглася, так як в S '' є шлях: . Тому S '' - зв'язний граф. Якби в S '' був цикл, то він обов'язково включав би ребро dk. Але тоді частина цього циклу без ребра dk утворювала б шлях p 'між u в v, який не збігається з шляхом p. Отже, в дереві T 'було б два різних шляхи між u в v, що неможливо, так як тоді в T' був би цикл. Звідси робимо висновок, що в S '' циклів немає і S '' - кістяк. Його вартість c (S '') = c (S ') - c (f) + c (dk) <= c (S'). Так як S '- мінімальний остов, то c (S' ') = c (S') і S '' - теж мінімальний остов, у якого з S є k загальних ребер: d1, ..., dk.

Тоді при k = n-1 отримуємо, що S - мінімальний остов.

Приклад 11.1. Розглянемо навантажений граф G, показаний на Мал. 11.1 .

Застосуємо до нього алгоритм МінОстов. На першому етапі впорядкуємо всі ребра, а на другому - поряд з кожним з них визначимо відповідне безліч Ti. Ребра, що потрапили в T, будемо по ходу обчислення відзначати знаком '+', а не потрапили - знаком '-'.

Таким чином, ми побудували для G мінімальний остов S = (V, T), де T = T8 = {(a, g), (g, e), (g, c), (e, d), (a, b), (f, g)}. Він показаний на Мал. 11.2 . Вартість цього остова c (S) = 25.

Мал.11.2.

Мінімальний остов S = (V, T) для графа G

Зауваження. Так як дерево з n вершинами містить в точності (n-1) ребер, то роботу алгоритму МінОстов можна припиняти після такого кроку i, на якому в Ti виявиться | V | - 1 ребер. У нашому прикладі | V | = 7 і алгоритм міг зупинитися після 8-го кроку.