Минимальное связующее дерево

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

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

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

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

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

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

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

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

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

Предположим противное , что существуют два разных $A$ и $B.$ MST
Поскольку $A$ и $B$ различаются, несмотря на то, что содержат одни и те же узлы, существует хотя бы одно ребро, принадлежащее одному, но не принадлежащее другому. Среди таких ребер пусть $e 1$ — ребро с наименьшим весом; этот выбор уникален, поскольку все веса ребер различны. Без ограничения общности предположим, что $e 1$ находится в $A$ .
Поскольку $B$ является MST, ${e 1} \cup B$ должен содержать цикл $C$ с $e 1$ .
Как дерево, $A$ не содержит циклов, поэтому $должно$ иметь ребро $e2,$ которого нет в $A.$ C
Поскольку $e 1$ было выбрано как единственное ребро с наименьшим весом среди ребер, принадлежащих ровно одному из $A$ и $B$ , вес $e 2$ должен быть больше веса $e 1$ .
Поскольку $e1 дает$ и $e2 являются$ цикла $C$ , замена $e2 e1$ на $частью .$ в $B$ остовное дерево с меньшим весом
Это противоречит предположению, что $B$ является MST.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сокращение

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

Алгоритмы

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

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

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

Второй алгоритм — это алгоритм Прима , который был изобретен Войтехом Ярником в 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) 3)$ .

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

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

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

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

Самый быстрый нерандомизированный алгоритм сравнения с известной сложностью, разработанный Бернаром Шазелем , основан на мягкой куче — приблизительной очереди с приоритетами. ^[7]^[8] Время его работы равно $O (m α(m, n))$ , где $α$ — классический функционал, обратный функции Аккермана . Функция $α$ растет крайне медленно, так что для всех практических целей ее можно считать константой, не превышающей 4; таким образом, алгоритм Шазеля требует очень близкого к линейному времени.

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

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

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

Существуют и другие алгоритмы, которые работают за линейное время на плотных графах. ^[7]^[10]

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

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

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

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

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

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

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

