36. Задача построения минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима. Оценка вычислительной сложности этих алгоритмов.

Деревья

Граф G = <V, E> называется деревом, если он связен и ацикличен.

Пусть G = <V, E> — граф с n вершинами и m ребрами.

Необходимые и достаточные условия того, что G — дерево:

• Любая пара вершин в G соединена единственным путем

• G связен и m = n – 1

• G связен и удаление хотя бы одного его ребра нарушает связность графа

• G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

Остовной граф

• В любом связном графе найдется подграф, являющийся деревом.

• Подграф в G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом.

• Построение остовного дерева: Выбираем произвольное ребро и последовательно добавляем другие ребра, не создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла.

• Всего n -1 ребро!!!

Алгоритм построения минимального остовного дерева (задача поиска кратчайшего соединения)

• Задача построения минимального остовного дерева — это одна из немногих задач теории графов, которую можно считать полностью решенной.

• Задача о проведении дорог. Для каждой пары городов А и В известна стоимость С(А,В) строительства городов между ними. Нужно построить самую дешевую из все возможных сеть дорог. Искомый граф должен быть деревом, которое называют экономическим. Таким образом, задача состоит в нахождении алгоритма, определяющего среди nn–2 возможных деревьев, которые соединяют вершины, дерева наименьшей длины, определяемой как сумма его ребер.

Алгоритм Краскала

• Пусть есть связный граф, имеющий n вершин.

• Шаг 1. Упорядочим ребра графа в порядке их неубывания их весов.

• Шаг 2. Начиная с первого ребра в этом списке, добавлять ребра в графе, соблюдая условие: такое добавление не должно приводить к появлению цикла.

• Шаг 3. Повторять Шаг 2 до тех пор, пока число ребер в графе не станет равно n – 1. Получившееся дерево является минимальным остовным деревом графа.

Больше всего времени необходимо для выполнения сортировки — при m ребрах это m log2m операций. Но нужны только n – 1 ребро!

Для полных графов более эффективный алгоритм был предложен Примом и Дейкстрой.

Алгоритм Прима

• Шаг 1. Выбрать произвольную вершину и ребро, соединяющее ее с ближайшим по весу соседом.

• Шаг 2. Найдите не присоединенную (еще) вершину, ближе всего лежащую к одной из присоединенных, и соедините с ней.

• Шаг 3. Повторять Шаг 2 до тех пор, пока все вершины не будут присоединены.