Еуклидово минимално разапињуће стабло

ЕМСТ за 25 насумичних тачака у равни

Еуклидово минимално разапињуће стабло (Еуцлидеан минимум спаннинг трее - ЕМСТ) је минимално разапињуће стабло скупа од н тачака у равни (или уопштеније у ℝ^д), где је тежина ивице између сваког пара тачака раздаљина између те две тачке. У једноставнијим условима, ЕМСТ повезује скуп тачака користећи линије такве да је тотална дужина свих линија минимизована и до било које тачке се може доћи из било које друге пратећи линије.

У равни, ЕМСТ за задати скуп тачака се може наћи у О(н*лог(н)) времену користећи О(н) простора у моделу рачунања алгебарског стабла одлуке. Бржи насумични алгоритми сложености О(н лог лог н) су познати у моћнијим моделима рачунања који прецизније моделирају способности правих рачунара.

У већим димензијама (д ≥ 3), проналазак оптималног алгоритма остаје отворен проблем.

Доња граница

Асимтотска доња граница од Ω(н лог н) за временску сложеност ЕМСТ проблема може бити утврђена у ограниченим моделима рачунања, какви су алгебарско дрво одлуке и алгебарско дрво за рачунање, у којима алгоритам има приступ улазним тачкама само кроз одређене ограничене примитиве које изводе једноставно алгебарско рачунање на њиховим координатама: у овим моделима, проблем најближег пара тачака захтева Ω(н лог н) време, али најближи пар је обавезно ивица ЕМСТ-а, тако да ЕМСТ захтева такође толико времена. Како год, ако улазне тачке имају целобројне координате и битске операције и операцијама табеларног индексирања је дозвољено коришћење тих координата, могући су и бржи алгоритми.

Алгоритми за рачунање ЕМСТ у две димензије

Најједноставнији алгоритам за проналажење ЕМСТ у две димензије, за задатих н тачака, је заправо конструкција комплетног графа од н врхова, који има н(н-1)/2 грана, рачуна се тежина сваке ивице налазењем растојања између сваког пара тачака, и онда се примењује стандардни алгоритам минималног разапињућег стабла (какав је Примов алгоритам или Крускалов алгоритам) на њега. Пошто овај граф има Θ(н²) грана за н различитих тачака, конструкција већ захтева време Ω(н²). Ово решење такође захтева Ω(н²) простора да сачува све ивице.

Бољи приступ налажењу ЕМСТ-а у простору ћемо добити ако приметимо да је то подстабло сваке Делаунаy-еве триангулације од н тачака, са много више редукованим скупом грана:

1. Израчунавање Делаунаy-еве триангулације у О(н лог н) времену и О(н) простору. Зато што је Делаунаy-ева триангулација планарни граф и не постоји више од три пута колико има врхова или грана у било ком планарном графу, ово генерише само О(н) грана.

2. Обележавање сваке гране својом дужином.

3. Покретање алгоритма минималног разапињућег стабла графа на овом графу да би се нашло минимално разапињуће стабло. Пошто постоји О(н) грана, ово захтева О(н лог н лог н) време користећи било који од стандардних алгоритама минималног разапињућег стабла какви су Борůвка, Прим-ов или Крускал-ов алгоритам.

Коначан резултат је алгоритам који узима О(н лог н) времена и О(н) простора.

Ако су унете координате целобројне а могу бити коришћене као индекси низова, могући су и бржи алгоритми: Делаунаy-ева триангулација може бити конструисана насумичним алгоритмом у очекиваном О(н лог лог н) времену. Додатно, пошто је Делаунаy-ева триангулација планарни граф, његово минимално разапињће стабло може бити нађено у линеарном времену варијантом Борůвка алгоритма који уклања све осим најјефтиније гране између сваког пара компоненти после сваке фазе алгоритма. Стога је укупно очекивано време за овај алгоритам О(н лог лог н).

Више димензије

