Евклидово минимальное остовное дерево -Euclidean minimum spanning tree

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

Ребра минимального остовного дерева сходятся под углами не менее 60°, не более шести к вершине. В более высоких измерениях количество ребер на вершину ограничено числом касательных единичных сфер . Общая длина ребер для точек в единичном квадрате не более чем пропорциональна квадратному корню из числа точек. Каждое ребро лежит в пустой области плоскости, и эти области можно использовать для доказательства того, что евклидово минимальное остовное дерево является подграфом других геометрических графов , включая граф относительных соседей и триангуляцию Делоне . Построив триангуляцию Делоне, а затем применив алгоритм минимального остовного дерева графа, минимальное остовное дерево заданных плоских точек может быть найдено за время , выраженное в нотации большого O. Это оптимально в некоторых моделях вычислений, хотя для точек с целочисленными координатами существуют более быстрые рандомизированные алгоритмы . Для точек более высоких размерностей поиск оптимального алгоритма остается открытой проблемой . ${\ Displaystyle п}$${\ Displaystyle О (п \ журнал п)}$

Определение и связанные с ним проблемы

Евклидово минимальное остовное дерево для множества точек на евклидовой плоскости или в евклидовом пространстве — это система отрезков , конечными точками которых являются только заданные точки, объединение которых включает все точки связного множества и которое имеет минимально возможная общая длина любой такой системы. Такая сеть не может содержать многоугольное кольцо сегментов; если бы он существовал, сеть можно было бы сократить, удалив край многоугольника. Таким образом, сеть минимальной длины образует дерево . Это наблюдение приводит к эквивалентному определению, согласно которому евклидово минимальное остовное дерево представляет собой дерево отрезков прямой между парами заданных точек минимальной общей длины. То же дерево можно также описать как минимальное остовное дерево взвешенного полного графа , имеющего заданные точки в качестве вершин и расстояния между точками в качестве весов ребер. Одни и те же точки могут иметь более одного минимального остовного дерева. Например, для вершин правильного многоугольника удаление любого ребра многоугольника дает минимальное остовное дерево. ${\ Displaystyle п}$

Публикации по евклидову минимальному остовному дереву обычно сокращают его до «EMST». ^{Их также можно назвать «геометрическими минимальными остовными деревьями», но этот термин может использоваться в более общем смысле для геометрических пространств с} неевклидовыми расстояниями, таких как пространства Lp . Когда контекст евклидовых наборов точек ясен, их можно назвать просто «минимальными остовными деревьями».

Несколько других стандартных геометрических сетей тесно связаны с евклидовым минимальным остовным деревом:

• Задача дерева Штейнера снова ищет систему отрезков, соединяющих все заданные точки, но не требует, чтобы отрезки начинались и заканчивались только в заданных точках. В этой задаче в качестве конечных точек сегмента могут быть добавлены дополнительные точки, что позволяет дереву Штейнера быть короче, чем минимальное остовное дерево.
• В задаче о пути евклидова коммивояжера соединительные отрезки должны начинаться и заканчиваться в заданных точках, как в остовном дереве, в отличие от дерева Штейнера; кроме того, каждая точка может касаться не более двух отрезков прямой, поэтому результат образует многоугольную цепочку . Из-за этого ограничения оптимальный путь может быть длиннее минимального евклидова остовного дерева, но не более чем в два раза длиннее.
• Геометрические гаечные ключи — это сети с малым весом, которые, подобно минимальному остовному дереву, соединяют все точки. В отличие от минимального остовного дерева, все эти соединительные пути должны быть короткими и иметь длину, пропорциональную расстоянию между точками, которые они соединяют. Чтобы достичь этого свойства, эти сети обычно имеют циклы и поэтому не являются деревьями.

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

Углы и градусы вершин

Всякий раз, когда два ребра евклидова минимального остовного дерева встречаются в вершине, они должны образовывать угол 60 ° или более, с равенством только тогда, когда они образуют две стороны равностороннего треугольника . Это связано с тем, что для двух ребер, образующих любой более острый угол, одно из двух ребер может быть заменено третьим, более коротким ребром треугольника, который они образуют, образуя дерево с меньшей общей длиной. Для сравнения, проблема дерева Штейнера имеет более сильную границу угла: оптимальное дерево Штейнера имеет все углы не менее 120 °.

