13.Задача об остовном дереве. Алгоритмы Прима и Краскала, их реализация

Пусть каждое ребро графа имеет положительный вес.

Задача состоит в том чтобы найти остов наименьшего веса.

Теорема Кирхгофа. Число остовных деревьев связного графа G равно алгебраическому дополнению любого эл-та его матрицы Кирхгофа.

Теорема Кэли. Число остовных деревьев полного графа на n вершинах равно n^n-2.

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

1.Начать с пустого графа T. 2.Упорядочить ребра графа G в порядке неубывания их весов. 3.Начав с первого ребра в этом списке, добавлять ребра в графе T, соблюдая условие: такое добавление не должно приводить к появлению цикла в T. 4.Повторять шаг 3 до тех пор, пока число ребер в T не станет равным n-1 Пример. Есть граф с различными весами ребер-все его вершины помечаем a b c d e f g и расставляем под ними метки 1 2 3 4 5 6 7. Далее находим наименьшее по весу ребро(пусть af), помечаем его и под f пишем 1, т.е то, что написано под а, ищем следующее мин ребро(пусть cd), помечаем его и под d пишем 3(то что под с) Следующее мин ребро помечаем f b-тогда под b пишем 1(то что под f)- далее помечаем fc-тогда под c пишем 1 и под соответственно тоже(так как под c стало 1) и тд, пока под всеми буквами не будут стоять единицы. В итоге помеченные ребра и образуют дерево мин веса. Сложность алгоритма Краскала - O(mlogm)

Теорема. Алгоритм Краскала строит дерево минимального

веса.

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

1.Начать с пустого графа T₀ 2.Пусть T_k-1 уже построено, T_k получается из T_k-1 добавлением ребра e минимального веса среди обладающих свойствами: a) e инцидентно какой-либо вершине T_k-1; b)T_k-1+e не содержит циклов; Алгоритм. Сначала всем вершинам метки 0 в новом графе где только вершины, соединяем ребром с мин весом вершины а и f – тогда у а и f метки 0,у всех же остальных вершин мин веса ребер из f к другим вершинам, либо если через а короче, то и вес мин ребра из а, тогда выбираем вершиту с мин меткой и соединяем ребром-пусть это b-тогда b тоже получает метку 0 теперь просматриваем расстановку меток вершин для b и т д пока не построим остов(то есть через все вершины должны проходить ребра). Сложность алгоритма Прима при стандартной реализации – O (n²)