Минимальное остовное дерево: описание и особенности теории графов

Минимальное остовное дерево - важная задача теории графов с множеством практических применений. В статье мы разберем ее определение, основные свойства и алгоритмы построения. Узнаете, зачем нужно минимальное остовное дерево и как его эффективно найти.

Постановка задачи о минимальном остовном дереве

Формально задача ставится следующим образом. Дан взвешенный неориентированный граф G=(V,E). Требуется найти такое поддерево T этого графа, которое бы соединяло все его вершины V, и при этом имело наименьший возможный вес w(T) (сумму весов входящих в него ребер).

Неформально задачу можно представить на примере транспортной сети или дорожной системы. Есть n городов, которые нужно соединить дорогами так, чтобы из любого города можно было попасть в любой другой. Между некоторыми парами городов уже есть дороги, причем известна стоимость строительства каждой дороги. Требуется определить минимальный набор дорог, который обеспечит транспортную связность всех городов.

Рассмотрим пример исходного графа с 6 вершинами A,B,C,D,E,F и 9 ребрами:

Здесь вершины соответствуют городам, ребра - возможным дорогам между ними, а веса ребер являются стоимостью строительства дорог.

Свойства минимальных остовных деревьев

Рассмотрим основные свойства минимальных остовных деревьев:

• Существование и единственность. Минимальное остовное дерево всегда существует для любого связного взвешенного графа. Если все веса ребер различны, такое дерево единственно.
• Объем входных данных: O(m + n), где m - число ребер, n - число вершин. Выходные данные: список ребер минимального остовного дерева. Их объем: O(n).
• Минимальное ребро фрагмента. Пусть F - фрагмент минимального остовного дерева. Тогда ребро наименьшего веса, исходящее из F, принадлежит этому дереву.

Для нахождения минимального остовного дерева разработано несколько эффективных алгоритмов. Рассмотрим подробнее один из самых известных - алгоритм Крускала.

Минимальное остовное дерево Крускала: описание и пример

Алгоритм Крускала работает следующим образом:

1. Сортируем все ребра графа по возрастанию весов
2. Начинаем строить остовное дерево, последовательно добавляя в него наименьшие ребра, при условии, что добавляемое ребро не образует цикла
3. Заканчиваем, когда все вершины оказываются соединены

Рассмотрим работу алгоритма на примере графа, приведенного выше:

1. Ребра отсортированы по возрастанию весов: D-B (вес 2) D-C (вес 6) A-B (вес 7) A-C (вес 8) C-E (вес 9)

2. Начинаем добавлять ребра в порядке сортировки:

   Добавляем ребро D-B (вес 2), получаем фрагмент {D, B} Добавляем D-C (вес 6), получаем фрагмент {D, B, C} Ребро A-C не добавляем, т.к. оно образует цикл
3. Продолжаем добавлять следующие ребра до тех пор, пока все вершины не окажутся соединенными

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

Реализация алгоритма Крускала

Нахождение минимального остовного дерева - алгоритма - основана на использовании так называемой Системы Непересекающихся Множеств (СНМ, Disjoint Sets Union). Рассмотрим основные шаги:

1. Сортируем ребра графа по возрастанию весов
2. С помощью make_set() помещаем каждую вершину v в свое множество
3. Для каждого ребра uv в отсортированном порядке: Находим множества, к которым принадлежат u и v с помощью find_set() Если множества разные, объединяем их через union_sets() и добавляем ребро uv к ответу

Временная сложность такой реализации с использованием деревьев как представления множеств составляет O(E log V).

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

Докажем, что описанный алгоритм Крускала действительно строит минимальное остовное дерево.

На каждой итерации алгоритм берет минимальное ребро из оставшихся и проверяет, не замыкает ли оно цикл. Таким образом, согласно свойству минимального ребра фрагмента, каждое добавленное ребро является безопасным и входит в минимальное остовное дерево.

Количество итераций равно n - 1, где n - число вершин. Это ровно столько ребер, сколько нужно добавить, чтобы получилось дерево. Значит, в результате работы алгоритма получается минимальное остовное дерево исходного графа.