Та же граница угла в 60 ° также встречается в задаче о числе поцелуев , когда нужно найти максимальное количество единичных сфер в евклидовом пространстве, которые могут касаться центральной единичной сферы без пересечения каких-либо двух сфер (за пределами точки касания). Центральные точки этих сфер имеют минимальное остовное дерево в виде звезды с центральной точкой, смежной со всеми остальными точками. И наоборот, для любой вершины любого минимального остовного дерева можно построить непересекающиеся единичные сферы с центром и в точках, на две единицы вдоль каждого из его ребер, с касанием для каждого соседа . Следовательно, в -мерном пространстве максимально возможная степень вершины (число связанных с ней ребер остовного дерева) равна целочисленному числу сфер в измерениях. Планарные минимальные остовные деревья имеют степень не более шести, а когда дерево имеет степень шесть, всегда существует другое минимальное остовное дерево с максимальной степенью пять. Трехмерные минимальные остовные деревья имеют степень не более двенадцати. Единственными высшими измерениями, в которых известно точное значение числа поцелуев, являются четыре, восемь и 24 измерения. ${\ Displaystyle v}$${\ Displaystyle v}$${\ Displaystyle v}$${\ Displaystyle п}$${\ Displaystyle п}$

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

Пустые регионы

Для любого ребра любого евклидова минимального остовного дерева линза (или vesica piscis ), образованная пересечением двух окружностей с радиусами, не может иметь внутри себя никакой другой заданной вершины. Иными словами, если у любого дерева есть ребро , линза которого содержит третью точку , то оно не имеет минимальной длины. Ибо по геометрии два круга были бы ближе к обоим и чем они друг к другу. Если бы ребро было удалено из дерева, оно осталось бы связанным с одним из и , но не с другим. Замена удаленного ребра на или (в зависимости от того, какое из этих двух ребер снова соединяется с вершиной, от которой оно было отсоединено) приведет к более короткому дереву. ${\ Displaystyle уф}$${\ Displaystyle уф}$${\ Displaystyle ш}$${\ Displaystyle уф}$${\ Displaystyle ш}$${\ Displaystyle ш}$${\ Displaystyle ты}$${\ Displaystyle v}$${\ Displaystyle уф}$${\ Displaystyle ш}$${\ Displaystyle ты}$${\ Displaystyle v}$${\ Displaystyle уф}$${\ Displaystyle нч}$${\ Displaystyle vw}$${\ Displaystyle ш}$

Для любого ребра любого евклидова минимального остовного дерева ромб с углами 60° и 120°, имеющий своей длинной диагональю, не пересекается с ромбами, образованными аналогично всеми остальными ребрами. У двух ребер, имеющих общую конечную точку, не может быть перекрывающихся ромбов, потому что это означало бы, что угол ребра острее 60 °, а у двух непересекающихся ребер не может быть перекрывающихся ромбов; если бы они это сделали, более длинное из двух ребер могло бы быть заменено более коротким ребром среди тех же четырех вершин. ${\ Displaystyle уф}$${\ Displaystyle уф}$

Суперграфы

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

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

Поскольку критерии пустой области для этих графов становятся все слабее, эти графы образуют упорядоченную последовательность подграфов. То есть, используя «⊆» для обозначения отношения подмножества между их ребрами, эти графы имеют отношения:

Другим графом, который гарантированно содержит минимальное остовное дерево, является граф Яо , определяемый для точек на плоскости путем деления плоскости вокруг каждой точки на шесть клиньев по 60° и соединения каждой точки с ближайшим соседом в каждом клине. Полученный граф содержит граф относительных соседей, поскольку две вершины с пустой линзой должны быть ближайшими соседями друг к другу в своих клиньях. Как и в случае многих других геометрических графов, приведенных выше, это определение можно обобщить на более высокие измерения, и (в отличие от триангуляции Делоне) его обобщения всегда включают линейное число ребер.

Общая длина

