Введение

Кратчайшая сеть, соединяющая точки

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

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

Когда два ребра евклидова минимального остовного дерева сходятся в вершине, они должны образовывать угол 60° или больше, причем равенство достигается только тогда, когда они являются двумя сторонами равностороннего треугольника. Это происходит потому, что для двух ребер, образующих более острый угол, одно из этих ребер можно заменить на третье, более короткое ребро треугольника, который они образуют, получив дерево с меньшей общей длиной. В отличие от этого, задача о дереве Штейнера имеет более строгий угловой критерий: оптимальное дерево Штейнера имеет все углы не менее 120°. Тот же угловой критерий в 60° также встречается в задаче о числе поцелуев, которая заключается в нахождении максимального количества единичных сфер в евклидовом пространстве, которые могут касаться центральной единичной сферы, не пересекаясь (за исключением точки касания). Центры этих сфер образуют минимальное остовное дерево в форме звезды, где центральная точка соединена со всеми остальными точками. И наоборот, для любой вершины любого минимального остовного дерева можно построить непересекающиеся единичные сферы, центры которых находятся в самой вершине и в точках, расположенных на расстоянии двух единиц вдоль каждого из ее ребер, причем каждая сфера касается соседних вершин. Следовательно, в n-мерном пространстве максимальная возможная степень вершины (количество ребер остовного дерева, соединенных с ней) равна числу поцелуев сфер в n измерениях. Плоские минимальные остовные деревья имеют степень не более шести, и если степень дерева равна шести, то всегда существует другое минимальное остовное дерево с максимальной степенью пять. Трехмерные минимальные остовные деревья имеют степень не более двенадцати. Точные значения числа поцелуев известны только для четырех, восьми и двадцати четырех измерений. Для точек, случайно сгенерированных из заданного непрерывного распределения, минимальное остовное дерево почти наверняка единственно. Количество вершин заданной степени, при большом числе вершин, сходится к константе, умноженной на это число вершин. Значения этих констант зависят от степени и распределения. Однако даже в простых случаях, таких как количество листьев для точек, равномерно распределенных в единичном квадрате, их точные значения неизвестны.

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

Для любого ребра любого евклидова минимального остовного дерева линза (или везика писцис), образованная пересечением двух окружностей с радиусами, равными длине этого ребра, не может содержать внутри себя никакую другую заданную вершину. Иными словами, если в каком-либо дереве есть ребро, линза которого содержит третью точку , то это дерево не является минимальным по длине. Действительно, из геометрии двух окружностей следует, что точка будет ближе к обеим точкам и , чем они друг к другу. Если ребро удалить из дерева, точка останется соединенной с одной из точек и , но не с другой. Замена удаленного ребра на или (в зависимости от того, какое из этих двух ребер восстановит соединение точки с вершиной, от которой она была отключена) приведет к образованию более короткого дерева. Для любого ребра любого евклидова минимального остовного дерева ромб с углами 60° и 120°, имеющий в качестве длинной диагонали, не пересекается с ромбами, образованными аналогичным образом для всех остальных ребер. Два ребра, имеющие общую конечную точку, не могут иметь перекрывающиеся ромбы, поскольку это означало бы, что угол одного из ребер меньше 60°; а два непересекающихся ребра не могут иметь перекрывающиеся ромбы – если бы они пересекались, то более длинное из двух ребер можно было бы заменить более коротким ребром, соединяющим те же четыре вершины.

Суперграфики

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

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

Общая длина

Для точек в единичном квадрате (или любой другой фиксированной форме) общая длина ребер минимального остовного дерева равна. Некоторые наборы точек, такие как точки, равномерно расположенные в сетке, достигают этой границы. Для точек в единичном гиперкубе в -мерном пространстве соответствующая граница равна. Та же граница применяется к ожидаемой общей длине минимального остовного дерева для точек, выбранных равномерно и независимо из единичного квадрата или единичного гиперкуба. Вернемся к единичному квадрату: сумма квадратов длин ребер минимального остовного дерева равна. Эта граница следует из наблюдения, что ребра образуют непересекающиеся ромбы, площадь которых пропорциональна квадрату длин ребер. Ограничение на общую длину следует из применения неравенства Коши — Буняковского — Шварца. Другая интерпретация этих результатов заключается в том, что средняя длина ребра для любого набора точек в единичном квадрате не превышает значения, пропорционального расстоянию между точками в регулярной сетке; и что для случайных точек в единичном квадрате средняя длина пропорциональна. Однако в случайном случае с высокой вероятностью самая длинная грань имеет длину примерно на множитель больше средней, причем этот множитель не является константой. С высокой вероятностью самый длинный край образует лист остовного дерева и соединяет точку, удаленную от всех остальных точек, с ближайшим соседом. Для большого числа точек распределение длины самого длинного ребра вокруг его ожидаемого значения сходится к распределению Лапласа. Любой геометрический спаннер, подграф полного геометрического графа, кратчайшие пути в котором аппроксимируют евклидово расстояние, должен иметь общую длину ребер не меньше, чем минимальное остовное дерево, и одним из стандартных показателей качества геометрического спаннера является отношение его общей длины к общей длине минимального остовного дерева для тех же точек. Несколько методов построения спаннеров, таких как жадный геометрический спаннер, достигают постоянной границы для этого отношения. Предполагается, что отношение Штейнера, наибольшее возможное отношение между общей длиной минимального остовного дерева и дерева Штейнера для одного и того же набора точек на плоскости, равно , что соответствует отношению для трех точек в равностороннем треугольнике.

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

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

Комплексность вычислений

Для точек в любом измерении минимальное остовное дерево может быть построено за время O(n²) путем построения полного графа с ребром между каждой парой точек, взвешенным евклидовым расстоянием, а затем применения алгоритма поиска минимального остовного дерева, такого как алгоритм Прима — Дейкстры — Ярника или алгоритм Борувки. Эти алгоритмы могут быть реализованы за время O(n²) на полных графах, в отличие от другого распространенного варианта, алгоритма Крускала, который работает медленнее из-за необходимости сортировки всех расстояний. Для точек в пространствах с небольшим числом измерений задача может быть решена быстрее, как описано ниже. Вычисление евклидовых расстояний включает операцию извлечения квадратного корня. При сравнении весов ребер сравнение квадратов евклидовых расстояний вместо самих расстояний дает тот же результат и не влияет на дальнейшие вычисления дерева. Этот прием ускоряет вычисления и позволяет построить минимальное остовное дерево для точек с целочисленными координатами, используя только целочисленную арифметику.

Более высокие размеры

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

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

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

Приложения

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

Реализация

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