Улучшение производительности Крускала

Построение минимального остовного дерева Крускала можно оптимизировать, используя эффективные структуры данных.

Построить минимальное остовное дерево, где ключевыми операциями являются: сортировка ребер, проверка наличия цикла, объединение множеств вершин.

• Для сортировки ребер по весу можно использовать кучу или быструю сортировку за O(E log E).
• Для представления множеств вершин удобно использовать структуры с быстрыми операциями объединения за O(log V) - например, деревья отрезков.
• Тогда общая асимптотика алгоритма составит O((V+E) log V).

Модификации алгоритма Крускала

Существует несколько модификаций алгоритма Крускала:

• Для несвязных графов в результате получается остовный лес.
• Можно строить максимальное остовное дерево, если сортировать ребра по убыванию весов.
• Для задачи о дереве Штайнера разрешено добавлять новые вершины с целью уменьшить общий вес.

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

Еще одним популярным алгоритмом построения минимального остовного дерева является алгоритм Прима. Рассмотрим его основную идею и особенности.

Основная идея алгоритма Прима

Алгоритм Прима последовательно достраивает минимальное остовное дерево, начиная с произвольной начальной вершины. На каждом шаге к текущему дереву добавляется минимальное ребро, ведущее в еще непосещенную вершину.

Для нахождения такого ребра используется приоритетная очередь из «кандидатов» - всех ребер, соединяющих текущее дерево с оставшимися вершинами. Ключом в очереди является вес ребра.

Инварианты в алгоритме Прима

Работа алгоритма Прима базируется на следующих инвариантах:

• Дерево F является фрагментом минимального остовного дерева исходного графа
• Ребра в приоритетной очереди Q являются кандидатами на включение в дерево F

Эти инварианты сохраняются на каждой итерации, что гарантирует корректность алгоритма.

Доказательство корректности Прима

Покажем, что алгоритм Прима действительно строит минимальное остовное дерево.

Каждое вновь добавляемое ребро (u, v) имеет минимальный вес среди всех ребер из множества вершин дерева F во множество оставшихся вершин. Значит, оно является минимальным ребром фрагмента и, согласно соответствующему свойству, безопасно.

Так как алгоритм добавляет ровно V-1 безопасных ребер, то результатом его работы является минимальное остовное дерево.

Сложность алгоритма Прима

Временная сложность Прима зависит от структуры данных для реализации приоритетной очереди.

Например, с двоичной кучей - O((V+E) log V). С Фибоначчиевой кучей или деревьями отрезков можно добиться линейного времени O(V+E).

Сравнение алгоритмов Крускала и Прима

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

Крускал начинает с сортировки всех ребер и затем постепенно добавляет их в растущее дерево. Прим же, наоборот, начинает с одной вершины и достраивает дерево путем добавления минимальных отходящих ребер на каждом шаге.

Преимуществом алгоритма Прима является его сложность, которая лучше, чем у алгоритма Крускала. Следовательно, алгоритм Прима полезен при работе с плотными графами с большим количеством ребер.

Однако, алгоритм Прима не дает нам большого контроля над выбранными ребрами, когда встречается несколько ребер с одинаковым весом. Причина в том, что внутри очереди хранятся только ребра, обнаруженные на данный момент, а не все ребра, как в алгоритме Крускала.

Кроме того, в отличие от алгоритма Крускала, алгоритм Прима немного сложнее реализовать.

Общая производительность

Асимптотическая сложность обоих алгоритмов одинакова и составляет O(E log V) в наивной реализации и O(V+E) с использованием сложных структур данных.

На практике Прим часто работает немного быстрее из-за более локального характера операций.

Сложность реализации

Алгоритм Крускала проще реализовать, т.к. опирается всего на две структуры данных - сортировку ребер и disjoin-set.

В Приме сложнее реализовать эффективную приоритетную очередь с быстрым изменением приоритета элемента.

Параллельные версии

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