Проблем може бити и уопштен до н тачака д-димензионог простора ℝ^д. У вишим димензијама повезаност одређена Делаунаy-евом триангулацијом (која, такође, партиционише конвексан труп у д-димензионе једноставности) минималног разапињућег стабла; како год, триангулација можда садржи комплетан граф. Тако, налазећи ЕМСТ као разапињуће стабло комплетног графа или разапињуће стабло Делаунаy-еве триангулације захтева О(дн²) време. За три димензије могуће је пронаћи минимално разапињуће стабло у времену О((н лог н)^4/3), и у било којој димензији већој од три могуће је решити у времену које је брже од квадратне временске границе за комплетне графове и алгоритме Делаунаy-еве триангулације. За равномерно насумичне скупове тачака могуће је израчунати минимално разапињуће дрво толико брзо као код сортирања.

Подстабло Делаунаy-еве триангулације

Све ивице ЕМСТ-а су ивице релативног суседства графа, оне су и ивице Габриел-овог графа, и ивице у Делаунаy-евој триангулацији тачака, што може бити доказано преко еквивалентне контрапозитивне изјаве: свака грана која није у Делаунаy-евој триангулацији, такође није ни у једном ЕМСТ. Доказ је заснован на два својства минималних разапињућих стабала и Делаунаy-еве триангулације:

1. (кружно својство минималних разапињућих стабала - МРС): За сваки цикл C у графу, ако је тежина гране е од C већа од тежине друге две гране у C, онда ова грана не може припадати МРС.

2. (својство Делаунаy-их триангулација): Ако постоји кружница са две улазне тачке на својој граници која садржи друге улазне тачке, линија између те две тачке је грана Делаунаy-еве триангулације.

Размотримо грану е између две улазне тачке п и q која није грана Делаунаy-еве триангулације. Из својства 2 следи да кружница C са е као својим пречником мора да садржи неку другу тачку р унутар себе. Али онда је р близе и тачки п и тачки q него што су оне једна другој, и тако је грана од п до q најдужа грана у циклу између тачака п → q → р → п, и по својству 1 е није ни у једном ЕМСТ.

Очекивана величина

Очекивана величина ЕМСТ-а за велике бројеве тачака је одређена од стране Ј. Мицхаел Стееле. Ако је $f$ густина вероватноће функције одабира тачака, онда за велико $n$ и $d\neq 1$ величина ЕМСТ-а је приближно

$c(d)n^{\frac {d-1}{d}}\int _{\mathbb {R} ^{d}}f(x)^{\frac {d-1}{d}}dx$

где је $c(d)$ константа која зависи само од димензије $d$. Тачне вредности константи су непознате али могу бити процењене из емпиријских доказа.

Апликације

Очигледан захтев ЕМСТ-а је да пронађе најјефтинију мрежу жица или цеви које повезују низ места, претпостављајући да су цене веза по јединици дужине фиксне. Како год, док ове дају апсолутну доњу границу на износ потребних веза, углавном такве мреже преферирају к-повезан граф у дрво, тако да неуспех било које везе појединачно неће поделити мрежу на делове.

Други захтев ЕМСТ-а је алгоритам апроксимације константног фактора за приближно решење Еуклидовог проблема трговачког путника, верзија проблема трговачког путника на скупу тачака у равни са ивицама обележеним њиховим дужинама. Реалистична варијанта проблема може бити решена са фактором 2 рачунањем ЕМСТ-а, вршећи шетњу уз његову границу која оцртава цело стабло, и онда уклања сва осим једног појављивања сваког врха из ове шетње.

Раванска реализација

Проблем реализације за ЕМСТ-а је задат на следећи нацин: Дато је дрво Т = (V,Е), наћи локацију D(у) за сваки врх у ∈ V тако да је Т минимално разапињуће стабло од D(у): у ∈ V, или показати да таква локација не постоји. Тестирање постојања реализације у равни је НП-тежак проблем.