Для точек в единичном квадрате (или любой другой фиксированной форме) общая длина минимальных ребер остовного дерева равна . Некоторые наборы точек, например точки, равномерно расположенные в сетке, достигают этой границы. Для точек единичного гиперкуба в -мерном пространстве соответствующая граница есть . Та же оценка применяется к ожидаемой общей длине минимального остовного дерева для точек, выбранных равномерно и независимо от единичного квадрата или единичного гиперкуба. Возвращаясь к единичному квадрату, сумма квадратов длин ребер минимального остовного дерева равна . Эта оценка следует из наблюдения, что ребра имеют непересекающиеся ромбы с площадью, пропорциональной квадрату длины ребра. Оценка общей длины получается путем применения неравенства Коши – Шварца . ${\ Displaystyle п}$${\ Displaystyle О ({\ sqrt {п}})}$${\ displaystyle {\ sqrt {n}} \ times {\ sqrt {n}}}$${\ Displaystyle д}$${\ Displaystyle О (п ^ {(д-1) / д})}$${\ Displaystyle п}$${\ Displaystyle О (1)}$${\ Displaystyle О ({\ sqrt {п}})}$

Другая интерпретация этих результатов заключается в том, что средняя длина ребра для любого набора точек в единичном квадрате не более чем пропорциональна расстоянию между точками в регулярной сетке; и что для случайных точек в единичном квадрате средняя длина пропорциональна . Однако в случайном случае с большой вероятностью самое длинное ребро имеет длину примерно${\ Displaystyle О (1 / {\ sqrt {п}})}$${\ Displaystyle 1/{\ sqrt {п}}}$

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

Любой геометрический гаечный ключ , подграф полного геометрического графа, кратчайшие пути которого приближаются к евклидову расстоянию, должен иметь общую длину ребра, по крайней мере, такую ​​же большую, как минимальное остовное дерево, и одним из стандартных показателей качества для геометрического гаечного ключа является отношение между его общей длины и минимального остовного дерева для тех же точек. Некоторые методы построения гаечных ключей, такие как жадный геометрический гаечный ключ , обеспечивают постоянную оценку этого отношения. Было высказано предположение, что отношение Штейнера , максимально возможное отношение между общей длиной минимального остовного дерева и дерева Штейнера для одного и того же набора точек на плоскости, равно отношению для трех точек в равностороннем треугольнике . ${\ displaystyle 2 / {\ sqrt {3}} \ приблизительно 1,1547}$

подразделение

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

Вычислительная сложность

Для точек в любом измерении минимальное остовное дерево может быть построено за время путем построения полного графа с ребром между каждой парой точек, взвешенного по евклидову расстоянию , а затем применения алгоритма минимального остовного дерева графа, такого как алгоритм Прима-Дейкстры- Алгоритм Ярника или алгоритм Борувки на нем. Эти алгоритмы можно сделать так, чтобы они занимали время на полных графах, в отличие от другого распространенного варианта, алгоритма Крускала , который медленнее, поскольку включает сортировку всех расстояний. Для точек в низкоразмерных пространствах проблема может быть решена быстрее, как подробно описано ниже. ${\ Displaystyle О (п ^ {2})}$${\ Displaystyle О (п ^ {2})}$

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

Два измерения

Более быстрый подход к поиску минимального остовного дерева плоских точек использует то свойство, что это подграф триангуляции Делоне:

1. Вычислите триангуляцию Делоне, которую можно сделать за время. Поскольку триангуляция Делоне является планарным графом , она имеет не более ребер.${\ Displaystyle О (п \ журнал п)}$${\ Displaystyle 3n-6}$
2. Пометьте каждое ребро его (в квадрате) длиной.
3. Запустите алгоритм минимального остовного дерева графа. Поскольку есть ребра, это требует времени с использованием любого из стандартных алгоритмов минимального остовного дерева.${\ Displaystyle О (п)}$${\ Displaystyle О (п \ журнал п)}$

В результате получается требующий времени алгоритм, оптимальный в определенных моделях вычислений (см. ниже ). ${\ Displaystyle О (п \ журнал п)}$

