Минимальное остовное дерево - Minimum spanning tree - Wikipedia

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

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

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

Характеристики

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

Если есть п вершин в графе, то каждое остовное дерево имеет п − 1 края.

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

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

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

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

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

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

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

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

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

Цикл свойство

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

Доказательство: Предположим противное, т.е. что е принадлежит MST Т₁. Затем удаление е сломает Т₁ на два поддерева с двумя концами е в разных поддеревьях. Остальная часть C повторно соединяет поддеревья, следовательно, есть ребро ж из C с концами в разных поддеревьях, т.е. повторно соединяет поддеревья в дерево Т₂ с весом меньше, чем у Т₁, потому что вес ж меньше веса е.

Вырезать собственность

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

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

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

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

Преимущество минимальной стоимости

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

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

Сокращение

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

Алгоритмы

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

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

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

Второй алгоритм Алгоритм Прима, который был изобретен Войтех Ярник в 1930 году и заново открыт Prim в 1957 г. и Dijkstra в 1959 г. В основном это выращивает МСТ (Т) по одному краю за раз. Первоначально, Т содержит произвольную вершину. На каждом этапе Т дополняется ребром наименьшего веса (Икс,у) такие, что Икс в Т и у еще не в Т. Посредством Вырезать собственность, все ребра добавлены к Т находятся в MST. Его время выполнения - O (м бревно п) или O (м + п бревно п), в зависимости от используемых структур данных.

Третий широко используемый алгоритм: Алгоритм Краскала, который также принимает O (м бревно п) время.

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

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

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

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

В модели сравнения, в которой единственными разрешенными операциями с весами ребер являются попарные сравнения, Каргер, Кляйн и Тарьян (1995) найти рандомизированный алгоритм с линейным временем основан на комбинации алгоритма Борувки и алгоритма обратного удаления.^[3][4]

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

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

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

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

Есть и другие алгоритмы, которые работают в линейное время на плотных графах.^[5][8]

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

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

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

Данный граф грамм где узлы и ребра фиксированы, но веса неизвестны, можно построить двоичный Древо решений (DT) для вычисления MST для любой перестановки весов. Каждый внутренний узел DT содержит сравнение двух ребер, например "Вес края между Икс и у больше, чем вес края между ш и z? ". Двум дочерним узлам соответствуют два возможных ответа" да "или" нет ". На каждом листе DT есть список ребер из грамм которые соответствуют MST. Сложность выполнения DT - это наибольшее количество запросов, необходимых для поиска MST, что составляет всего лишь глубину DT. ОД для графа грамм называется оптимальный если он имеет наименьшую глубину из всех правильных ОД для грамм.

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

A. Создание всех потенциальных DT

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

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

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

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

Смотрите также: Модель дерева решений

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

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

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

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

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

Дальнейшая информация: Параллельные алгоритмы для минимальных остовных деревьев

Исследования также рассмотрели параллельные алгоритмы для задачи минимального остовного дерева. с линейным числом процессоров можно решить задачу в ${\displaystyle O(\log n)}$ время.^[10][11]Бадер и Конг (2006) продемонстрируйте алгоритм, который может вычислять MST в 5 раз быстрее на 8 процессорах, чем оптимизированный последовательный алгоритм.^[12]

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

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

MST на полных графиках

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

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

Вершины	Ожидаемый размер	Примерный ожидаемый размер
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

Приложения

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

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

• Таксономия.^[19]
• Кластерный анализ: точки кластеризации на плоскости,^[20] одинарная кластеризация (метод иерархическая кластеризация ),^[21] теоретико-графическая кластеризация,^[22] и кластеризация экспрессия гена данные.^[23]
• Построение деревьев для вещание в компьютерных сетях.^[24]
• Регистрация изображения^[25] и сегментация^[26] - видеть минимальная сегментация на основе остовного дерева.
• Криволинейный извлечение признаков в компьютерное зрение.^[27]
• Распознавание почерка математических выражений.^[28]
• Схемотехника: реализация эффективного многократного умножения констант, как используется в конечная импульсная характеристика фильтры.^[29]
• Регионализация социально-географических зон, группировка территорий в однородные, смежные регионы.^[30]
• Сравнение экотоксикология данные.^[31]
• Топологический наблюдаемость в энергосистемах.^[32]
• Измерение однородности двумерных материалов.^[33]
• Минимакс контроль над процессом.^[34]
• Минимальные остовные деревья также можно использовать для описания финансовых рынков.^[35][36] Матрица корреляции может быть создана путем вычисления коэффициента корреляции между любыми двумя акциями. Эта матрица может быть представлена ​​топологически как сложная сеть, и минимальное остовное дерево может быть построено для визуализации взаимосвязей.

