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

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

A минимальное остовное дерево (MST ) или минимальное остовное дерево является подмножеством ребра связного, взвешенного по ребрам неориентированного графа, который соединяет все вершины вместе, без каких-либо циклов и с минимально возможным общим весом ребер. То есть это остовное дерево , сумма весов ребер которого минимальна. В более общем смысле, любой неориентированный граф, взвешенный по ребрам (не обязательно связанный), имеет минимальный остовный лес, который представляет собой объединение минимальных остовных деревьев для его связных компонентов.

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

• 1 Свойства
  • 1.1 Возможная множественность
  • 1.2 Уникальность
  • 1.3 Подграф минимальной стоимости
  • 1.4 Свойство цикла
  • 1.5 Свойство Cut
  • 1.6 Ребро минимальной стоимости
  • 1.7 Сжатие
• 2 Алгоритмы
  • 2.1 Классические алгоритмы
  • 2.2 Более быстрые алгоритмы
  • 2.3 Линейные алгоритмы в особых случаях
    • 2.3.1 Плотные графы
    • 2.3.2 Целочисленные веса
  • 2.4 Деревья решений
  • 2.5 Оптимальный алгоритм
  • 2.6 Параллельные и распределенные алгоритмы
• 3 MST на полных графах
• 4 Приложения
• 5 Связанные проблемы
• 6 Ссылки
• 7 Дополнительная литература
• 8 Внешние ссылки

Возможная кратность

Если в графе n вершин, то каждое остовное дерево имеет n - 1 ребро.

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

Может быть несколько минимальных остовных деревьев одинакового веса; в частности, если все веса ребер данного графа одинаковы, то каждое остовное дерево этого графа является минимальным.

Уникальность

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

Доказательство:

1. Допустим противное, что есть два разных MST A и B.
2. Поскольку A и B различаются, несмотря на то, что они содержат одни и те же узлы, существует по крайней мере один край, принадлежащий одному, но не другому. Пусть среди таких ребер e 1 будет иметь наименьший вес; этот выбор уникален, потому что веса ребер различны. Без потери общности предположим, что e 1 находится в A.
3. Поскольку B является MST, {e 1} $\cup \; \{\backslash \; displaystyle\; \backslash \; cup\}$B должен содержат цикл C с e 1.
4. Как дерево, A не содержит циклов, поэтому C должно иметь ребро e 2, которого нет в A.
5. Поскольку e 1 был выбран как уникальное ребро с наименьшим весом среди ребер, принадлежащих ровно одному из A и B, вес e 2 должен быть больше веса e 1.
6. Поскольку e 1 и e 2 являются частью цикла C, поэтому замена e 2 на e 1 в B дает остовное дерево с меньшим весом.
7. Это противоречит предположению, что B является MST.

В более общем смысле, если веса ребер не все различны, то только (мульти-) набор весов в минимальных остовных деревьях обязательно будет уникальным; это то же самое для всех минимальных остовных деревьев.

Подграф с минимальной стоимостью

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

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

Для любого цикла C в графе, если вес ребра e ребра C больше, чем веса всех остальных ребер C, то это ребро не может принадлежать MST.

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

Свойство вырезания

На этом рисунке показано свойство вырезания MST-файлов. T - единственный MST данного графа. Если S = ​​{A, B, D, E}, таким образом, VS = {C, F}, тогда есть 3 возможности ребра через разрез (S, VS), это ребра BC, EC, EF оригинала. график. Тогда e является одним из ребер с минимальным весом для разреза, поэтому S ∪ {e} является частью MST T.

Для любого разреза C графа, если вес ребро e в разрезе C строго меньше, чем веса всех других ребер множества разрезов C, тогда это ребро принадлежит всем MST графа.

