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

Материал из MachineLearning.

Версия от 13:42, 13 июля 2026; Alfina Iamaeva (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Минимальное остовное дерево (Minimum Spanning Tree, MST)

Минимальное остовное дерево (Minimum Spanning Tree, MST)

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

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

Определения

Пусть задан связный неориентированный граф $G = (V, E)$ , где $V$ — множество вершин, а $E$ — множество рёбер. Для каждого ребра $e \in E$ определена его весовая функция $w(e) \in \mathbb{R}$ , которая сопоставляет ребру некоторое числовое значение (стоимость, длину, пропускную способность и т.д.).

Остовное дерево графа $G$ — это ациклический связный подграф $T = (V, E')$ , где $E' \subseteq E$ и $|E'| = |V| - 1$ . Вес остовного дерева определяется как сумма весов входящих в него рёбер: $w(T) = \sum_{e \in E'} w(e)$ .

Минимальное остовное дерево (MST) — это остовное дерево $T^*$ , такое что $w(T^*) \le w(T)$ для любого другого остовного дерева $T$ графа $G$ .

Свойства MST

Задача поиска MST обладает рядом важных свойств, которые лежат в основе всех классических алгоритмов её решения:

Свойство разреза (Cut Property): Рассмотрим произвольное подмножество вершин $S \subset V$ , где $S \neq \emptyset$ и $S \neq V$ . Пусть ребро $e$ — ребро минимального веса среди всех рёбер, пересекающих разрез $(S, V \setminus S)$ (т.е. соединяющих вершину из $S$ с вершиной из $V \setminus S$ ). Тогда существует минимальное остовное дерево, содержащее ребро $e$ .

Свойство цикла (Cycle Property): Рассмотрим любое ребро $e$ , принадлежащее некоторому циклу в графе $G$ . Если вес ребра $e$ строго больше веса любого другого ребра в этом цикле, то $e$ не может принадлежать никакому минимальному остовному дереву.

Свойство безопасного ребра (Safe Edge Property): Добавление ребра, удовлетворяющего свойству разреза, к частичному остовному лесу сохраняет возможность построения MST. Такое ребро называется безопасным.

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

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

Алгоритм Крускала (Kruskal's algorithm)

Алгоритм Крускала был предложен Джозефом Крускалом в 1956 году . Его основная идея заключается в построении MST путём последовательного добавления рёбер в порядке возрастания их весов, при условии, что добавляемое ребро не создаёт цикла .

Этапы алгоритма:

Инициализировать лес, состоящий из изолированных вершин графа $G$ .
Отсортировать все рёбра графа $G$ по неубыванию весов.
Для каждого ребра в отсортированном порядке:
- Если вершины $u$ и $v$ принадлежат разным компонентам связности текущего леса, добавить ребро $e$ в остовное дерево и объединить эти две компоненты.
- В противном случае (если $u$ и $v$ уже в одной компоненте), пропустить ребро, так как его добавление создаст цикл.
Алгоритм завершается, когда в остовном дереве будет $|V| - 1$ ребро (т.е. все вершины будут соединены в одну компоненту).

Для эффективной проверки принадлежности вершин к разным компонентам и их объединения используется структура данных системы непересекающихся множеств (Union-Find, DSU) .

Сложность алгоритма: $O(E \log E) = O(E \log V)$ , где $E$ — число рёбер, $V$ — число вершин. Сложность определяется, в первую очередь, сортировкой рёбер . При использовании эффективной реализации DSU операции find и union выполняются почти за константное время.

Алгоритм Прима (Prim's algorithm)

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

Этапы алгоритма:

Выбрать произвольную стартовую вершину $r \in V$ и добавить её в множество построенного дерева $U$ .
Для каждой вершины $v \notin U$ вычислить расстояние до текущего дерева $U$ как минимальный вес ребра, соединяющего $v$ с какой-либо вершиной из $U$ .
На каждом шаге выбирается вершина $v \notin U$ , имеющая минимальное расстояние до дерева. Вершина $v$ и соответствующее ребро минимального веса добавляются в дерево $U$ .
Шаги 2-3 повторяются, пока $U \neq V$ (пока не будут включены все вершины).

Сложность алгоритма: зависит от реализации приоритетной очереди для выбора вершины с минимальным расстоянием.

Простая реализация (без кучи): $O(V^2)$ , эффективна для плотных графов.
С использованием двоичной кучи: $O(E \log V)$ .
С использованием кучи Фибоначчи: $O(E + V \log V)$ .

Алгоритм Борувки (Borůvka's algorithm)

Один из первых алгоритмов для решения задачи MST, предложенный Отакаром Борувкой в 1926 году . Его идея заключается в параллельном добавлении минимальных рёбер для каждой компоненты связности. На каждом шаге для каждой компоненты выбирается исходящее ребро минимального веса, и все такие рёбра добавляются в дерево, объединяя компоненты. Алгоритм завершается, когда остаётся одна компонента. Его сложность составляет $O(E \log V)$ .

Применение в анализе данных и машинном обучении

Хотя задача о MST традиционно относится к области теории графов, она находит важные применения в анализе данных и машинном обучении:

Кластеризация с одиночной связью (Single-linkage clustering): Это один из базовых иерархических алгоритмов кластеризации. Процесс построения дендрограммы методом одиночной связи эквивалентен построению MST графа, вершинами которого являются объекты, а весами рёбер — расстояния между ними . Отсечение рёбер MST с весами, превышающими некоторый порог, позволяет получить кластеры.

Визуализация многомерных данных: MST может быть использовано для построения скелетной структуры данных, отражающей их топологию. Например, для отображения структуры многообразия или для выявления цепочек и паттернов в данных.

Выделение признаков и снижение размерности: Алгоритмы, подобные Isomap, используют MST (или его вариант, Minimum Spanning Tree в метрическом пространстве) для оценки геодезических расстояний между точками на нелинейном многообразии, что помогает выполнить снижение размерности.

Сжатие данных: MST может быть использовано для построения аппроксимирующих графов, которые компактно описывают структуру данных и могут служить для эффективного поиска ближайших соседей.

Вариации и обобщения

Минимальное остовное дерево с ограничениями (Constrained MST): Задача поиска MST с дополнительными ограничениями, например, на степень вершины или на включение обязательных рёбер.
Задача о минимальном остовном дереве Штейнера (Steiner Tree Problem): Обобщение, в котором не требуется включать все вершины графа, а только заданное подмножество (терминалы). Разрешается добавлять вспомогательные вершины (точки Штейнера) для уменьшения суммарного веса дерева .
MST в динамических графах: Задача поддержания MST при добавлении или удалении рёбер в графе.

Список литературы

Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е. — Вильямс, 2013.
Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — ДиаСофт, 2002.
Vorontsov, K.V., Inyakin, A.S., Strizhov, V.V., Chekhovich, Y.V. MachineLearning.ru – информационно-аналитический ресурс по проблемам машинного обучения и интеллектуального анализа данных // Труды конференции. — 2008.
Клейнберг Д., Тардос Е. Алгоритмы: разработка и применение. — Питер, 2016.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE»