Преобразование графа в остовное связное дерево минимального веса

Алгоритм Крускала (Kruscal)

XIV. ДЕРЕВЬЯ

Дерево – это граф, в котором нет циклов, то есть граф, в котором нельзя из некоторой вершины пройти по нескольким различным ребрам, и вернутся в ту же вершину.

Остовным связным деревом называется подграф, включающий в себя все вершины исходного графа G, каждая вершина которого (дерева) достижима из любой другой, и не содержащий циклов.

Пусть G=(V,R) – связный взвешенный неориентированный граф (матрицу смежности см. на стр.). Цикломатическое число равно разности между количеством ребер и количеством вершин графа, увеличенной на единицу.

у=т-п+1

Для графа G у =8-5+1=4. это значит, что для получения остовного связного дерева в графе G необходимо удалить 4 ребра, тогда в нем не останется ни одного цикла.

Пример остовного связного дерева:

V₂

V₅

V₃ V₄

Для построения остовного связного дерева минимального веса используется алгоритм Крускала:

1. каждая вершина исходного графа помещается в одноэлементное подмножество, где все вершины изолированы:

2. ребра сортируются по возрастанию веса;

3. ребра последовательно включаются в остовное дерево. Существуют четыре случая:

а) обе вершины ребра не принадлежат пока ни одному из множеств, тогда они объединяются в новое множество;

б) одна из вершин принадлежит множеству, а другая – нет, тогда включаем вторую во множество первой;

в) обе вершины принадлежат разным множествам, тогда эти множества объединяются;

г) обе вершины принадлежат одному множеству, тогда данное ребро исключаем;

4. алгоритм заканчивает работу, когда все вершины объединяются в одно множество, при этом оставшиеся ребра не включаются в остовное дерево.

Построим остовный подграф, содержащий только изолированные вершины

Каждая вершина исходного графа помещается в одноэлементное подмножество {V₁} {V₂} {V₃} {V₄} {V₅}

V₂ V₁     V₅   V₃ V₄

Найдем ребро минимального веса и добавим его в остовный подграф

Образуется связное подмножество вершин: {V₁,V₅}. Сохраняются одноэлементные подмножества {V₂} {V₃} {V₄}

V₂ V₁     V₅   V₃ V₄

Среди оставшихся ребер ищем ребро минимальной длины и добавляем его в остовный подграф

Так как одна из вершин входит в связное подмножество, добавим в него и вторую вершину: {V₁,V₅,V₄}. Сохраняются одноэлементные подмножества {V₂} {V₃}

V₂ V₁     V₅   V₃ V₄

Среди оставшихся ребер ищем ребро минимальной длины и добавляем его в остовный подграф

Так как ни одна из вершин не входит в связанное подмножество, создадим второе подмножество: {V₂,V₃}. Существует так же первое подмножество {V₁,V₅,V₄}.

V₂ V₁     V₅   V₃ V₄

Среди оставшихся ребер ищем ребро минимальной длины и добавляем его в остовный подграф

Так как одна вершина ребра входит в одно подмножество, а другая вершина – во второе подмножество, эти подмножества объединяются в одно подмножество {V₁,V₅,V₄,V₂,V₃}

V₂ V₁

V₅

V₃ V₄

Остальные ребра в граф включать не надо, так как все их вершины уже принадлежат одному связному множеству.

Получен граф, который:

- является остовным, так как включает все вершины,

- является связным, так как вершины в нем можно соединить маршрутом,

- является деревом, так как в нем отсутствуют циклы,

- обладает минимальным весом: R₁₅ +R₄₅ +R₂₃ +R₂₅= 10+15+25+30=80.

Дата добавления: 2014-01-20