Связанные проблемы

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

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

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

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

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

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

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

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

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

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

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

В динамический MST проблема касается обновления ранее вычисленного MST после изменения веса ребра в исходном графе или вставки / удаления вершины.^[44][45][46]

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

Ребро узкого места - это край с самым высоким весом в остовном дереве. Остовное дерево - это остовное дерево с минимальным узким местом (или же MBST), если граф не содержит остовного дерева с меньшим весом ребра узкого места. MST обязательно является MBST (доказывается вырезать собственность ), но MBST не обязательно является MST.^[48][49]

Рекомендации

1. «Имеют ли минимальные остовные деревья взвешенного графа одинаковое количество ребер с заданным весом?». cs.stackexchange.com. Получено 4 апреля 2018.
2. Петти, Сет; Рамачандран, Виджая (2002), «Оптимальный алгоритм минимального остовного дерева» (PDF), Журнал Ассоциации вычислительной техники, 49 (1): 16–34, Дои:10.1145/505241.505243, МИСТЕР  2148431, S2CID  5362916.
3. Каргер, Дэвид Р.; Klein, Philip N .; Тарджан, Роберт Э. (1995), "Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев", Журнал Ассоциации вычислительной техники, 42 (2): 321–328, Дои:10.1145/201019.201022, МИСТЕР  1409738, S2CID  832583
4. Петти, Сет; Рамачандран, Виджая (2002), «Минимизация случайности в минимальном остовном дереве, параллельная связность и алгоритмы установки максимума», Proc. 13-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '02), Сан-Франциско, Калифорния, стр. 713–722..
5. Шазель, Бернар (2000), "Минимальный алгоритм остовного дерева с обратной сложностью типа Аккермана", Журнал Ассоциации вычислительной техники, 47 (6): 1028–1047, Дои:10.1145/355541.355562, МИСТЕР  1866456, S2CID  6276962.
6. Шазель, Бернар (2000), «Мягкая куча: примерная приоритетная очередь с оптимальной частотой ошибок» (PDF), Журнал Ассоциации вычислительной техники, 47 (6): 1012–1027, Дои:10.1145/355541.355554, МИСТЕР  1866455, S2CID  12556140.
7. Fredman, M. L .; Тарьян, Р. Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». Журнал ACM. 34 (3): 596. Дои:10.1145/28869.28874. S2CID  7904683.
8. Gabow, H.N .; Галил, З .; Спенсер, Т .; Тарьян, Р. Э. (1986). «Эффективные алгоритмы поиска минимальных остовных деревьев в неориентированных и ориентированных графах». Комбинаторика. 6 (2): 109. Дои:10.1007 / bf02579168. S2CID  35618095.
9. Фредман, М.Л.; Уиллард, Д. Э. (1994), «Транс-дихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук, 48 (3): 533–551, Дои:10.1016 / S0022-0000 (05) 80064-9, МИСТЕР  1279413.
10. Чонг, Ка Вонг; Хан, Ицзе; Лам, Так Ва (2001), "Параллельные потоки и алгоритм оптимального параллельного минимального остовного дерева", Журнал Ассоциации вычислительной техники, 48 (2): 297–323, Дои:10.1145/375827.375847, МИСТЕР  1868718, S2CID  1778676.
11. Петти, Сет; Рамачандран, Виджая (2002), «Рандомизированный оптимальный по времени параллельный алгоритм для поиска минимального остовного леса» (PDF), SIAM Журнал по вычислениям, 31 (6): 1879–1895, Дои:10.1137 / S0097539700371065, МИСТЕР  1954882.
12. Бадер, Дэвид А.; Конг, Гоцзин (2006), «Быстрые алгоритмы с общей памятью для вычисления минимального остовного леса разреженных графов», Журнал параллельных и распределенных вычислений, 66 (11): 1366–1378, Дои:10.1016 / j.jpdc.2006.06.001, S2CID  2004627.
13. Дементьев, Роман; Сандерс, Питер; Шультес, Доминик; Сибейн, Джоп Ф. (2004), "Разработка алгоритма минимального остовного дерева внешней памяти", Proc. 18-й Всемирный компьютерный конгресс IFIP, 3-я Международная конференция TC1 по теоретической информатике (TCS2004) (PDF), стр. 195–208.
14. Стил, Дж. Майкл (2002), «Минимальные остовные деревья для графов со случайной длиной ребер», Математика и информатика, II (Версаль, 2002), Trends Math., Базель: Birkhäuser, стр. 223–245, МИСТЕР  1940139
15. Грэм, Р. Л.; Ад, Павол (1985), "К истории проблемы минимального остовного дерева", Анналы истории вычислительной техники, 7 (1): 43–57, Дои:10.1109 / MAHC.1985.10011, МИСТЕР  0783327, S2CID  10555375
16. Никос Христофидес, Анализ наихудшего случая новой эвристики для задачи коммивояжера, Отчет 388, Высшая школа промышленного администрирования, CMU, 1976.
17. Dahlhaus, E .; Джонсон, Д.С.; Пападимитриу, К.; Сеймур, П. Д.; Яннакакис, М. (Август 1994 г.). «Сложность многотерминальных разрезов» (PDF). SIAM Журнал по вычислениям. 23 (4): 864–894. Дои:10.1137 / S0097539792225297. Архивировано из оригинал (PDF) 24 августа 2004 г.. Получено 17 декабря 2012.
18. Supowit, Kenneth J .; Плейстед, Дэвид А .; Рейнгольд, Эдвард М. (1980). Эвристика для взвешенного идеального соответствия. 12-й ежегодный симпозиум ACM по теории вычислений (STOC '80). Нью-Йорк, Нью-Йорк, США: ACM. С. 398–419. Дои:10.1145/800141.804689.
19. Снит, П. Х. А. (1 августа 1957 г.). «Применение компьютеров в таксономии». Журнал общей микробиологии. 17 (1): 201–226. Дои:10.1099/00221287-17-1-201. PMID  13475686.
20. Асано, Т.; Bhattacharya, B .; Keil, M .; Яо, Ф. (1988). Алгоритмы кластеризации на основе минимального и максимального остовных деревьев. Четвертый ежегодный симпозиум по вычислительной геометрии (SCG '88). 1. С. 252–257. Дои:10.1145/73393.73419.
21. Gower, J.C .; Росс, Дж. Дж. С. (1969). «Минимальные связующие деревья и кластерный анализ единственной связи». Журнал Королевского статистического общества. C (Прикладная статистика). 18 (1): 54–64. Дои:10.2307/2346439. JSTOR  2346439.
22. Пяйвинен, Ниина (1 мая 2005 г.). «Кластеризация с минимальным остовным деревом безмасштабной структуры». Письма с распознаванием образов. 26 (7): 921–930. Дои:10.1016 / j.patrec.2004.09.039.
23. Xu, Y .; Olman, V .; Сюй Д. (1 апреля 2002 г.). «Кластеризация данных экспрессии генов с использованием теоретико-графического подхода: применение минимальных остовных деревьев». Биоинформатика. 18 (4): 536–545. Дои:10.1093 / биоинформатика / 18.4.536. PMID  12016051.
24. Далал, Йоген К .; Меткалф, Роберт М. (1 декабря 1978 г.). «Пересылка широковещательных пакетов по обратному пути». Коммуникации ACM. 21 (12): 1040–1048. Дои:10.1145/359657.359665. S2CID  5638057.
25. Ma, B .; Герой, А .; Gorman, J .; Мишель, О. (2000). Регистрация изображений с помощью алгоритма минимального остовного дерева (PDF). Международная конференция по обработке изображений. 1. С. 481–484. Дои:10.1109 / ICIP.2000.901000.
26. П. Фельценшвалб, Д. Хуттенлохер: Эффективная сегментация изображений на основе графов. IJCV 59 (2) (сентябрь 2004 г.)
27. Сук, Минсу; Сон, Охён (1 июня 1984 г.). «Извлечение криволинейных объектов с использованием минимальных остовных деревьев». Компьютерное зрение, графика и обработка изображений. 26 (3): 400–411. Дои:10.1016 / 0734-189X (84) 90221-4.
28. Тапиа, Эрнесто; Рохас, Рауль (2004). «Распознавание он-лайн рукописных математических выражений с использованием построения минимального связующего дерева и доминирования символов» (PDF). Распознавание графики. Последние достижения и перспективы. Конспект лекций по информатике. 3088. Берлин Гейдельберг: Springer-Verlag. С. 329–340. ISBN  978-3540224785.
29. Олссон, Х. (2004). Реализация КИХ-фильтров низкой сложности с использованием минимального остовного дерева. 12-я Средиземноморская электротехническая конференция IEEE (MELECON 2004). 1. С. 261–264. Дои:10.1109 / MELCON.2004.1346826.
30. AssunÇão, R. M .; М. К. Невес; Г. Камара; К. Да Коста Фрейтас (2006 г.). «Эффективные методы регионализации для социально-экономических географических единиц с использованием минимальных остовных деревьев». Международный журнал географической информатики. 20 (7): 797–811. Дои:10.1080/13658810600665111. S2CID  2530748.
31. Devillers, J .; Дор, Дж. К. (1 апреля 1989 г.). «Эвристическая эффективность метода минимального остовного дерева (MST) в токсикологии». Экотоксикология и экологическая безопасность. 17 (2): 227–235. Дои:10.1016/0147-6513(89)90042-0. PMID  2737116.
32. Mori, H .; Цузуки, С. (1 мая 1991 г.). «Быстрый метод анализа топологической наблюдаемости с использованием метода минимального остовного дерева». Транзакции IEEE в системах питания. 6 (2): 491–500. Дои:10.1109/59.76691.
33. Филлибен, Джеймс Дж .; Кафадар, Карен; Шайер, Дуглас Р. (1 января 1983 г.). «Проверка на однородность двумерных поверхностей». Математическое моделирование. 4 (2): 167–189. Дои:10.1016 / 0270-0255 (83) 90026-Х.
34. Калаба, Роберт Э. (1963), Теория графов и автоматическое управление (PDF)
35. Мантенья, Р. Н. (1999). Иерархическая структура на финансовых рынках. Европейский физический журнал B-конденсированное вещество и сложные системы, 11 (1), 193-197.
36. Джаухари М. и Ган С. (2015). Проблема оптимальности сетевой топологии в анализе фондового рынка. Physica A: Статистическая механика и ее приложения, 419, 108-114.
37. Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, В. Х. Фриман, ISBN  0-7167-1045-5. ND12
38. Габоу, Гарольд Н. (1977), "Два алгоритма построения взвешенных остовных деревьев по порядку", SIAM Журнал по вычислениям, 6 (1): 139–150, Дои:10.1137/0206011, МИСТЕР  0441784.
39. Эппштейн, Дэвид (1992), "В поисках k самые маленькие остовные деревья », КУСОЧЕК, 32 (2): 237–248, Дои:10.1007 / BF01994879, МИСТЕР  1172188, S2CID  121160520.
40. Фредериксон, Грег Н. (1997), "Амбивалентные структуры данных для динамического подключения двух сторон и k самые маленькие остовные деревья ", SIAM Журнал по вычислениям, 26 (2): 484–538, Дои:10.1137 / S0097539792226825, МИСТЕР  1438526.
41. Джоти, Раджа; Рагхавачари, Баладжи (2005), «Алгоритмы аппроксимации для задачи минимального связующего дерева с ограниченными возможностями и ее варианты при проектировании сети», ACM Trans. Алгоритмы, 1 (2): 265–282, Дои:10.1145/1103963.1103967, S2CID  8302085
42. Ху, Т. С. (1961), "Проблема маршрута с максимальной пропускной способностью", Исследование операций, 9 (6): 898–900, Дои:10.1287 / opre.9.6.898, JSTOR  167055.
43. Макдональд, Райан; Перейра, Фернандо; Рибаров, Кирилл; Гайч, Ян (2005). «Непроективный анализ зависимостей с использованием алгоритмов связующего дерева» (PDF). Proc. HLT / EMNLP.
44. Spira, P. M .; Пан, А. (1975), «О поиске и обновлении остовных деревьев и кратчайших путей» (PDF), SIAM Журнал по вычислениям, 4 (3): 375–380, Дои:10.1137/0204032, МИСТЕР  0378466.
45. Холм, Джейкоб; де Лихтенберг, Кристиан; Торуп, Миккель (2001), «Полилогарифмические детерминированные полностью динамические алгоритмы для подключения, минимального остовного дерева, 2-ребер и двусвязности», Журнал Ассоциации вычислительной техники, 48 (4): 723–760, Дои:10.1145/502090.502095, МИСТЕР  2144928, S2CID  7273552.
46. Подбородок, F .; Хаук Д. (1978), "Алгоритмы обновления минимальных остовных деревьев", Журнал компьютерных и системных наук, 16 (3): 333–344, Дои:10.1016/0022-0000(78)90022-3.
47. Chang, R.S .; Лей, С.Дж. (1997), «Минимальные обозначения остовных деревьев», Письма об обработке информации, 63 (5): 277–282, Дои:10.1016 / s0020-0190 (97) 00127-0.
48. «Все о связующем дереве по узким местам». flashing-gotits.blogspot.ru. Получено 4 апреля 2018.
49. http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf

дальнейшее чтение

• Отакар Борувка о проблеме минимального остовного дерева (перевод обеих статей 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 для .Net