Введение

Минимальное остовное дерево (MST) или дерево минимального веса — это подмножество рёбер связного, взвешенного неориентированного графа, которое соединяет все вершины вместе, без каких-либо циклов и с минимально возможным суммарным весом рёбер. Иными словами, это остовное дерево, сумма весов рёбер которого как можно меньше. В более общем случае, любой взвешенный неориентированный граф (не обязательно связный) имеет минимальный остовный лес, который представляет собой объединение минимальных остовных деревьев для его связных компонент. Существует множество применений минимальных остовных деревьев. Например, телекоммуникационная компания, прокладывающая кабель в новом районе. Если компания вынуждена прокладывать кабель только по определённым маршрутам (например, по дорогам), то можно представить граф, где точки (например, дома) соединены этими маршрутами. Некоторые маршруты могут быть дороже, например, из-за большей длины или необходимости более глубокой прокладки кабеля; эти маршруты будут представлены рёбрами с большим весом. В качестве единицы измерения веса рёбер можно использовать валюту — нет необходимости, чтобы длины рёбер подчинялись обычным правилам геометрии, таким как неравенство треугольника. Остовное дерево для этого графа — это подмножество маршрутов, не содержащее циклов, но соединяющее все дома; возможно существование нескольких остовных деревьев. Минимальное остовное дерево будет иметь наименьшую общую стоимость, представляя собой наиболее экономичный маршрут для прокладки кабеля.

Возможная многообразие

Если в графе n вершин, то каждое остовное дерево содержит n − 1 ребро. Может существовать несколько минимальных остовных деревьев с одинаковым весом; в частности, если все веса ребер данного графа одинаковы, то любое остовное дерево этого графа является минимальным.

Подграфик минимальных затрат

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

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

Для любого цикла C в графе, если вес ребра e цикла C больше любого из весов всех остальных рёбер C, то это ребро не может входить в MST. Доказательство: Предположим обратное, то есть что e входит в MST. Тогда удаление e разобьёт граф на два поддерева, с концами e в разных поддеревьях. Остальная часть цикла C соединяет эти поддеревья, следовательно, существует ребро f цикла C, концы которого находятся в разных поддеревьях, то есть оно соединяет поддеревья в дерево с весом меньше веса e, поскольку вес f меньше веса e.

Собственность

