Минимальное остовное дерево
Дерево наименьшего веса, соединяющее вершины графа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для любого цикла 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 }, таким образом, V – S = { C , F }, то существует 3 возможности ребра через разрез ( S , V – S ) , это ребра 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 для графа до сжатия. [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 ≥ log log log n ) , то детерминированный алгоритм Фредмана и Тарьяна находит MST за время O( m ) . [9] Алгоритм выполняет ряд фаз. Каждая фаза выполняет алгоритм Прима много раз, каждая для ограниченного числа шагов. Время выполнения каждой фазы составляет O( m + n ) . Если количество вершин до фазы равно n' , количество вершин, оставшихся после фазы, не превышает . Следовательно, требуется не более log* n фаз, что дает линейное время выполнения для плотных графов. [4] н ′ 2 м / н ′ {\displaystyle {\tfrac {n'}{2^{m/n'}}}}

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

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

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

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

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

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

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

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

( г 4 ) ( 2 г 2 ) = г 2 ( г 2 + 2 ) . {\displaystyle {(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.}

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

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

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

2 ( г 2 ) ⋅ г 2 ( г 2 + 2 ) ⋅ ( г 2 + 1 ) ! , {\displaystyle 2^{r \выберите 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,}

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

2 2 г 2 + о ( г ) . {\displaystyle 2^{2^{r^{2}+o(r)}}.}

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

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

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

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

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

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

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

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

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

Для равномерных случайных весов в точный ожидаемый размер минимального остовного дерева был вычислен для небольших полных графов. [14] [ 0 , 1 ] {\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

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

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

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

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

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

Минимальные деревья Штейнера вершин правильных многоугольников с N = 3–8 сторонами. Наименьшая длина сети L для N > 5 — это длина окружности за вычетом одной стороны. Квадраты представляют точки Штейнера.
  • Дерево Штейнера подмножества вершин — это минимальное дерево, охватывающее данное подмножество. Нахождение дерева Штейнера — 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 для ориентированных графов . Она может быть решена за время с помощью алгоритма Чу–Лю/Эдмондса . О ( Э + В бревно ⁡ В ) {\displaystyle 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]

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

Ссылки

  1. ^ "scipy.sparse.csgraph.minimum_spanning_tree - Руководство SciPy v1.7.1". Документация Numpy и Scipy — Документация Numpy и Scipy . Получено 2021-12-10 . Минимальное остовное дерево — это граф, состоящий из подмножества ребер, которые вместе соединяют все соединенные узлы, при этом минимизируя общую сумму весов на ребрах.
  2. ^ "networkx.algorithms.tree.mst.minimum_spanning_edges". Документация NetworkX 2.6.2 . Получено 13.12.2021 . Минимальное остовное дерево — это подграф графа (дерева) с минимальной суммой весов ребер. Охватывающий лес — это объединение остовных деревьев для каждого связного компонента графа.
  3. ^ «Имеют ли минимальные остовные деревья взвешенного графа одинаковое количество ребер с заданным весом?». cs.stackexchange.com . Получено 4 апреля 2018 г. .
  4. ^ abcde Pettie, Seth; Ramachandran, Vijaya (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), «Минимизация случайности в алгоритмах минимального остовного дерева, параллельной связности и множества максимальных алгоритмов», Труды 13-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA '02) , Сан-Франциско, Калифорния, стр.  713–722 , ISBN 9780898715132{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ).
  7. ^ ab Chazelle, Bernard (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). «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации». Журнал ACM . 34 (3): 596. doi : 10.1145/28869.28874 . S2CID  7904683.
  10. ^ Габов, Х. Н .; Галил, З.; Спенсер, Т.; Тарьян, Р. Э. (1986). «Эффективные алгоритмы поиска минимальных остовных деревьев в неориентированных и ориентированных графах». Combinatorica . 6 (2): 109. doi :10.1007/bf02579168. S2CID  35618095.
  11. ^ Фредман, ML ; Уиллард, DE (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук , 48 (3): 533–551 , doi : 10.1016/S0022-0000(05)80064-9 , MR  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
  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. MR  0519066. OCLC  247570676.. ND12
  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. Algorithms , 1 (2): 265– 282, doi :10.1145/1103963.1103967, S2CID  8302085
  21. ^ Ху, TC (1961), «Проблема маршрута с максимальной пропускной способностью», Operations Research , 9 (6): 898–900 , doi :10.1287/opre.9.6.898, JSTOR  167055.
  22. ^ Макдональд, Райан; Перейра, Фернандо; Рибаров, Кирил; Хаджич, Ян (2005). «Непроективный анализ зависимостей с использованием алгоритмов связующего дерева» (PDF) . Proc. HLT/EMNLP .
  23. ^ Spira, PM; Pan, A. (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, MR  2144928, S2CID  7273552.
  25. ^ Чин, Ф.; Хоук, Д. (1978), «Алгоритмы обновления минимальных остовных деревьев», Журнал компьютерных и системных наук , 16 (3): 333– 344, doi :10.1016/0022-0000(78)90022-3.
  26. ^ Чанг, RS; Лей, SJ (1997), «Минимальная маркировка связующих деревьев», Information Processing Letters , 63 (5): 277– 282, doi :10.1016/s0020-0190(97)00127-0.
  27. ^ "Все о Bottleneck Spanning Tree". flashing-thoughts.blogspot.ru . 5 июня 2010 г. Получено 4 апреля 2018 г.
  28. ^ "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2013-06-12 . Получено 2014-07-02 .{{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 . doi : 10.1137/S0097539792225297. Архивировано из оригинала (PDF) 24 августа 2004 года . Проверено 17 декабря 2012 г.
  32. ^ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Эвристики для взвешенного совершенного соответствия. 12-й ежегодный симпозиум ACM по теории вычислений (STOC '80). Нью-Йорк, штат Нью-Йорк, США: ACM. стр.  398–419 . doi :10.1145/800141.804689.
  33. ^ Sneath, PHA (1 августа 1957 г.). «Применение компьютеров в таксономии». Журнал общей микробиологии . 17 (1): 201– 226. doi : 10.1099/00221287-17-1-201 . PMID  13475686.
  34. ^ Асано, Т .; Бхаттачарья, Б.; Кейл, М.; Яо, Ф. (1988). Алгоритмы кластеризации на основе минимальных и максимальных остовных деревьев . Четвертый ежегодный симпозиум по вычислительной геометрии (SCG '88). Том 1. С.  252–257 . doi :10.1145/73393.73419.
  35. ^ Gower, JC; Ross, GJS (1969). «Минимальные остовные деревья и кластерный анализ с одиночной связью». Журнал Королевского статистического общества . C (Прикладная статистика). 18 (1): 54– 64. doi :10.2307/2346439. JSTOR  2346439.
  36. ^ Päivinen, Niina (1 мая 2005 г.). «Кластеризация с минимальным остовным деревом структуры, подобной безмасштабной». Pattern Recognition Letters . 26 (7): 921– 930. Bibcode : 2005PaReL..26..921P. doi : 10.1016/j.patrec.2004.09.039.
  37. ^ Xu, Y.; Olman, V.; Xu, D. (1 апреля 2002 г.). «Кластеризация данных по экспрессии генов с использованием подхода на основе теории графов: применение минимальных остовных деревьев». Биоинформатика . 18 (4): 536–545 . doi : 10.1093/bioinformatics/18.4.536 . PMID  12016051.
  38. ^ Далал, Йоген К.; Меткалф, Роберт М. (1 декабря 1978 г.). «Пересылка широковещательных пакетов по обратному пути». Сообщения ACM . 21 (12): 1040–1048 . doi : 10.1145/359657.359665 . S2CID  5638057.
  39. ^ Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Регистрация изображений с алгоритмом минимального остовного дерева (PDF) . Международная конференция по обработке изображений. Том 1. стр.  481– 484. doi :10.1109/ICIP.2000.901000. Архивировано (PDF) из оригинала 2022-10-09.
  40. ^ П. Фельценшвальб, Д. Хуттенлохер: Эффективная сегментация изображений на основе графов. IJCV 59 (2) (сентябрь 2004 г.)
  41. ^ Сук, Минсу; Сонг, Оёнг (1 июня 1984 г.). «Извлечение криволинейных признаков с использованием минимальных остовных деревьев». Computer Vision, Graphics, and Image Processing . 26 (3): 400– 411. doi :10.1016/0734-189X(84)90221-4.
  42. ^ Тапиа, Эрнесто; Рохас, Рауль (2004). «Распознавание рукописных математических выражений в режиме онлайн с использованием конструкции минимального остовного дерева и доминирования символов» (PDF) . Распознавание графики. Последние достижения и перспективы . Конспект лекций по информатике. Том 3088. Берлин-Гейдельберг: Springer-Verlag. С.  329–340 . ISBN 978-3540224785. Архивировано (PDF) из оригинала 2022-10-09.
  43. ^ Олссон, Х. (2004). Реализация низкосложных FIR-фильтров с использованием минимального остовного дерева . 12-я Средиземноморская электротехническая конференция IEEE (MELECON 2004). Том 1. С.  261– 264. doi :10.1109/MELCON.2004.1346826.
  44. ^ Ассунсао, РМ; МК Невес; Г. Камара; К. Да Коста Фрейтас (2006). «Эффективные методы регионализации для социально-экономических географических единиц с использованием минимальных связующих деревьев». Международный журнал географической информатики . 20 (7): 797–811 . Бибкод : 2006IJGIS..20..797A. дои : 10.1080/13658810600665111. S2CID  2530748.
  45. ^ Devillers, J.; Dore, JC (1 апреля 1989 г.). «Эвристическая сила метода минимального остовного дерева (MST) в токсикологии». Экотоксикология и безопасность окружающей среды . 17 (2): 227– 235. Bibcode : 1989EcoES..17..227D. doi : 10.1016/0147-6513(89)90042-0. PMID  2737116.
  46. ^ Мори, Х.; Цузуки, С. (1 мая 1991 г.). «Быстрый метод анализа топологической наблюдаемости с использованием метода минимального остовного дерева». Труды IEEE по энергосистемам . 6 (2): 491– 500. Bibcode : 1991ITPSy...6..491M. doi : 10.1109/59.76691.
  47. ^ Филлибен, Джеймс Дж.; Кафадар, Карен ; Шиер, Дуглас Р. (1 января 1983 г.). «Проверка однородности двумерных поверхностей». Математическое моделирование . 4 (2): 167– 189. doi :10.1016/0270-0255(83)90026-X.
  48. ^ Калаба, Роберт Э. (1963), Теория графов и автоматическое управление (PDF) , архивировано из оригинала (PDF) 21 февраля 2016 г.
  49. ^ Мантенья, Р. Н. (1999). Иерархическая структура на финансовых рынках. Европейский физический журнал B-Condensed Matter and Complex Systems, 11(1), 193–197.
  50. ^ Джаухари, М. и Ган, С. (2015). Задача оптимальности сетевой топологии в анализе рынка акций. Physica A: Статистическая механика и ее приложения, 419, 108–114.

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

  • Отакар Борувка о проблеме минимального остовного дерева (перевод обеих статей 1926 года, комментарии, история) (2000) Ярослав Нешетржил , Ева Милкова, Хелена Несетрилова. (В разделе 7 представлен его алгоритм, который выглядит как нечто среднее между алгоритмами Прима и Краскала.)
  • Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Глава 23: Минимальные остовные деревья, стр. 561–579. 
  • Эйснер, Джейсон (1997). Современные алгоритмы для минимальных остовных деревьев: Учебное обсуждение. Рукопись, Университет Пенсильвании, апрель. 78 стр.
  • Кромковски, Джон Дэвид. «Все еще не расплавленный после всех этих лет», в ежегодных выпусках, Расовые и этнические отношения, 17/e (2009 McGraw Hill) (Использование минимального остовного дерева как метода демографического анализа этнического разнообразия в Соединенных Штатах).
На Викискладе есть медиафайлы по теме « Минимальные остовные деревья» .
  • Реализовано в BGL, библиотеке Boost Graph
  • Репозиторий алгоритмов Стоуни-Брук - Минимальные коды остовного дерева
  • Реализовано в QuickGraph для .Net
Получено с "https://en.wikipedia.org/w/index.php?title=Minimum_spanning_tree&oldid=1262803997"