Если входные координаты являются целыми числами и могут использоваться в качестве индексов массива , возможны более быстрые алгоритмы: триангуляция Делоне может быть построена рандомизированным алгоритмом за ожидаемое время. Кроме того, поскольку триангуляция Делоне представляет собой планарный граф , его минимальное остовное дерево может быть найдено за линейное время с помощью варианта алгоритма Борувки, который удаляет все ребра между каждой парой компонентов, кроме самого дешевого, после каждого этапа алгоритма. Следовательно, общее ожидаемое время для этого алгоритма равно . В другом направлении триангуляция Делоне может быть построена из минимального остовного дерева за почти линейную временную границу , где обозначает повторный логарифм . ${\ Displaystyle О (п \ журнал \ журнал п)}$${\ Displaystyle О (п \ журнал \ журнал п)}$${\ Displaystyle О (п \ журнал ^ {*} п)}$${\ Displaystyle \ журнал ^ {*}}$

Высшие измерения

Задача также может быть обобщена на точки в -мерном пространстве . В более высоких измерениях связность, определяемая триангуляцией Делоне (которая также разбивает выпуклую оболочку на -мерные симплексы ), содержит минимальное остовное дерево; однако триангуляция может содержать полный граф. Следовательно, нахождение евклидова минимального остовного дерева как остовного дерева полного графа или остовного дерева триангуляции Делоне требует времени. Для трех измерений минимальное остовное дерево можно найти за время , а в любом большем измерении — за время .${\ Displaystyle п}$${\ Displaystyle д}$${\ Displaystyle \ mathbb {R} ^ {d}}$${\ Displaystyle д}$${\ Displaystyle О (дн ^ {2})}$${\ Displaystyle О {\ bigl (} (п \ журнал п) ^ {4/3} {\ bigr)}}$

для любого — быстрее, чем квадратичная граница времени для алгоритмов полного графа и триангуляции Делоне. ${\ Displaystyle \ varepsilon > 0}$

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

Для равномерно случайных наборов точек в любом ограниченном измерении граф Яо или триангуляция Делоне имеют линейное ожидаемое количество ребер, гарантированно содержат минимальное остовное дерево и могут быть построены за линейное ожидаемое время. Из этих графов само минимальное остовное дерево может быть построено за линейное время с использованием рандомизированного алгоритма линейного времени для графа минимальных остовных деревьев . Однако низкая производительность этих методов на входных данных, поступающих из кластеризованных данных, побудила исследователей алгоритмов разработать методы с несколько более медленными временными рамками для случайных входных данных или входных данных, расстояния и кластеризация которых напоминают случайные данные, демонстрируя при этом лучшую производительность на реальных данных. -мировые данные. ${\ Displaystyle О (п \ журнал п)}$

Хорошо разделенная парная декомпозиция — это семейство пар подмножеств заданных точек, так что каждая пара точек принадлежит одной из этих пар подмножеств, и все пары точек, происходящие из одной и той же пары подмножеств, имеют приблизительно одинаковая длина. За время можно найти хорошо разделенную парную декомпозицию с линейным числом подмножеств и репрезентативной парой точек для каждого подмножества . Тогда минимальное остовное дерево графа, образованного этими репрезентативными парами, является приближением к минимальному остовному дереву. Используя эти идеи, можно найти -аппроксимацию минимального остовного дерева во времени для постоянного . Точнее, выбирая каждую репрезентативную пару для аппроксимации ближайшей пары в своем классе эквивалентности и тщательно варьируя качество этой аппроксимации для разных пар, зависимость от во времени может быть задана как для любого фиксированного измерения. ${\ Displaystyle О (п \ журнал п)}$${\ Displaystyle (1+ \ varepsilon)}$${\ Displaystyle О (п \ журнал п)}$${\ Displaystyle \ varepsilon}$${\ Displaystyle \ varepsilon}$${\ displaystyle O (n \ log n + (\ varepsilon ^ {- 2} \ log ^ {2} {\ tfrac {1} {\ varepsilon}}) n),}$

Динамический и кинетический

Евклидово минимальное остовное дерево по-разному обобщалось на системы перемещения или изменения точек:

