1. Задача о минимальном остовном дереве неориентированного графа
Напомним, что дерево это ациклический связный граф. Подграф графа называется остовным, если он содержит все вершины исходного графа. Пусть дан связный неориентированный граф G(V, E), с числом вершин | V | = n, числом ребер | E | = m, и каждому его ребру e E приписан некоторый вес w(e). Вес подграфа G’(V ‘, E’) графа G(V, E) определим как сумму весов его ребер, то есть
.
Задача о минимальном остовном дереве состоит в поиске остовного дерева исходного графа с минимальным весом.
Приведем базовые алгоритмы решения задачи. Обозначим через Ij совокупность ребер, включенное в искомое дерево на j-ой итерации алгоритма.
Алгоритм Краскала. Начальный шаг: j = 0, I0 = .
Шаг 1. Упорядочиваем ребра множества E в порядке неубывания их весов. Пусть w(e1) ≤ w(e2) ≤…≤w(em).
Шаг 2.
Шаг 3. Если | Ij+1 | = n-1, стоп. Ij+1 – совокупность ребер искомого дерева. В противном случае j := j+1, идем к шагу 2.
Алгоритм Краскала выполняет не более чем m итераций, сложность алгоритма O(m log m).
Обозначим через Oe ( Ij ) множество ребер из E \ Ij, в котором каждое ребро инцидентно с некоторым ребром из Ij . Полагаем Oe ( ) = E.
Алгоритм Прима. Начальный шаг: j = 0, I0 = .
Шаг 1. Строим
множество Oe
( Ij
) и упорядочиваем
его ребра по неубыванию весов. Пусть
Oe ( Ij ) = {
}
и
.
Шаг 2.1. k = 1.
Шаг 2.2.
Шаг 2.3. Если Ij+1 ≠ Ij , то идем к шагу 3. В противном случае k := k + 1 и возвращаемся к шагу 2.2.
Шаг 3. Если | Ij+1 | = n-1, стоп. Ij+1 – совокупность ребер искомого дерева. В противном случае j := j+1, идем к шагу 1.
Cложность алгоритма Прима составляет O(m + n log n).
Для подграфа G’(V ‘, E’) графа G( V, E ) обозначим через Ov (G’ ) множество ребер из E \ E’ инцидентных ровно с одной вершиной множества V ‘. Через V( Ij ) обозначим множество вершин графа G( V, E ) инцидентных ребрам из Ij . При этом положим V( ) = V.
Алгоритм Борувки. Начальный шаг: j = 0, I0 = .
Шаг 1. Упорядочиваем ребра множества E в порядке неубывания их весов.
Шаг 2. Выделяем
компоненты связности
подграфа
G’(V(
Ij
), Ij
), образованного
ребрами Ij
.
Шаг 3. Для каждого
,
находим первое в упорядочении, полученном
на шаге 1, ребро
из
.
Очевидно,
.
Шаг 4. Полагаем
Ij+1
= Ij
{
,
}.
Шаг 5. Если | Ij+1 | = n-1, стоп. Ij+1 – совокупность ребер искомого дерева. В противном случае j := j+1, идем к шагу 2.
Cложность алгоритма Борувки составляет O(m log n).
Пример. Найти минимальное остовное дерево для графа, представленного на рисунке 1. Числа указывают вес ребра, в скобках указано обозначение ребра с номером соответствующим упорядочению по неубыванию.
Рис. 1.
Схема алгоритма Крускала представлена на рисунках 2.1. – 2.4.
Рис. 2.1. Первые две итерации алгоритма Краскала
Рис. 2.2. Третья и четвертая итерации алгоритма Краскала
Рис. 2.3. Пятая и шестая итерации алгоритма Краскала
Рис. 2.4. Завершающая итерация алгоритма Крускала.
Схема алгоритма Прима представлена на рисунках 3.1 – 3.7.
1(e2)
Рис. 3.1. Первые две итерации алгоритма Прима
12(e10)
1(e2)
7(e6)
Рис. 3.2. Третья и четвертая итерации алгоритма Прима
Рис. 3.3. Пятая и шестая итерации алгоритма Прима
Рис. 3.4. Завершающая итерация алгоритма Прима
Схема алгоритма Борувки представлена на рисунке 4.
Рис. 4. Первая и завершающая итерации алгоритма Борувки
Указанные алгоритмы Краскала, Прима и Борувки можно применять и для поиска максимального остовного дерева. Для этого необходимо заменить упорядочение по неубыванию на упорядочение по невозрастанию в соответствующих шагах алгоритмов.