Минима́льное осто́вное де́рево (англ. Minimum Spanning Tree – MST), в связном неориентированном графе $G$ со взвешенными рёбрами – дерево, являющееся подграфом $G,$ множество вершин которого совпадает со множеством вершин графа $G$ (т. е. остовным деревом), а суммарный вес рёбер минимален (Алгоритмы ... 2013. Гл. 23). Веса рёбер графа могут быть любыми действительными числами, и никакие ограничения, например, неотрицательность или неравенство треугольника, на них не накладываются. Суммарный вес рёбер подграфа для краткости далее будет называться весом этого подграфа.

Первая опубликованная постановка задачи поиска MST появилась в 1926 г. в статьях чешского математика О. Борувки (Borûvka. O jistém problému ... 1926; Borûvka. Příspěvek k otázce ekonomické ... 1926). Им исследовалась задача построения электросетей при электрификации сельской местности. В этих работах был предложен эффективный алгоритм нахождения MST, ныне известный как алгоритм Борувки (Nešetřil. 2001).

Благодаря многочисленным практическим применениям, задача впоследствии несколько раз независимо переоткрывалась другими исследователями.

Другими известными классическими алгоритмами нахождения MST являются алгоритм Краскала (1956) и алгоритм Прима (1930, переоткрыт в 1957). Как и алгоритм Борувки, они являются жадными. Все перечисленные алгоритмы могут быть реализованы с временно́й сложностью $O(\vert E\vert \log \vert V\vert).$ Известна реализация алгоритма Прима со сложностью $O(\vert E\vert + \vert V\vert \log \vert V\vert).$ Здесь и далее $E$ и $V$ обозначаются множества рёбер и вершин графа $G,$ $\vert E\vert$ и $\vert V\vert$ – число рёбер и вершин в графе $G$ соответственно.

См. также «О большое».

Алгоритмы построения MST с меньшей асимптотической временно́й сложностью

Минимальное остовное дерево, получаемое при применении любого из вышеупомянутых классических алгоритмов, зависит не от значений весов рёбер, а от результатов попарных сравнений данных весов. Например, при изменении весов всех рёбер на одинаковую величину, результат работы алгоритмов не изменяется. Это связано с тем, что классические алгоритмы – детерминированные, и используют основанную на сравнениях модель вычислений.

Если не указано обратного, все результаты из данного раздела также касаются модели вычислений, основанной на сравнениях. В данной модели считается, что единственными разрешёнными операциями являются операции попарного сравнения весов рёбер (Karger. 1995).

В работе Б. Шазеля (Chazelle. 2000) в 2000 г. был предложен детерминированный алгоритм построения MST сложности $O (|E| \alpha(|E|, |V|)),$ где $\alpha(|E|, |V|)$ – двухпараметрическая функция Аккермана, описанная в (Tarjan. 1975). Данная функция растёт крайне медленно: $\alpha(|E|, |V|) = o(\log^* |V|) .$ См. также «о малое».

В публикации (Pettie. 2002) был предложен алгоритм с асимптотически оптимальной временно́й сложностью. Для каждого графа $G$ алгоритм с целью поиска MST строит дерево решений, в каждой вершине которого происходит сравнение весов двух рёбер $G.$ Данное дерево строится за время, равное $O(T^* (G)),$ где $T^* (G)$ – максимальное число сравнений на пути от корня дерева решений к одному из его листьев. Иными словами $T^* (G)$ – это сложность построения MST для графа $G.$

Согласно теореме Левина (Computability and complexity ... 1997. С. 300; Левин. 1974. С. 174–185), имея асимптотически оптимальный алгоритм верификации решения задачи $Pr,$ можно построить алгоритм для решения задачи $Pr$ сложности $O(Ver_{Pr} + Opt_{Pr}),$ где $Ver_{Pr}$ и $Opt_{Pr}$ – сложность верификации и нахождения оптимального решения соответственно. Для задачи построения MST существуют алгоритмы верификации решения асимптотически оптимальной, линейной временно́й сложности $O(m)$ (Dixon. 1992). Оптимальный же алгоритм для MST имеет временну́ю сложность $\Omega(m).$ Отсюда следует существование алгоритма асимптотически оптимальной сложности. Однако данный алгоритм может выходить за рамки основанной на сравнениях модели вычислений, и быть непрактичным вследствие астрономических мультипликаторов для временно́й сложности (Pettie. 2002).

Сложность задачи построения MST

Задача решается за полиномиальное время и принадлежит классу временно́й сложности $P.$ Однако точное значение сложности построения MST для графа не известно. Известно, что оно составляет $\Omega(|E|)$ и $O (|E| \alpha(|E|, |V|)).$ Сложность же оптимального алгоритма (Pettie. 2002) не известна.

Основные свойства MST