• Если набор точек подвергается последовательности динамических вставок или удалений точек, каждое из этих обновлений вызывает ограниченное количество изменений в минимальном остовном дереве точек. Когда последовательность обновления известна заранее, для точек на плоскости изменение после каждой вставки или удаления может быть найдено во времени для каждой вставки или удаления. Когда обновления должны обрабатываться в режиме онлайн , известен более медленный (но все же полилогарифмический) предел времени. Для многомерных версий задачи время на обновление медленнее, но все же сублинейно.${\ Displaystyle О (\ журнал ^ {2} п)}$${\ Displaystyle О (\ журнал ^ {10} п)}$
• Для точек, движущихся линейно с постоянной скоростью или с более общими алгебраическими движениями, минимальное остовное дерево будет меняться последовательностью перестановок, в которой одно ребро удаляется, а другое заменяет его в момент времени, когда оба имеют одинаковую длину. Для линейных движений число изменений самое большее немного больше, чем . Для более общих алгебраических движений существует почти кубическая верхняя граница количества перестановок, основанная на теории последовательностей Давенпорта-Шинзеля .${\ Displaystyle п}$${\ Displaystyle п ^ {25/9}}$
• Задача о минимальном движущемся остовном дереве снова касается точек, движущихся линейно с постоянной скоростью в течение интервала времени, и ищет единственное дерево, которое минимизирует максимальную сумму весов, возникающую в любой момент в течение этого интервала. Это NP-сложно вычислить точно, но его можно аппроксимировать с точностью до двух раз за полиномиальное время.
• Кинетическая проблема евклидова минимального остовного дерева требует кинетической структуры данных , которая может поддерживать минимальное остовное дерево, поскольку его точки подвергаются как непрерывным движениям, так и вставкам и удалениям. В нескольких статьях изучались такие структуры, и известна кинетическая структура для алгебраически движущихся точек с почти кубическим полным временем, почти совпадающая с ограничением на количество обменов.

Нижняя граница

Асимптотическая нижняя граница евклидовой задачи о минимальном остовном дереве может быть установлена ​​в ограниченных моделях вычислений. К ним относятся модели алгебраического дерева решений и дерева алгебраических вычислений , в которых алгоритм имеет доступ к входным точкам только через определенные ограниченные примитивы, которые выполняют простые алгебраические вычисления со своими координатами. В этих моделях задача о ближайшей паре точек требует времени, но ближайшая пара обязательно является ребром минимального остовного дерева, поэтому минимальное остовное дерево также требует столько же времени. Поэтому оптимальными являются алгоритмы построения планарного минимального остовного дерева во времени в рамках данной модели, например с помощью триангуляции Делоне. Однако эти нижние границы не применяются к моделям вычислений с целочисленными координатами точек, в которых разрешены побитовые операции и операции индексации таблиц с этими координатами. В этих моделях возможны более быстрые алгоритмы, как описано выше. ${\ Displaystyle \ Омега (п \ журнал п)}$${\ Displaystyle \ Омега (п \ журнал п)}$${\ Displaystyle О (п \ журнал п)}$

Приложения

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

Минимальные связующие деревья тесно связаны с кластеризацией с одной связью , одним из нескольких методов иерархической кластеризации . Ребра минимального остовного дерева, отсортированные по их длине, задают порядок, в котором кластеры объединяются в более крупные кластеры в этом методе кластеризации. Как только эти ребра найдены любым алгоритмом, их можно использовать для построения кластеризации с одной связью во времени . Хотя длинные тонкие формы кластеров, создаваемые кластеризацией с одной связью, могут плохо подходить для определенных типов данных, таких как смеси распределений Гаусса , это может быть хорошим выбором в приложениях, где ожидается, что сами кластеры будут иметь длинные тонкие формы. например, при моделировании ореолов темной материи галактик . В геоинформатике несколько групп исследователей использовали минимальные остовные деревья центроидов зданий для выявления значимых кластеров зданий, например, путем удаления ребер, идентифицированных каким-либо другим способом как несогласованные. ${\ Displaystyle О (п \ журнал п)}$

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

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

Реализация

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

Смотрите также

• Прямолинейное минимальное остовное дерево , минимальное остовное дерево с расстояниями, измеренными с использованием геометрии такси.

использованная литература

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

• Учебное пособие по EMST , документация по млпаку