Доказательство: Предположим, что существует MST T, не содержащее e. Добавление e к T приведет к циклу, который пересекает разрез один раз в точке e и снова пересекает другую кромку e '. Удаляя e ', мы получаем остовное дерево T ∖ {e'} ∪ {e} строго меньшего веса, чем T. Это противоречит предположению, что T было MST.

Аналогичным образом, если более одного ребра имеет минимальный вес на разрезе, то каждое такое ребро содержится в некотором минимальном остовном дереве.

Ребро минимальной стоимости

Если ребро e минимальной стоимости графа уникально, то это ребро включается в любой MST.

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

Сжатие

Если T - дерево ребер MST, то мы можем сжать T в одну вершину, сохраняя при этом инвариант, что MST сжатого графа плюс T дает MST для графа перед сжатием.

Во всех приведенных ниже алгоритмах m - это количество ребер в графе, а n - количество вершин.

Классические алгоритмы

Первый алгоритм для поиска минимального остовного дерева был разработан чешским ученым Отакаром Борувкой в 1926 году (см. алгоритм Борувки ). Его целью было эффективное электрическое покрытие Моравии. Алгоритм работает в последовательности этапов. На каждом этапе, называемом шагом Борувки, он идентифицирует лес F, состоящий из ребра минимального веса, инцидентного каждой вершине в графе G, а затем формирует граф $G\; 1\; =\; G\; \setminus \; F\; \{\backslash \; displaystyle\; G\_\; \{1\}\; =\; G\; \backslash \; setminus\; F\}$в качестве входных данных для следующего шага. Здесь $G\; \setminus \; F\; \{\backslash \; displaystyle\; G\; \backslash \; setminus\; F\}$обозначает граф, полученный из G путем сжатия ребер в F (по свойству Cut эти ребра принадлежат MST). Каждый шаг Борувки занимает линейное время. Поскольку количество вершин уменьшается как минимум наполовину на каждом шаге, алгоритм Борувки занимает время O (m log n).

Второй алгоритм - это алгоритм Прима, который был изобретен Войтех Ярник в 1930 году и вновь обнаруженный Примом в 1957 году и Дейкстрой в 1959 году. В основном, MST (T) выращивается по одной кромке за раз. Изначально T содержит произвольную вершину. На каждом шаге T дополняется ребром наименьшего веса (x, y) таким образом, что x находится в T, а y еще не в T. По свойству Cut все ребра, добавленные к T, находятся в MST. Его время выполнения составляет O (m log n) или O (m + n log n), в зависимости от используемых структур данных.

Третий широко используемый алгоритм - это алгоритм Крускала, который также занимает время O (m log n).

Четвертый алгоритм, который не так широко используется, - это алгоритм обратного удаления, который является обратным алгоритму Крускала. Его время выполнения - O (m log n (log log n)).

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

Более быстрые алгоритмы

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

В модели сравнения, в которой единственными разрешенными операциями с весами ребер являются попарные сравнения, Karger, Klein Tarjan (1995) нашли рандомизированный алгоритм с линейным временем основан на комбинации алгоритма Борувки и алгоритма обратного удаления.

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

Алгоритмы линейного времени в особых случаях

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

Если граф плотный (т.е. m / n ≥ log log log n), то детерминированный алгоритм Фредмана и Тарьян находит MST за время O (m). Алгоритм выполняет несколько этапов. На каждой фазе алгоритм Прима выполняется много раз, каждый для ограниченного числа шагов. Время выполнения каждой фазы составляет O (m + n). Если количество вершин перед фазой равно $n\; \prime \; \{\backslash \; displaystyle\; n\; \text{'}\}$, количество вершин, оставшихся после фазы, не превышает $n\; \prime \; /\; 2\; m\; /\; n\; \prime \; \{\; \backslash \; Displaystyle\; n\; \text{'}/\; 2\; ^\; \{m\; /\; n\text{'}\}\}$. Следовательно, необходимо не более $log\; \ast \; \; n\; \{\backslash \; displaystyle\; \backslash \; log\; ^\; \{*\}\; \{n\}\}$фаз, что дает линейное время выполнения для плотных графов.

Существуют и другие алгоритмы, которые работают в линейном времени на плотных графах.

Целочисленные веса

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

Деревья решений

Для данного графа G, где узлы и ребра фиксированы, но веса неизвестны, можно построить двоичное дерево решений (DT) для вычисления MST для любой перестановки весов. Каждый внутренний узел DT содержит сравнение двух ребер, например «Является ли вес ребра между x и y больше, чем вес ребра между w и z?». Двум дочерним узлам соответствуют два возможных ответа «да» или «нет». В каждом листе DT есть список ребер из G, которые соответствуют MST. Сложность выполнения DT - это наибольшее количество запросов, необходимых для нахождения MST, что составляет всего лишь глубину DT. DT для графа G называется оптимальным, если оно имеет наименьшую глубину из всех правильных DT для G.

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

А. Генерация всех потенциальных DT

• Существует $2\; (r\; 2)\; \{\backslash \; displaystyle\; 2\; ^\; \{r\; \backslash \; choose\; 2\}\}$различных графов на r вершинах.
• Для каждого графа, MST всегда можно найти с помощью сравнений r (r-1), например по алгоритму Прима.
• Следовательно, глубина оптимального DT меньше, чем $r\; 2\; \{\backslash \; displaystyle\; r\; ^\; \{2\}\}$.
• Следовательно, количество внутренних узлов в оптимальном DT меньше чем $2\; r\; 2\; \{\backslash \; displaystyle\; 2\; ^\; \{r\; ^\; \{2\}\}\}$.
• Каждый внутренний узел сравнивает два ребра. Количество ребер не превышает $r\; 2\; \{\backslash \; displaystyle\; r\; ^\; \{2\}\}$, поэтому различное количество сравнений не превышает $r\; 4\; \{\backslash \; displaystyle\; r\; ^\; \{4\}\}$.
• Следовательно, количество потенциальных DT меньше, чем: $(r\; 4)\; (2\; r\; 2)\; =\; r\; 2\; (r\; 2\; +\; 2)\; \{\backslash \; displaystyle\; \{(r\; ^\; \{4\})\}\; ^\; \{(\; 2\; ^\; \{r\; ^\; \{2\}\})\}\; =\; r\; ^\; \{2\; ^\; \{(r\; ^\; \{2\}\; +2)\}\}\}$.

Б. Определение правильных ОУ Чтобы проверить правильность ОУ, необходимо проверить все возможные перестановки весов ребер.

• Число таких перестановок не превышает $(r\; 2)!\; \{\backslash \; displaystyle\; (r\; ^\; \{2\})!\}$.
• Для каждой перестановки решите задачу MST на заданном графе, используя любой существующий алгоритм, и сравните результат с ответом, данным DT.
• Время работы любого алгоритма MST составляет не более $(r\; 2)\; \{\backslash \; displaystyle\; (r\; ^\; \{2\})\}$, поэтому общее время, необходимое для проверки всех перестановок, не превышает $(г\; 2\; +\; 1)!\; \{\backslash \; displaystyle\; (r\; ^\; \{2\}\; +1)!\}$.

Следовательно, общее время, необходимое для нахождения оптимального DT для всех графов с r вершинами, составляет: $2\; (r\; 2)\; \cdot \; r\; 2\; (r\; 2\; +\; 2)\; \cdot \; (г\; 2\; +\; 1)!\; \{\backslash \; displaystyle\; 2\; ^\; \{r\; \backslash \; choose\; 2\}\; \backslash \; cdot\; r\; ^\; \{2\; ^\; \{(r\; ^\; \{2\}\; +2)\}\}\; \backslash \; cdot\; (r\; ^\; \{2\}\; +1)!\}$, что меньше чем: $2\; 2\; r\; 2\; +\; o\; (r)\; \{\backslash \; displaystyle\; 2\; ^\; \{2\; ^\; \{r\; ^\; \{2\}\; +\; o\; (r)\}\}\}$.

Оптимальный алгоритм

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

1. Пусть $r\; =\; log\; \; log\; \; log\; \; n\; \{\backslash \; displaystyle\; r\; =\; \backslash \; log\; \backslash \; log\; \backslash \; log\; n\}$, где n - количество вершин. Найдите все оптимальные деревья решений на r вершинах. Это можно сделать за время O (n) (см. Деревья решений выше).
2. Разделите граф на компоненты с не более чем r вершинами в каждом компоненте. Этот раздел использует мягкую кучу, которая «портит» небольшое количество ребер графа.
3. Используйте оптимальные деревья решений, чтобы найти MST для неповрежденного подграфа в каждом компоненте.
4. Сожмите каждый компонент связности, охватываемый MST, с одной вершиной и примените любой алгоритм, который работает на плотных графах за время O (m), к сжатию неповрежденного подграфа
5. Добавьте обратно поврежденные ребра к результирующему лесу, чтобы сформировать подграф, который гарантированно содержит минимальное остовное дерево и на постоянный коэффициент меньше исходного графа. Рекурсивно примените оптимальный алгоритм к этому графу.

Время выполнения всех шагов в алгоритме составляет O (m), за исключением шага использования деревьев решений. Время выполнения этого шага неизвестно, но было доказано, что он оптимален - ни один алгоритм не может работать лучше, чем оптимальное дерево решений. Таким образом, этот алгоритм обладает тем особенным свойством, что он доказуемо оптимален, хотя сложность его выполнения неизвестна.

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

Исследователи также рассмотрели параллельные алгоритмы для задачи минимального связующего дерева. При линейном количестве процессоров можно решить проблему за $O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$времени. Bader Cong (2006) продемонстрировать алгоритм, который может вычислять MST в 5 раз быстрее на 8 процессорах, чем оптимизированный последовательный алгоритм.

Другие специализированные алгоритмы были разработаны для вычисления минимальных остовных деревьев графа настолько большого размера, что большая их часть должна быть всегда хранятся на диске. Эти алгоритмы внешнего хранилища, например, описанные в статье Романа, Дементьева и др. В статье «Разработка алгоритма минимального связующего дерева внешней памяти», могут работать, по утверждениям авторов, всего в 2-5 раз медленнее, чем традиционные алгоритмы в памяти. алгоритм. Они полагаются на эффективные алгоритмы сортировки внешнего хранилища и на методы сжатия графа для эффективного уменьшения размера графа.

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

Алан М. Фриз показал, что данные полный граф на n вершинах, с весами ребер, которые являются независимыми одинаково распределенными случайными величинами с функцией распределения $F\; \{\backslash \; displaystyle\; F\}$, удовлетворяющей $F\; \text{'}(0)>0\; \{\backslash \; displaystyle\; F\; \text{'}(0)>0\}$, тогда, когда n приближается к + ∞, ожидаемый вес MST приближается к $\zeta \; (3)\; /\; F\; \prime \; (0)\; \{\backslash \; displaystyle\; \backslash \; zeta\; (\; 3)\; /\; F\; \text{'}(0)\}$, где $\zeta \; \{\backslash \; displaystyle\; \backslash \; zeta\}$- это дзета-функция Римана (точнее, $\zeta \; (3)\; \{\backslash \; displaystyle\; \backslash \; zeta\; (3)\}$постоянная Апери ). Frieze и Steele также доказали сходимость по вероятности lity. Сванте Янсон доказал центральную предельную теорему для веса MST.

Для однородных случайных весов в $[0,\; 1]\; \{\backslash \; displaystyle\; [0,1]\}$, точный ожидаемый размер минимального связующего дерева был вычислен для малых полных графиков.

Вершины	Ожидаемый размер	Приблизительный ожидаемый размер
2	1/2	0,5
3	3/4	0,75
4	31/35	0,8857143
5	893/924	0,9664502
6	278/273	1,0183151
7	30739/29172	1.053716
8	199462271/184848378	1.0790588
9	126510063932/115228853025	1.0979027

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

Другие практические приложения, основанные на минимальных остовных деревьях, включают:

• Таксономия.
• Кластерный анализ : точки кластеризации на плоскости, однократная кластеризация (метод иерархической кластеризации ), теоретико-графическая кластеризация и кластеризация экспрессии генов данных.
• Построение деревьев для вещания в компьютерных сетях.
• Регистрация изображения и сегментация - см. минимальная сегментация на основе связующего дерева.
• Криволинейное извлечение признаков в компьютерное зрение.
• Распознавание почерка математических выражений.
• Circui t дизайн : реализация эффективного многократного умножения констант, как используется в фильтрах с конечной импульсной характеристикой.
• Регионализация социально-географических областей, группировка областей в однородные смежные области.
• Сравнение данных по экотоксикологии.
• Топологическая наблюдаемость в энергосистемах.
• Измерение однородности двумерных материалов.
• Минимакс управление процессом.
• Минимальные остовные деревья также могут использоваться для описания финансовых рынков. Матрица корреляции может быть создана путем вычисления коэффициента корреляции между любыми двумя акциями. Эта матрица может быть представлена ​​топологически как сложная сеть, и минимальное остовное дерево может быть построено для визуализации взаимосвязей.

Минимальные деревья Штейнера вершин правильных многоугольников с N = от 3 до 8 сторон. Наименьшая длина сети L для N>5 - это длина окружности без одной стороны. Квадраты представляют точки Штейнера.

Проблема поиска дерева Штейнера подмножества вершин, то есть минимального дерева, охватывающего данное подмножество, известна как NP-Complete.

Связанная проблема - это k-минимальное остовное дерево (k-MST), которое представляет собой дерево, которое охватывает некоторое подмножество из k вершин в графе с минимальным весом.

Набор k-наименьших остовных деревьев - это подмножество k остовных деревьев (из всех возможных остовных деревьев), такое, что никакое остовное дерево вне подмножества не имеет меньшего веса. (Обратите внимание, что эта проблема не связана с k-минимальным остовным деревом.)

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

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

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

Ограниченное минимальное остовное дерево - это дерево, которое имеет отмеченный узел (источник или корень), и каждое из поддеревьев, прикрепленных к узлу, содержит не более c узлов. c называется емкостью дерева. Оптимальное решение CMST NP-сложно, но хорошие эвристики, такие как Исау-Вильямс и Шарма, дают решения, близкие к оптимальным по полиномиальному времени.

Минимальное остовное дерево с ограничениями по степени - это минимальное остовное дерево, в котором каждая вершина соединена не более чем с d другими вершинами для некоторого заданного числа d. Случай d = 2 является частным случаем задачи коммивояжера , поэтому минимальное остовное дерево с ограничениями по степени в целом является NP-hard.

Для ориентированных графов проблема минимального остовного дерева называется проблемой Arborescence и может быть решена за квадратичное время с использованием алгоритма Чу – Лю / Эдмондса..

A максимальное связующее дерево - это связующее дерево, вес которого больше или равен весу любого другого связующего дерева. Такое дерево можно найти с помощью таких алгоритмов, как Prim или Kruskal, после умножения весов ребер на -1 и решения проблемы MST на новом графе. Путь в максимальном остовном дереве - это самый широкий путь в графе между двумя его конечными точками: среди всех возможных путей он максимизирует вес ребра с минимальным весом. Максимальные связующие деревья находят применение в алгоритмах синтаксического анализа для естественных языков и в алгоритмах обучения для условных случайных полей.

Проблема динамического MST касается обновления ранее вычисленного MST после изменения веса ребер в исходном графе или вставки / удаления вершины.

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

Ребро узкого места - это ребро с максимальным весом в остовном дереве. Остовное дерево - это остовное дерево минимального узкого места (или MBST ), если граф не содержит остовного дерева с меньшим весом ребра узкого места. MST обязательно является MBST (доказывается с помощью свойства cut), но MBST не обязательно является MST.

• Отакар Борувка на Задача минимального остовного дерева (перевод обеих статей 1926 г., комментарии, история) (2000) Ярослав Нешетржил, Ева Милкова, Хелена Несетрилова. (В разделе 7 приводится его алгоритм, который выглядит как нечто среднее между алгоритмом Прима и Крускала.)
• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Стейн. Введение в алгоритмы, второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7. Глава 23: Минимальные остовные деревья, стр. 561–579.
• Эйснер, Джейсон (1997). Современные алгоритмы для минимальных остовных деревьев: Обсуждение в учебном пособии. Рукопись, Пенсильванский университет, апрель. 78 с.
• Кромковский, Джон Дэвид. «Все еще не растаял после всех этих лет», в Annual Editions, Race and Ethnic Relations, 17 / e (McGraw Hill, 2009 г.) (Использование минимального остовного дерева как метода демографического анализа этнического разнообразия в США).

На Викискладе есть материалы, относящиеся к Минимальным остовным деревьям.

• Реализованным в BGL, Библиотеке графов ускорения
• Репозиторий алгоритмов Стоуни-Брук - Минимальные коды остовного дерева
• Реализованы в QuickGraph для. Сеть