${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.$

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

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

Следовательно, общее время, необходимое для поиска оптимального DT для всех графов с $r$ вершинами, равно: ^[4]

2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,

что меньше, чем

2^{2^{r^{2}+o(r)}}.

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

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

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

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

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

В исследованиях также рассматривались параллельные алгоритмы для решения задачи минимального остовного дерева. При линейном числе процессоров задачу можно решить за $время O (log n)$ . ^[12]^[13]

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

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

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

Для равномерных случайных весов в $[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

Дробный вариант

Существует дробный вариант MST, в котором каждому ребру разрешено появляться «дробно». Формально, дробное остовное множество графа (V,E) — это неотрицательная функция f на E такая, что для каждого нетривиального подмножества W графа V (т. е. W не пусто и не равно V ), сумма f ( e ) по всем ребрам, соединяющим узел W с узлом V \ W , равно как минимум 1. Интуитивно f ( e ) представляет долю e, содержащуюся в связующем множестве. Минимальный дробный набор охвата — это дробный набор охвата, для которого сумма $\sum _{e\in E}f(e)\cdot w(e)$ как можно меньше.

Если дроби f ( e ) вынуждены находиться в {0,1}, то набор T ребер с f(e) = 1 является связующим набором, поскольку каждый узел или подмножество узлов соединены с остальной частью граф хотя бы по одному ребру T . Более того, если f минимизирует $\sum _{e\in E}f(e)\cdot w(e)$ , то полученное связующее множество обязательно является деревом, поскольку, если бы оно содержало цикл, то ребро можно было бы удалить, не затрагивая условие охвата. Таким образом, проблема минимального дробного охватывающего множества является смягчением проблемы MST и может также называться проблемой дробного MST.

Задача дробного MST может быть решена за полиномиальное время с использованием метода эллипсоидов . ^[15]^: 248 Однако если мы добавим требование, чтобы f ( e ) было полуцелым числом (то есть f ( e ) должно находиться в {0, 1/2, 1}), то проблема становится NP-сложной , ^[15]^: 248 поскольку она включает в себя в качестве частного случая проблему гамильтонова цикла : в $n$ -вершинный невзвешенный граф, полуцелое значение MST веса $n/2$ может быть получено только путем присвоения веса 1/2 каждому ребру гамильтонова цикла.

Другие варианты

Дерево Штейнера подмножества вершин — это минимальное дерево, охватывающее данное подмножество. Нахождение дерева Штейнера является NP-полным . ^[16]

k - минимальное остовное дерево ( k -MST) — это дерево, которое охватывает некоторое подмножество из k вершин графа с минимальным весом.
Набор k-наименьших остовных деревьев — это подмножество k остовных деревьев (из всех возможных остовных деревьев), такое, что ни одно остовное дерево вне этого подмножества не имеет меньшего веса. ^[17]^[18]^[19] (Обратите внимание, что эта проблема не связана с k -минимальным остовным деревом.)
Евклидово минимальное остовное дерево — это остовное дерево графа с весами ребер, соответствующими евклидову расстоянию между вершинами, которые являются точками на плоскости (или пространстве).
Прямолинейное минимальное остовное дерево — это остовное дерево графа с весами ребер, соответствующими прямолинейному расстоянию между вершинами, которые являются точками на плоскости (или пространстве).
Распределенное минимальное связующее дерево является расширением MST для распределенной модели , где каждый узел считается компьютером, и ни один узел не знает ничего, кроме своих собственных подключенных каналов. Математическое определение проблемы одно и то же, но существуют разные подходы к решению.
Минимальное связующее дерево с емкостью — это дерево, имеющее отмеченный узел (исходное место или корень), и каждое из поддеревьев, прикрепленных к этому узлу, содержит не более c узлов. c называется емкостью дерева. Оптимальное решение CMST NP-сложно . ^[20] но хорошие эвристики, такие как Эсау-Вильямс и Шарма, дают решения, близкие к оптимальным, за полиномиальное время.
Минимальное остовное дерево с ограничением по степени — это MST, в котором каждая вершина соединена не более чем с d другими вершинами для некоторого заданного числа d . Случай d = 2 является частным случаем задачи коммивояжера , поэтому минимальное остовное дерево с ограничением степени в целом является NP-трудным .
Древовидность — это вариант MST для ориентированных графов . Это можно решить в $O(E+V\log V)$ время с использованием алгоритма Чу-Лю/Эдмондса .
Максимальное связующее дерево — это связующее дерево, вес которого больше или равен весу любого другого связующего дерева. Такое дерево можно найти с помощью таких алгоритмов, как алгоритм Прима или Крускала, после умножения весов ребер на -1 и решения задачи MST на новом графе. Путь в максимальном остовном дереве — это самый широкий путь в графе между двумя его конечными точками: среди всех возможных путей он максимизирует вес ребра с минимальным весом. ^[21] Максимальные остовные деревья находят применение в синтаксического анализа алгоритмах естественных языков. ^[22] и в алгоритмах обучения условным случайным полям .
Проблема динамического MST касается обновления ранее вычисленного MST после изменения веса ребра в исходном графе или вставки/удаления вершины. ^[23]^[24]^[25]
состоит Задача остовного дерева с минимальной разметкой в том, чтобы найти остовное дерево с наименьшим количеством типов меток, если каждое ребро в графе связано с меткой из конечного набора меток вместо веса. ^[26]
Ребро узкого места — это ребро с наибольшим весом в связующем дереве. Охватывающее дерево является минимальным связующим деревом с узким местом (или MBST ), если граф не содержит остовное дерево с меньшим весом ребра узкого места. MST обязательно является MBST (что доказывается свойством вырезания ), но MBST не обязательно является MST. ^[27]^[28]
Игра с остовным деревом с минимальной стоимостью — это совместная игра, в которой игроки должны разделить между собой затраты на построение оптимального остовного дерева.
Задача оптимального проектирования сети — это задача вычисления набора с учетом бюджетных ограничений, который содержит связующее дерево, такое, что сумма кратчайших путей между каждой парой узлов является как можно меньшей.

Приложения

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

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

Таксономия . ^[33]
Кластерный анализ : кластеризация точек на плоскости, ^[34] односвязная кластеризация (метод иерархической кластеризации ), ^[35] теоретико-графовая кластеризация, ^[36] и кластеризация об экспрессии генов . данных ^[37]
Построение деревьев для вещания в компьютерных сетях. ^[38]
Регистрация изображения ^[39] и сегментация ^[40] – см. минимальную сегментацию на основе связующего дерева .
криволинейных Выделение признаков в компьютерном зрении . ^[41]
Распознавание рукописного ввода математических выражений. ^[42]
Проектирование схемы : реализация эффективного многократного умножения констант, используемого в фильтрах с конечной импульсной характеристикой . ^[43]
Районирование социально-географических территорий, группировка территорий в однородные, сопредельные районы. ^[44]
Сравнение данных экотоксикологии . ^[45]
Топологическая наблюдаемость в энергосистемах. ^[46]
Измерение однородности двумерных материалов. ^[47]
Минимаксное управление процессом . ^[48]
Минимальные связующие деревья также можно использовать для описания финансовых рынков. ^[49]^[50] Матрица корреляции может быть создана путем расчета коэффициента корреляции между любыми двумя акциями. Эту матрицу можно топологически представить как сложную сеть, и можно построить минимальное связующее дерево для визуализации отношений.

Ссылки

^ «scipy.sparse.csgraph.minimum_spanning_tree — Руководство по SciPy v1.7.1» . Документация Numpy и Scipy — Документация Numpy и Scipy . Проверено 10 декабря 2021 г. Минимальное остовное дерево — это граф, состоящий из подмножества ребер, которые вместе соединяют все связанные узлы, минимизируя при этом общую сумму весов на ребрах.
^ "networkx.algorithms.tree.mst.minimum_spanning_edges" . Документация NetworkX 2.6.2 . Проверено 13 декабря 2021 г. Минимальное остовное дерево — это подграф графа (дерева) с минимальной суммой весов ребер. Охватывающий лес — это объединение остовных деревьев для каждого связного компонента графа.
^ «Имеют ли минимальные остовные деревья взвешенного графа одинаковое количество ребер с заданным весом?» . cs.stackexchange.com . Проверено 4 апреля 2018 г.
^ Перейти обратно: ^а ^б ^с ^д ^и Петти, Сет; Рамачандран, Виджая (2002), «Оптимальный алгоритм минимального остовного дерева» (PDF) , Журнал Ассоциации вычислительной техники , 49 (1): 16–34, doi : 10.1145/505241.505243 , MR 2148431 , S2CID 5362916 .
^ Каргер, Дэвид Р .; Кляйн, Филип Н.; Тарьян, Роберт Э. (1995), «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев», Журнал Ассоциации вычислительной техники , 42 (2): 321–328, doi : 10.1145/201019.201022 , MR 1409738 , S2CID 832583
^ Петти, Сет; Рамачандран, Виджая (2002), «Минимизация случайности в минимальном остовном дереве, параллельной связности и алгоритмах установки максимумов», Proc. 13-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '02) , Сан-Франциско, Калифорния, стр. 713–722, ISBN 9780898715132 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .
^ Перейти обратно: ^а ^б Шазель, Бернар (2000), «Алгоритм минимального остовного дерева со сложностью обратного типа Аккермана», Журнал Ассоциации вычислительной техники , 47 (6): 1028–1047, doi : 10.1145/355541.355562 , MR 1866456 , S2CID 6276962 .
^ Шазель, Бернар (2000), «Мягкая куча: приблизительная очередь приоритетов с оптимальной частотой ошибок», Журнал Ассоциации вычислительной техники , 47 (6): 1012–1027, doi : 10.1145/355541.355554 , MR 1866455 , S2CID 12556140 .
^ Фредман, МЛ; Тарьян, Р.Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Журнал АКМ . 34 (3): 596. дои : 10.1145/28869.28874 . S2CID 7904683 .
^ Габоу, Гонконг ; Галил, З.; Спенсер, Т.; Тарьян, Р.Э. (1986). «Эффективные алгоритмы поиска минимальных остовных деревьев в неориентированных и ориентированных графах». Комбинаторика . 6 (2): 109. дои : 10.1007/bf02579168 . S2CID 35618095 .
^ Фредман, ML ; Уиллард, DE (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064-9 , МР 1279413 .
^ Чонг, Ка Вонг; Хан, Ицзе; Лам, Так Ва (2001), «Параллельные потоки и алгоритм оптимального параллельного минимального связующего дерева», Журнал Ассоциации вычислительной техники , 48 (2): 297–323, doi : 10.1145/375827.375847 , MR 1868718 , S2CID 1778676 .
^ Петти, Сет; Рамачандран, Виджая (2002), «Оптимальный параллельный алгоритм с рандомизированной работой по времени для поиска минимального остовного леса» (PDF) , SIAM Journal on Computing , 31 (6): 1879–1895, doi : 10.1137/S0097539700371065 , MR 1954882 .
^ Стил, Дж. Майкл (2002), «Минимальные остовные деревья для графов со случайной длиной ребер», Математика и информатика, II (Версаль, 2002) , Trends Math., Базель: Birkhäuser, стр. 223–245, MR 1940139
^ Перейти обратно: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419
^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . . НД12
^ Габоу, Гарольд Н. (1977), «Два алгоритма для генерации взвешенных остовных деревьев по порядку», SIAM Journal on Computing , 6 (1): 139–150, doi : 10.1137/0206011 , MR 0441784 .
^ Эппштейн, Дэвид (1992), «Нахождение k наименьших остовных деревьев», BIT , 32 (2): 237–248, doi : 10.1007/BF01994879 , MR 1172188 , S2CID 121160520 .
^ Фредериксон, Грег Н. (1997), «Амбивалентные структуры данных для динамической 2-реберной связности и k наименьших остовных деревьев» , SIAM Journal on Computing , 26 (2): 484–538, doi : 10.1137/S0097539792226825 , MR 1438526 .
^ Джоти, Раджа; Рагхавачари, Баладжи (2005), «Алгоритмы аппроксимации задачи минимального остовного дерева с емкостью и ее варианты в проектировании сетей», ACM Trans. Алгоритмы , 1 (2): 265–282, doi : 10.1145/1103963.1103967 , S2CID 8302085
^ Ху, Т.К. (1961), «Проблема маршрута с максимальной пропускной способностью», Operations Research , 9 (6): 898–900, doi : 10.1287/opre.9.6.898 , JSTOR 167055 .
^ Макдональд, Райан; Перейра, Фернандо; Рыбаров Кирилл; Гаич, Ян (2005). «Разбор непроективных зависимостей с использованием алгоритмов связующего дерева» (PDF) . Учеб. HLT/ЕМНЛП .
^ Спира, премьер-министр; Пан, А. (1975), «О поиске и обновлении связующих деревьев и кратчайших путей» (PDF) , SIAM Journal on Computing , 4 (3): 375–380, doi : 10.1137/0204032 , MR 0378466 .
^ Холм, Джейкоб; де Лихтенберг, Кристиан; Торуп, Миккель (2001), «Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального остовного дерева, 2-ребер и двусвязности», Журнал Ассоциации вычислительной техники , 48 (4): 723–760, doi : 10.1145 /502090.502095 , МР 2144928 , S2CID 7273552 .
^ Чин, Ф.; Хоук, Д. (1978), «Алгоритмы обновления минимальных остовных деревьев», Journal of Computer and System Sciences , 16 (3): 333–344, doi : 10.1016/0022-0000(78)90022-3 .
^ Чанг, РС; Леу, С.Дж. (1997), «Минимальная маркировка связующих деревьев», Information Processing Letters , 63 (5): 277–282, doi : 10.1016/s0020-0190(97)00127-0 .
^ «Все о связующем дереве узких мест» . flashing-thions.blogspot.ru . 5 июня 2010 г. Проверено 4 апреля 2018 г.
^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 июня 2013 г. Проверено 2 июля 2014 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ Грэм, РЛ ; Ад, Павол (1985), «К истории проблемы минимального остовного дерева», Annals of the History of Computing , 7 (1): 43–57, doi : 10.1109/MAHC.1985.10011 , MR 0783327 , S2CID 10555375
^ Никос Кристофидес , Анализ наихудшего случая новой эвристики для задачи коммивояжера , Отчет 388, Высшая школа промышленного управления, CMU, 1976.
^ Дальхаус, Э.; Джонсон, Д.С .; Пападимитриу, Швейцария ; Сеймур, Полиция ; Яннакакис, М. (август 1994 г.). «Сложность многоконцевых разрезов» (PDF) . SIAM Journal по вычислительной технике . 23 (4): 864–894. дои : 10.1137/S0097539792225297 . Архивировано из оригинала (PDF) 24 августа . Получено 17 декабря.
^ Суповит, Кеннет Дж.; Плейстед, Дэвид А.; Рейнгольд, Эдвард М. (1980). Эвристика для взвешенного идеального соответствия . 12-й ежегодный симпозиум ACM по теории вычислений (STOC '80). Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 398–419. дои : 10.1145/800141.804689 .
^ Снит, PHA (1 августа 1957 г.). «Применение компьютеров в таксономии» . Журнал общей микробиологии . 17 (1): 201–226. дои : 10.1099/00221287-17-1-201 . ПМИД 13475686 .
^ Асано, Т .; Бхаттачарья, Б.; Кейл, М.; Яо, Ф. (1988). Алгоритмы кластеризации на основе минимального и максимального остовных деревьев . Четвертый ежегодный симпозиум по вычислительной геометрии (SCG '88). Том. 1. С. 252–257. дои : 10.1145/73393.73419 .
^ Гауэр, Дж. К.; Росс, GJS (1969). «Минимальные остовные деревья и кластерный анализ с одной связью». Журнал Королевского статистического общества . С (Прикладная статистика). 18 (1): 54–64. дои : 10.2307/2346439 . JSTOR 2346439 .
^ Пяйвинен, Ниина (1 мая 2005 г.). «Кластеризация с минимальным остовным деревом безмасштабной структуры». Буквы для распознавания образов . 26 (7): 921–930. Бибкод : 2005PaReL..26..921P . дои : 10.1016/j.patrec.2004.09.039 .
^ Сюй, Ю.; Олман, В.; Сюй, Д. (1 апреля 2002 г.). «Кластеризация данных об экспрессии генов с использованием теоретико-графового подхода: применение минимальных остовных деревьев» . Биоинформатика . 18 (4): 536–545. дои : 10.1093/биоинформатика/18.4.536 . ПМИД 12016051 .
^ Далал, Йоген К.; Меткалф, Роберт М. (1 декабря 1978 г.). «Пересылка широковещательных пакетов по обратному пути» . Коммуникации АКМ . 21 (12): 1040–1048. дои : 10.1145/359657.359665 . S2CID 5638057 .
^ Ма, Б.; Герой, А.; Горман, Дж.; Мишель, О. (2000). Регистрация изображения с использованием алгоритма минимального связующего дерева (PDF) . Международная конференция по обработке изображений. Том. 1. С. 481–484. дои : 10.1109/ICIP.2000.901000 . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ П. Фельценшвальб, Д. Хуттенлохер: Эффективная сегментация изображений на основе графов. IJCV 59 (2) (сентябрь 2004 г.)
^ Сук, Минсу; Сон, Оён (1 июня 1984 г.). «Извлечение криволинейных признаков с использованием минимальных остовных деревьев». Компьютерное зрение, графика и обработка изображений . 26 (3): 400–411. дои : 10.1016/0734-189X(84)90221-4 .
^ Тапиа, Эрнесто; Рохас, Рауль (2004). «Распознавание рукописных математических выражений в режиме онлайн с использованием построения минимального остовного дерева и доминирования символов» (PDF) . Распознавание графики. Последние достижения и перспективы . Конспекты лекций по информатике. Том. 3088. Берлин, Гейдельберг: Springer-Verlag. стр. 329–340. ISBN 978-3540224785 . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Олссон, Х. (2004). Реализация КИХ-фильтров низкой сложности с использованием минимального связующего дерева . 12-я Средиземноморская электротехническая конференция IEEE (MELECON 2004). Том. 1. С. 261–264. дои : 10.1109/MELCON.2004.1346826 .
^ АССУНАСЬО, РМ; МК Невес; Г. Камара; К. Да Коста Фрейтас (2006). «Эффективные методы регионализации социально-экономических географических единиц с использованием деревьев минимального диапазона» . Международный журнал географической информатики . 20 (7): 797–811. Бибкод : 2006IJGIS..20..797A . дои : 10.1080/13658810600665111 . S2CID 2530748 .
^ Девиллерс, Дж.; Доре, Дж. К. (1 апреля 1989 г.). «Эвристическая эффективность метода минимального остовного дерева (MST) в токсикологии». Экотоксикология и экологическая безопасность . 17 (2): 227–235. Бибкод : 1989ЭкоЭС..17..227Д . дои : 10.1016/0147-6513(89)90042-0 . ПМИД 2737116 .
^ Мори, Х.; Цузуки, С. (1 мая 1991 г.). «Быстрый метод топологического анализа наблюдаемости с использованием метода минимального остовного дерева». Транзакции IEEE в энергосистемах . 6 (2): 491–500. Бибкод : 1991ITPSy...6..491M . дои : 10.1109/59.76691 .
^ Филлибен, Джеймс Дж.; Кафадар, Карен ; Шир, Дуглас Р. (1 января 1983 г.). «Проверка однородности двумерных поверхностей». Математическое моделирование . 4 (2): 167–189. дои : 10.1016/0270-0255(83)90026-X .
^ Калаба, Роберт Э. (1963), Теория графов и автоматическое управление (PDF) , заархивировано из оригинала (PDF) 21 февраля 2016 г.
^ Мантенья, Р.Н. (1999). Иерархическая структура на финансовых рынках . Европейский физический журнал B-Конденсированная материя и сложные системы, 11 (1), 193–197.
^ Джаухари М. и Ган С. (2015). Проблема оптимальности топологии сети в анализе фондового рынка . Физика А: статистическая механика и ее приложения, 419, 108–114.

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

Отакар Борувка о проблеме минимального остовного дерева (перевод обеих статей 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 (2009 McGraw Hill) (Использование минимального связующего дерева в качестве метода демографического анализа этнического разнообразия в Соединенных Штатах).

Внешние ссылки

[Numpy_and_Scipy_Documentation_—_Numpy_and_Scipy_documentation-1] «scipy.sparse.csgraph.minimum_spanning_tree — Руководство по SciPy v1.7.1» . Документация Numpy и Scipy — Документация Numpy и Scipy . Проверено 10 декабря 2021 г. Минимальное остовное дерево — это граф, состоящий из подмножества ребер, которые вместе соединяют все связанные узлы, минимизируя при этом общую сумму весов на ребрах.

[NetworkX_2.6.2_documentation-2] "networkx.algorithms.tree.mst.minimum_spanning_edges" . Документация NetworkX 2.6.2 . Проверено 13 декабря 2021 г. Минимальное остовное дерево — это подграф графа (дерева) с минимальной суммой весов ребер. Охватывающий лес — это объединение остовных деревьев для каждого связного компонента графа.

[3] «Имеют ли минимальные остовные деревья взвешенного графа одинаковое количество ребер с заданным весом?» . cs.stackexchange.com . Проверено 4 апреля 2018 г.

[PettieRamachandran2002-4] Перейти обратно: ^а ^б ^с ^д ^и Петти, Сет; Рамачандран, Виджая (2002), «Оптимальный алгоритм минимального остовного дерева» (PDF) , Журнал Ассоциации вычислительной техники , 49 (1): 16–34, doi : 10.1145/505241.505243 , MR 2148431 , S2CID 5362916 .

[5] Каргер, Дэвид Р .; Кляйн, Филип Н.; Тарьян, Роберт Э. (1995), «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев», Журнал Ассоциации вычислительной техники , 42 (2): 321–328, doi : 10.1145/201019.201022 , MR 1409738 , S2CID 832583

[6] Петти, Сет; Рамачандран, Виджая (2002), «Минимизация случайности в минимальном остовном дереве, параллельной связности и алгоритмах установки максимумов», Proc. 13-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA '02) , Сан-Франциско, Калифорния, стр. 713–722, ISBN 9780898715132 {{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) .

[Chazelle2000-7] Перейти обратно: ^а ^б Шазель, Бернар (2000), «Алгоритм минимального остовного дерева со сложностью обратного типа Аккермана», Журнал Ассоциации вычислительной техники , 47 (6): 1028–1047, doi : 10.1145/355541.355562 , MR 1866456 , S2CID 6276962 .

[8] Шазель, Бернар (2000), «Мягкая куча: приблизительная очередь приоритетов с оптимальной частотой ошибок», Журнал Ассоциации вычислительной техники , 47 (6): 1012–1027, doi : 10.1145/355541.355554 , MR 1866455 , S2CID 12556140 .

[9] Фредман, МЛ; Тарьян, Р.Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Журнал АКМ . 34 (3): 596. дои : 10.1145/28869.28874 . S2CID 7904683 .

[10] Габоу, Гонконг ; Галил, З.; Спенсер, Т.; Тарьян, Р.Э. (1986). «Эффективные алгоритмы поиска минимальных остовных деревьев в неориентированных и ориентированных графах». Комбинаторика . 6 (2): 109. дои : 10.1007/bf02579168 . S2CID 35618095 .

[11] Фредман, ML ; Уиллард, DE (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064-9 , МР 1279413 .

[12] Чонг, Ка Вонг; Хан, Ицзе; Лам, Так Ва (2001), «Параллельные потоки и алгоритм оптимального параллельного минимального связующего дерева», Журнал Ассоциации вычислительной техники , 48 (2): 297–323, doi : 10.1145/375827.375847 , MR 1868718 , S2CID 1778676 .

[13] Петти, Сет; Рамачандран, Виджая (2002), «Оптимальный параллельный алгоритм с рандомизированной работой по времени для поиска минимального остовного леса» (PDF) , SIAM Journal on Computing , 31 (6): 1879–1895, doi : 10.1137/S0097539700371065 , MR 1954882 .

[14] Стил, Дж. Майкл (2002), «Минимальные остовные деревья для графов со случайной длиной ребер», Математика и информатика, II (Версаль, 2002) , Trends Math., Базель: Birkhäuser, стр. 223–245, MR 1940139

[:1-15] Перейти обратно: ^а ^б Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[16] Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN 9780716710455 . МР 0519066 . OCLC 247570676 . . НД12

[17] Габоу, Гарольд Н. (1977), «Два алгоритма для генерации взвешенных остовных деревьев по порядку», SIAM Journal on Computing , 6 (1): 139–150, doi : 10.1137/0206011 , MR 0441784 .

[18] Эппштейн, Дэвид (1992), «Нахождение k наименьших остовных деревьев», BIT , 32 (2): 237–248, doi : 10.1007/BF01994879 , MR 1172188 , S2CID 121160520 .

[19] Фредериксон, Грег Н. (1997), «Амбивалентные структуры данных для динамической 2-реберной связности и k наименьших остовных деревьев» , SIAM Journal on Computing , 26 (2): 484–538, doi : 10.1137/S0097539792226825 , MR 1438526 .

[20] Джоти, Раджа; Рагхавачари, Баладжи (2005), «Алгоритмы аппроксимации задачи минимального остовного дерева с емкостью и ее варианты в проектировании сетей», ACM Trans. Алгоритмы , 1 (2): 265–282, doi : 10.1145/1103963.1103967 , S2CID 8302085

[21] Ху, Т.К. (1961), «Проблема маршрута с максимальной пропускной способностью», Operations Research , 9 (6): 898–900, doi : 10.1287/opre.9.6.898 , JSTOR 167055 .

[22] Макдональд, Райан; Перейра, Фернандо; Рыбаров Кирилл; Гаич, Ян (2005). «Разбор непроективных зависимостей с использованием алгоритмов связующего дерева» (PDF) . Учеб. HLT/ЕМНЛП .

[23] Спира, премьер-министр; Пан, А. (1975), «О поиске и обновлении связующих деревьев и кратчайших путей» (PDF) , SIAM Journal on Computing , 4 (3): 375–380, doi : 10.1137/0204032 , MR 0378466 .

[24] Холм, Джейкоб; де Лихтенберг, Кристиан; Торуп, Миккель (2001), «Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального остовного дерева, 2-ребер и двусвязности», Журнал Ассоциации вычислительной техники , 48 (4): 723–760, doi : 10.1145 /502090.502095 , МР 2144928 , S2CID 7273552 .

[25] Чин, Ф.; Хоук, Д. (1978), «Алгоритмы обновления минимальных остовных деревьев», Journal of Computer and System Sciences , 16 (3): 333–344, doi : 10.1016/0022-0000(78)90022-3 .

[26] Чанг, РС; Леу, С.Дж. (1997), «Минимальная маркировка связующих деревьев», Information Processing Letters , 63 (5): 277–282, doi : 10.1016/s0020-0190(97)00127-0 .

[27] «Все о связующем дереве узких мест» . flashing-thions.blogspot.ru . 5 июня 2010 г. Проверено 4 апреля 2018 г.

[28] «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 12 июня 2013 г. Проверено 2 июля 2014 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[29] Грэм, РЛ ; Ад, Павол (1985), «К истории проблемы минимального остовного дерева», Annals of the History of Computing , 7 (1): 43–57, doi : 10.1109/MAHC.1985.10011 , MR 0783327 , S2CID 10555375

[30] Никос Кристофидес , Анализ наихудшего случая новой эвристики для задачи коммивояжера , Отчет 388, Высшая школа промышленного управления, CMU, 1976.

[31] Дальхаус, Э.; Джонсон, Д.С .; Пападимитриу, Швейцария ; Сеймур, Полиция ; Яннакакис, М. (август 1994 г.). «Сложность многоконцевых разрезов» (PDF) . SIAM Journal по вычислительной технике . 23 (4): 864–894. дои : 10.1137/S0097539792225297 . Архивировано из оригинала (PDF) 24 августа . Получено 17 декабря.

[32] Суповит, Кеннет Дж.; Плейстед, Дэвид А.; Рейнгольд, Эдвард М. (1980). Эвристика для взвешенного идеального соответствия . 12-й ежегодный симпозиум ACM по теории вычислений (STOC '80). Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 398–419. дои : 10.1145/800141.804689 .

[33] Снит, PHA (1 августа 1957 г.). «Применение компьютеров в таксономии» . Журнал общей микробиологии . 17 (1): 201–226. дои : 10.1099/00221287-17-1-201 . ПМИД 13475686 .

[34] Асано, Т .; Бхаттачарья, Б.; Кейл, М.; Яо, Ф. (1988). Алгоритмы кластеризации на основе минимального и максимального остовных деревьев . Четвертый ежегодный симпозиум по вычислительной геометрии (SCG '88). Том. 1. С. 252–257. дои : 10.1145/73393.73419 .

[35] Гауэр, Дж. К.; Росс, GJS (1969). «Минимальные остовные деревья и кластерный анализ с одной связью». Журнал Королевского статистического общества . С (Прикладная статистика). 18 (1): 54–64. дои : 10.2307/2346439 . JSTOR 2346439 .

[36] Пяйвинен, Ниина (1 мая 2005 г.). «Кластеризация с минимальным остовным деревом безмасштабной структуры». Буквы для распознавания образов . 26 (7): 921–930. Бибкод : 2005PaReL..26..921P . дои : 10.1016/j.patrec.2004.09.039 .

[37] Сюй, Ю.; Олман, В.; Сюй, Д. (1 апреля 2002 г.). «Кластеризация данных об экспрессии генов с использованием теоретико-графового подхода: применение минимальных остовных деревьев» . Биоинформатика . 18 (4): 536–545. дои : 10.1093/биоинформатика/18.4.536 . ПМИД 12016051 .

[38] Далал, Йоген К.; Меткалф, Роберт М. (1 декабря 1978 г.). «Пересылка широковещательных пакетов по обратному пути» . Коммуникации АКМ . 21 (12): 1040–1048. дои : 10.1145/359657.359665 . S2CID 5638057 .

[39] Ма, Б.; Герой, А.; Горман, Дж.; Мишель, О. (2000). Регистрация изображения с использованием алгоритма минимального связующего дерева (PDF) . Международная конференция по обработке изображений. Том. 1. С. 481–484. дои : 10.1109/ICIP.2000.901000 . Архивировано (PDF) из оригинала 9 октября 2022 г.

[40] П. Фельценшвальб, Д. Хуттенлохер: Эффективная сегментация изображений на основе графов. IJCV 59 (2) (сентябрь 2004 г.)

[41] Сук, Минсу; Сон, Оён (1 июня 1984 г.). «Извлечение криволинейных признаков с использованием минимальных остовных деревьев». Компьютерное зрение, графика и обработка изображений . 26 (3): 400–411. дои : 10.1016/0734-189X(84)90221-4 .

[42] Тапиа, Эрнесто; Рохас, Рауль (2004). «Распознавание рукописных математических выражений в режиме онлайн с использованием построения минимального остовного дерева и доминирования символов» (PDF) . Распознавание графики. Последние достижения и перспективы . Конспекты лекций по информатике. Том. 3088. Берлин, Гейдельберг: Springer-Verlag. стр. 329–340. ISBN 978-3540224785 . Архивировано (PDF) из оригинала 9 октября 2022 г.

[43] Олссон, Х. (2004). Реализация КИХ-фильтров низкой сложности с использованием минимального связующего дерева . 12-я Средиземноморская электротехническая конференция IEEE (MELECON 2004). Том. 1. С. 261–264. дои : 10.1109/MELCON.2004.1346826 .

[44] АССУНАСЬО, РМ; МК Невес; Г. Камара; К. Да Коста Фрейтас (2006). «Эффективные методы регионализации социально-экономических географических единиц с использованием деревьев минимального диапазона» . Международный журнал географической информатики . 20 (7): 797–811. Бибкод : 2006IJGIS..20..797A . дои : 10.1080/13658810600665111 . S2CID 2530748 .

[45] Девиллерс, Дж.; Доре, Дж. К. (1 апреля 1989 г.). «Эвристическая эффективность метода минимального остовного дерева (MST) в токсикологии». Экотоксикология и экологическая безопасность . 17 (2): 227–235. Бибкод : 1989ЭкоЭС..17..227Д . дои : 10.1016/0147-6513(89)90042-0 . ПМИД 2737116 .

[46] Мори, Х.; Цузуки, С. (1 мая 1991 г.). «Быстрый метод топологического анализа наблюдаемости с использованием метода минимального остовного дерева». Транзакции IEEE в энергосистемах . 6 (2): 491–500. Бибкод : 1991ITPSy...6..491M . дои : 10.1109/59.76691 .

[47] Филлибен, Джеймс Дж.; Кафадар, Карен ; Шир, Дуглас Р. (1 января 1983 г.). «Проверка однородности двумерных поверхностей». Математическое моделирование . 4 (2): 167–189. дои : 10.1016/0270-0255(83)90026-X .

[48] Калаба, Роберт Э. (1963), Теория графов и автоматическое управление (PDF) , заархивировано из оригинала (PDF) 21 февраля 2016 г.

[49] Мантенья, Р.Н. (1999). Иерархическая структура на финансовых рынках . Европейский физический журнал B-Конденсированная материя и сложные системы, 11 (1), 193–197.

[50] Джаухари М. и Ган С. (2015). Проблема оптимальности топологии сети в анализе фондового рынка . Физика А: статистическая механика и ее приложения, 419, 108–114.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]