Кістяк зв’язкового графа

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

Приклад. На рис. 2 представлений граф з п'ятьма вершинами і вісьмома ребрами. Чотири виділені ребра (разом з п'ятьма вершинами) складають кістяк цього графа. Кістяк визначено неоднозначно.

На рис. 3 виділені ребра, складові ще одне кістяк того ж графа (зауважимо, що на цьому малюнку невиділені ребра також складають кістяк).

У прикладному плані завдання знаходження остовного дерева можна розуміти як пошук системи зв'язків між заданими точками без непотрібного дублювання.

Побудова остовного дерева. Кістяк T графа G можна сформувати наступним чином. Спочатку беремо в якості T довільну вершину графа G. Далі послідовно нарощуємо дерево T у відповідності з наступним правилом: якщо на графі G є ребро, що з'єднує вершини u і v такі, що u міститься в T. а v -

немає, додаємо до T це ребро разом з вершиною v. Покажемо, що при цьому граф Т залишається деревом. По-перше, кожна додається вершина пов'язана з однією з вже входять в T. так що додавання нових вершин і ребер залишає граф T зв'язковим. Далі, в початковий момент граф T містить одну вершину і не має жодного ребра. Потім на кожному кроці побудови число його вершин і число ребер збільшується на одиницю. Таким чином, число вершин графа T на одиницю перевищує число його ребер. Отже, граф T є деревом. На певному етапі подальше розширення T виявиться неможливим. Покажемо, що в цьому випадку T являє собою кістяк графа G. тобто всі вершини графа G потрапили в T. Позначимо через T 'граф, який містить всі вершини графа G. не потрапили в T. і все що з'єднують їх ребра. На графі G немає ребер, які мали б одну кінцеву вершину в T. а іншу в T '. Так як граф G зв'язний, T 'не може бути непустою.

Нехай n - число вершин, а m - число ребер графа G. Будь-яке його кістяк T має n вершин і n - 1 ребро. Таким чином, кістяк виходить відкиданням m - n + 1 ребер графа G. Число # 61 677; (G) = m - n + 1 називають цикломатическая числом графа G.

Кістяк графа G може бути отримано послідовним видаленням # 61 677; (G) «зайвих» ребер: на кожному

кроці можна відкинути будь-ребро, якщо це не веде до порушення зв'язності графа.

Припустимо, що кожному ребру графа приписано деяке позитивне число, зване його вагою або вартістю (це може бути, наприклад, в разі інформаційних мереж, вартість встановлення зв'язку між кінцевими точками). В цьому випадку граф називається навантаженим. Вартістю навантаженого графа будемо вважати сумарну вартість всіх його ребер. Багато задач, пов'язані з побудовою економічних систем повідомлення або інформаційних систем, призводять до задачі пошуку остовного дерева мінімальної вартості.

Нехай G - зв'язний навантажений граф. Позначимо через c (T) вартість довільного подграфа T графа G. Якщо граф T зв'язний, містить всі вершини графа G і має мінімальну вартість серед усіх подграфов графа G. володіють цими двома властивостями, то T є остовне деревом. Справді, якби граф T містив цикл, то можна було б відкинути, принаймні, одне ребро і тим самим зменшити вартість T.

Наведемо алгоритм побудови остовного дерева мінімальної вартості. Він виходить невеликим видозміною алгоритму побудови остовного дерева зв'язкового графа. Спочатку беремо в якості T вершину графа G. з якої виходить ребро мінімальної вартості. Далі, поки

це можливо, послідовно нарощуємо дерево T. з усіх ребер графа G. з'єднують вершини u ∈T і v ∉T. вибираємо ребро мінімальної вартості і додаємо до T це ребро разом з вершиною v. Отримане в результаті виконання цього алгоритму кістяк буде мати мінімальну вартість.

Приклад. На рис. 4 виділено кістяк мінімальної вартості. Його вартість дорівнює 6. Остовне дерево, представлене на рис. 2, при тих же оцінках ребер має вартість 8, кістяк на рис. 3 - вартість 8, невиділені ребра на рис. 3 складають кістяк