Минимальное остовное дерево

Минимальное остовное дерево (МОД, Minimum Spanning Tree, MST) — это связный подграф взвешенного неориентированного графа, который включает все вершины исходного графа, не содержит циклов и имеет минимально возможный суммарный вес рёбер. В терминах теории графов, остовное дерево (или остов) — это ациклический связный подграф, содержащий все вершины графа. Минимальное остовное дерево является одним из фундаментальных понятий комбинаторной оптимизации и теории алгоритмов.

Определение и формальная постановка

Пусть дан неориентированный граф \( G = (V, E) \), где \( V \) — множество вершин, а \( E \) — множество рёбер. Каждому ребру \( e \in E \) приписан вес \( w(e) \) — действительное число. Остовное дерево \( T \) — это подграф \( G \), который является деревом (связным ациклическим графом) и содержит все вершины \( V \). Суммарный вес остовного дерева \( w(T) \) равен сумме весов всех его рёбер: \( w(T) = \sum_{e \in T} w(e) \).

Минимальное остовное дерево — это остовное дерево, для которого \( w(T) \) минимально среди всех возможных остовных деревьев графа \( G \). Если граф несвязен, то говорят о минимальном остовном лесе — наборе минимальных остовных деревьев для каждой компоненты связности.

Свойства

Единственность

Минимальное остовное дерево может быть не единственным. Если все рёбра графа имеют различные веса, то МОД единственно. При наличии рёбер с одинаковыми весами может существовать несколько различных МОД.

Свойство разреза

Одно из ключевых свойств, лежащих в основе алгоритмов построения МОД, — свойство разреза. Пусть \( S \) — непустое собственное подмножество вершин \( V \). Рассмотрим разрез \( (S, V \setminus S) \). Ребро \( e \), пересекающее этот разрез (то есть имеющее одну вершину в \( S \), а другую — в \( V \setminus S \)), называется лёгким для данного разреза, если его вес минимален среди всех рёбер, пересекающих этот разрез. Тогда любое лёгкое ребро для любого разреза принадлежит некоторому минимальному остовному дереву.

Свойство цикла

Для любого цикла в графе ребро с максимальным весом в этом цикле не принадлежит ни одному минимальному остовному дереву. Это свойство используется в алгоритме обратного удаления.

Алгоритмы построения

Существует несколько классических алгоритмов для нахождения МОД. Все они основаны на жадной стратегии и используют свойство разреза.

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

Алгоритм Прима начинает с произвольной вершины и постепенно наращивает дерево, добавляя на каждом шаге лёгкое ребро, соединяющее текущее дерево с ещё не включённой вершиной. Реализация с использованием очереди с приоритетами (например, двоичной кучи) имеет сложность \( O(E \log V) \), где \( V \) — число вершин, \( E \) — число рёбер. Для плотных графов может быть эффективна реализация без кучи со сложностью \( O(V^2) \).

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

Алгоритм Краскала изначально рассматривает каждую вершину как отдельное дерево (компоненту связности). Затем рёбра сортируются по возрастанию веса, и каждое ребро просматривается: если оно соединяет вершины из разных компонент, то добавляется в остов, а компоненты объединяются. Для проверки связности и объединения используется структура данных «система непересекающихся множеств» (DSU). Сложность алгоритма — \( O(E \log E) \) или \( O(E \log V) \) (так как \( E \leq V^2 \), логарифмы отличаются константой).

Алгоритм Борувки

Алгоритм Борувки (иногда называемый алгоритмом Солина) является одним из старейших (1926 год). На каждом шаге для каждой компоненты связности текущего леса выбирается ребро минимального веса, соединяющее эту компоненту с другой. Затем все выбранные рёбра добавляются в остов. Процесс повторяется, пока не останется одна компонента. Сложность — \( O(E \log V) \). Алгоритм хорошо подходит для параллельных вычислений.

Алгоритм обратного удаления

В отличие от предыдущих, этот алгоритм работает «от противного». Исходный граф рассматривается целиком, и из него последовательно удаляются рёбра с максимальным весом, если их удаление не нарушает связность графа. Алгоритм менее эффективен на практике (сложность \( O(E \log E \cdot \alpha(V)) \)), но нагляден.

Применение

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

Проектирование сетей

Классическое применение — прокладка кабелей, дорог, трубопроводов или линий электропередач, соединяющих несколько точек (городов, узлов) с минимальной суммарной длиной или стоимостью. МОД даёт оптимальный по стоимости связный каркас.

Кластеризация

В анализе данных и машинном обучении МОД используется для иерархической кластеризации. Например, алгоритм кластеризации на основе МОД (Single-linkage clustering) строит дендрограмму, последовательно удаляя из МОД рёбра с наибольшим весом. Это позволяет выделять кластеры произвольной формы.

Аппроксимация задач

МОД является ключевым элементом в приближённых алгоритмах для некоторых NP-трудных задач, таких как задача коммивояжёра (алгоритм Кристофидеса) и задача Штейнера. Для задачи коммивояжёра на метрическом пространстве МОД даёт 2-приближение (двойной обход дерева).

Компьютерное зрение и обработка изображений

В сегментации изображений МОД используется для разбиения изображения на области (суперпиксели). Алгоритм сегментации по методу Фельзенцвальба и Хуттенлохера основан на построении МОД на графе, где вершины — пиксели, а веса рёбер — мера различия между ними.

Другие области

• Биоинформатика: построение филогенетических деревьев, анализ генетических расстояний.
• Теория надёжности: оценка надёжности сетей с помощью дерева минимального веса.
• Планирование маршрутов: в задачах, где требуется посетить все точки, но не обязательно возвращаться (минимальное связующее дерево как нижняя граница).

Интересные факты

• Первый алгоритм для нахождения МОД был предложен чешским математиком Отакаром Борувкой в 1926 году для решения задачи электрификации Моравии.
• Алгоритм Краскала был опубликован в 1956 году, а алгоритм Прима — в 1957 году (хотя его первооткрывателем считается Войцех Ярник, опубликовавший его в 1930 году).
• Существуют рандомизированные алгоритмы (например, алгоритм Каргера — Кляйна — Тарьяна), которые работают в ожидаемом линейном времени \( O(E) \).
• В 2002 году Бернард Шазель предложил детерминированный алгоритм, работающий за \( O(E \, \alpha(V)) \), где \( \alpha \) — обратная функция Аккермана, что практически линейно.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание.
• Седжвик Р. «Фундаментальные алгоритмы на C++» (Algorithms in C++).
• Ахо А., Хопкрофт Дж., Ульман Дж. «Структуры данных и алгоритмы».
• Статья «Minimum spanning tree» в англоязычной Википедии (проверено на дату составления).