Для любого разреза C графа, если вес ребра e в разрезном множестве C строго меньше весов всех остальных ребер разрезного множества C, то это ребро принадлежит всем минимальным остовным деревьям (МОД) графа. Доказательство: Предположим, что существует МОД T, который не содержит e. Добавление e к T создаст цикл, который пересекает разрез один раз по ребру e и возвращается обратно по другому ребру e'. Удаление e' дает остовное дерево T \ {e'} ∪ {e} строго меньшего веса, чем T. Это противоречит предположению, что T был МОД. По аналогичному аргументу, если более одного ребра имеет минимальный вес на разрезе, то каждое такое ребро содержится хотя бы в одном минимальном остовном дереве.

Минимальная стоимость

Если минимальное по стоимости ребро e графа единственно, то это ребро входит в любое минимальное остовное дерево (MST). Доказательство: если e не включено в MST, удаление любого из (более дорогих) рёбер в цикле, образовавшемся после добавления e в MST, приведёт к получению остовного дерева с меньшим весом.

Сокращение

Если T — дерево рёбер минимального остовного дерева (MST), то мы можем сжать T в одну вершину, сохраняя инвариант, согласно которому минимальное остовное дерево сжатого графа плюс T даёт минимальное остовное дерево для графа до сжатия. Самый быстрый неслучайный алгоритм сравнения с известной сложностью, разработанный Бернардом Шазелем, основан на мягкой куче, являющейся приближённой очередью с приоритетами. Его время работы составляет O(n α), где α — классическая функциональная обратная функция Акермана. Функция α растёт крайне медленно, поэтому для всех практических целей её можно считать константой, не превышающей 4; таким образом, алгоритм Шазеля работает практически за линейное время.

Плотные графики

Если граф плотен (т. е. m/n ≥ log log log n), то детерминированный алгоритм Фредмана и Тарджана находит минимальное остовное дерево (MST) за время O(m). Алгоритм выполняет несколько фаз. Каждая фаза многократно выполняет алгоритм Прима, каждый раз на ограниченном числе шагов. Время выполнения каждой фазы составляет O(m + n). Если число вершин перед фазой равно n', то число вершин, оставшихся после фазы, не превышает. Следовательно, требуется не более log*n фаз, что обеспечивает линейное время выполнения для плотных графов.

Веса целых чисел

Если веса рёбер – целые числа, представленные в двоичной системе счисления, то известны детерминированные алгоритмы, решающие задачу за O(m + n) целочисленных операций. Остаётся открытым вопрос о том, можно ли решить задачу детерминированно для произвольного графа за линейное время алгоритмом, основанным на сравнениях.

Параллельные и распределенные алгоритмы

Исследования также рассматривали параллельные алгоритмы для задачи о минимальном остовном дереве. Используя линейное количество процессоров, можно решить задачу за время O(log n). Эту задачу можно также решать распределенным способом. Если каждый узел рассматривать как компьютер, и ни один узел не знает ничего, кроме своих собственных связей, все равно можно вычислить распределенное минимальное остовное дерево.

MST на полных графиках с случайными весами

Алан Фриз показал, что для полного графа на n вершинах с весами ребер, являющимися независимыми одинаково распределенными случайными величинами с функцией распределения, удовлетворяющей условию , при стремлении n к +∞ ожидаемый вес минимального остовного дерева стремится к , где – функция Римана (точнее, постоянная Апери). Фриз и Стил также доказали сходимость по вероятности. Сванте Янсон доказал центральную предельную теорему для веса минимального остовного дерева. Для равномерно случайных весов в , точный ожидаемый размер минимального остовного дерева был вычислен для небольших полных графов. ВершиныОжидаемый размерПриближенный ожидаемый размер200,530,75400,885714350,966450261,018315171,05371681,079058891,0979027

Фракционный вариант

Существует фракционный вариант МСТ, в котором каждому ребру разрешено участвовать "фракционно". Формально, фракционное остовное множество графа (V,E) — это неотрицательная функция f на E, такая что для каждого нетривиального подмножества W из V (т.е. W не пустое и не равно V), сумма f(e) по всем ребрам, соединяющим вершину из W с вершиной из V\W, не меньше 1. Интуитивно, f(e) представляет собой долю ребра e, входящего в остовное множество. Минимальное фракционное остовное множество — это фракционное остовное множество, для которого сумма f(e) минимальна. Если значения f(e) ограничены множеством {0,1}, то множество T ребер с f(e)=1 является остовным, поскольку каждая вершина или подмножество вершин связано с остальной частью графа хотя бы одним ребром из T. Более того, если f минимизирует сумму, то полученное остовное множество обязательно является деревом, так как если бы оно содержало цикл, то ребро можно было бы удалить, не нарушив условие связности. Таким образом, задача поиска минимального фракционного остовного множества является релаксацией задачи МСТ и также может называться задачей фракционного МСТ. Задачу фракционного МСТ можно решить за полиномиальное время с помощью метода эллипсоидов. Однако, если добавить требование, что f(e) должно быть полуцелым (т.е. f(e) должно принадлежать множеству {0, 1/2, 1}), то задача становится NP-трудной.

k-остовное дерево с минимальным весом (k MST) — это дерево, которое охватывает некоторое подмножество из k вершин в графе с минимальным весом. Множество из k наименьших остовных деревьев — это подмножество из k остовных деревьев (из всех возможных остовных деревьев), такое что ни одно остовное дерево вне этого подмножества не имеет меньшего веса. (Обратите внимание, что эта задача не связана с k-остовным деревом с минимальным весом). Евклидово остовное дерево с минимальным весом — это остовное дерево графа, веса ребер которого соответствуют евклидову расстоянию между вершинами, являющимися точками на плоскости (или в пространстве). Прямоугольное остовное дерево с минимальным весом — это остовное дерево графа, веса ребер которого соответствуют прямоугольному расстоянию между вершинами, являющимися точками на плоскости (или в пространстве). Распределенное остовное дерево с минимальным весом — это расширение МСТ для распределенной модели, где каждая вершина рассматривается как компьютер и ни одна вершина не знает ничего, кроме своих собственных связанных ребер. Математическое определение задачи остается прежним, но существуют различные подходы к ее решению. Остовное дерево с ограниченной емкостью — это дерево, имеющее выделенную вершину (корень или источник), и каждое поддерево, прикрепленное к этой вершине, содержит не более c вершин. Величина c называется емкостью дерева. Оптимальное решение задачи CMST является NP-трудным, но хорошие эвристики, такие как Эсау-Уильямса и Шарма, дают решения, близкие к оптимальным за полиномиальное время. Остовное дерево с ограниченной степенью — это МСТ, в котором каждая вершина соединена не более чем с d другими вершинами, для некоторого заданного числа d. Случай d=2 является частным случаем задачи коммивояжера, поэтому остовное дерево с ограниченной степенью в общем случае является NP-трудным. Арборесценция — это вариант МСТ для ориентированных графов. Ее можно решить за время, используя алгоритм Чу-Лю/Эдмондса. Максимальное остовное дерево — это остовное дерево с весом, большим или равным весу любого другого остовного дерева. Такое дерево можно найти с помощью алгоритмов Прима или Краскала после умножения весов ребер на -1 и решения задачи МСТ для нового графа. Путь в максимальном остовном дереве — это самый широкий путь в графе между его двумя конечными точками: среди всех возможных путей он максимизирует вес ребра с минимальным весом. Максимальные остовные деревья находят применение в алгоритмах синтаксического анализа для естественных языков и в алгоритмах обучения для условных случайных полей. Задача динамического МСТ связана с обновлением ранее вычисленного МСТ после изменения веса ребра в исходном графе или вставки/удаления вершины. Задача минимальной маркировки остовного дерева состоит в поиске остовного дерева с наименьшим количеством типов меток, если каждое ребро в графе связано с меткой из конечного набора меток вместо веса. Ребро-узкое место — это ребро с наибольшим весом в остовном дереве. Остовное дерево является минимальным остовным деревом по узкому месту (MBST), если в графе нет остовного дерева с меньшим весом узкого места. МСТ обязательно является MBST (по свойству разреза), но MBST не обязательно является МСТ. Задача о кооперативной игре с минимальной стоимостью остовного дерева — это кооперативная игра, в которой игроки должны разделить между собой затраты на построение оптимального остовного дерева.