Разрезом в графе $G$ (англ. cut-set, cutset) (Harary. 1969. С. 38) называется множество рёбер графа, одна вершина которых лежит в непустом подмножестве $S \subset V ,$ а другая – в его дополнении $V \setminus S.$

Справедливы следующие утверждения.

Утверждение 1 (свойство разреза). Если ребро из некоторого разреза имеет наименьший вес среди рёбер разреза, и других рёбер с таким весом в разрезе нет, то оно обязательно входит в любое минимальное остовное дерево.

Утверждение 2 (свойство цикла). Если ребро из некоторого цикла имеет наибольший вес среди рёбер цикла, и других рёбер с таким весом в цикле нет, то оно не входит ни в одно минимальное остовное дерево.

Утверждение 3 (уникальность MST). В связном графе с различным весом всех рёбер существует единственное минимальное остовное дерево.

Утверждение 4 (верификация MST). Дерево $T$ – минимальное остовное дерево графа $G$ тогда и только тогда, когда любое ребро $e$ в $G \setminus T$ – нестрого максимальное в цикле, образующемся при добавлении $e$ в $T.$

Рандомизированный алгоритм

В публикации (Karger. 1995) предложен рандомизированный алгоритм, строящий минимальный остовный лес (англ. MSF), т. е. обобщение MST на случай несвязного графа, за линейное в среднем время $O(|E|).$ Данный алгоритм находит MSF за линейное время всегда за исключением случаев, имеющих место с пренебрежимо малой вероятностью, составляющей $O(\exp\{-\Omega(|E|)\}).$

Для описания предложенного в работе алгоритма понадобится следующее следствие свойства цикла.

Утверждение 5. Пусть $T$ – некоторое остовное дерево, а $e$ – такое ребро, не принадлежащее $T,$ что при его добавлении к $T$ образуется цикл, в котором ребро $e$ – самое тяжёлое (т. н. $T$-тяжёлое ребро). Тогда $e$ не входит ни в один MSF графа $T.$

Алгоритм выполняет следующие рекурсивные шаги:

1. Применить 2 раза шаги «раскраска» и «сжатие» из алгоритма Борувки.

2. Из рёбер сжатого графа $H$ выбирается случайный подграф $F,$ каждое ребро в который добавляется с вероятностью ${1}/{2} .$ Рекурсивно строится MSF $T$ для $F$ и удаляются, согласно утверждению 5, из $H$ все $T$-тяжёлые рёбра. Случайное семплирование и удаление $T$-тяжёлых рёбер можно выполнить за линейное по числу рёбер графа $H$ время.

3. Предыдущие шаги выполняются рекурсивно, пока в графе остаются несжатые и неудалённые рёбра. MSF состоит из рёбер, сжатых на каждом из шагов алгоритмом Борувки.

Связь минимального остовного дерева и матроидов

Задача поиска минимального остовного дерева эквивалентна задаче поиска максимального остовного дерева. Действительно, поменяв вес каждого ребра графа $G$ на противоположный по знаку, можно получить взвешенный граф $G^ \prime ,$ минимальное остовное дерево для которого является максимальным остовным деревом для $G.$

Для поиска минимального остовного дерева успешно применяются жадные алгоритмы (см. выше). Заметим, что на каждом шаге любого жадного алгоритма получается ациклический граф. Множество ациклических подграфов любого графа непусто и обладает свойством наследования, а именно: при удалении ребра из одного ациклического подграфа получается другой ациклический подграф того же графа. Оказывается, что матроид является единственным непустым набором подмножеств, удовлетворяющим свойству наследования, для которого работает жадный алгоритм для нахождения независимого множества максимального веса (Oxley. 2003. С. 23) во взвешенном матроиде в случае неотрицательных весов элементов опорного подмножества.

Матроид является обобщением как графов, так и наборов линейно независимых векторов из линейной алгебры и теории решёток. В частности, для любого графа $G$ существует графический матроид $M (G),$ или матроид, ему соответствующий (Tutte. 1959). Циклам такого матроида соответствуют простые циклы графа $G.$ Независимым подмножествам $M (G)$ соответствуют ациклические подмножества множества всех рёбер. Для связного графа $G$ размер базы соответствующего графического матроида равен $|V| - 1.$

Практические применения

Минимальное остовное дерево применяется для сегментации изображений (Pal. 2002), где, введя специальное расстояние между сегментами и построив MST, нужное число финальных сегментов образуется при выставлении порога и объединении сегментов с расстоянием ниже порога в один финальный сегмент. Также MST применяется при построении филогенетических (эволюционных) деревьев (PHYLOViZ Online ... 2016), в задаче оптимального размещения объектов (Курочка. 2009) и во многих других практических и научных задачах.

Минимальное остовное дерево также часто применяется в качестве дополнительного построения и используется, например, в алгоритме Кристофидеса (Christofides. 2022) построения приближённого решения для метрической задачи коммивояжёра.