Изворни код странице Euklidovo minimalno razapinjuće stablo

[[Датотека:Euclidean minimum spanning tree.svg|thumb|300px|right|EMST za 25 nasumičnih tačaka u ravni]]

'''Euklidovo minimalno razapinjuće stablo''' ('''Euclidean minimum spanning tree - EMST''') je [[minimalno razapinjuće stablo]] skupa od ''n'' tačaka u [[ravan|ravni]] (ili uopštenije u ℝ<sup>''d''</sup>), gde je težina ivice između svakog para tačaka razdaljina između te dve tačke. U jednostavnijim uslovima, EMST povezuje skup tačaka koristeći linije takve da je totalna dužina svih linija minimizovana i do bilo koje tačke se može doći iz bilo koje druge prateći linije.

U ravni, EMST za zadati skup tačaka se može naći u O(n*log(n)) vremenu koristeći O(n) prostora u modelu računanja algebarskog stabla odluke. Brži nasumični algoritmi složenosti O(n log log n) su poznati u moćnijim modelima računanja koji preciznije modeliraju sposobnosti pravih računara.

U većim dimenzijama (''d'' ≥ 3), pronalazak optimalnog algoritma ostaje otvoren problem.

== Donja granica ==
Asimtotska donja granica od Ω(n log n) za vremensku složenost EMST problema može biti utvrđena u ograničenim modelima računanja, kakvi su algebarsko drvo odluke i algebarsko drvo za računanje, u kojima algoritam ima pristup ulaznim tačkama samo kroz određene ograničene primitive koje izvode jednostavno algebarsko računanje na njihovim koordinatama: u ovim modelima, problem najbližeg para tačaka zahteva Ω(n log n) vreme, ali najbliži par je obavezno ivica EMST-a, tako da EMST zahteva takođe toliko vremena. Kako god, ako ulazne tačke imaju celobrojne koordinate i bitske operacije i operacijama [[nasumičan pristup podacima|tabelarnog indeksiranja]] je dozvoljeno korišćenje tih koordinata, mogući su i brži algoritmi.

== Algoritmi za računanje EMST u dve dimenzije ==
Najjednostavniji algoritam za pronalaženje EMST u dve dimenzije, za zadatih ''n'' tačaka, je zapravo konstrukcija [[kompletan graf|kompletnog grafa]] od ''n'' vrhova, koji ima ''n''(''n''-1)/2 grana, računa se težina svake ivice nalazenjem rastojanja između svakog para tačaka, i onda se primenjuje standardni algoritam minimalnog razapinjućeg stabla (kakav je [[Primov algoritam]] ili [[Kruskalov algoritam]]) na njega. Pošto ovaj graf ima [[Veliko O|&Theta;]](''n''<sup>2</sup>) grana za n različitih tačaka, konstrukcija već zahteva vreme [[Veliko O|&Omega;]](''n''<sup>2</sup>). Ovo rešenje takođe zahteva Ω(''n''<sup>2</sup>) prostora da sačuva sve ivice.

Bolji pristup nalaženju EMST-a u prostoru ćemo dobiti ako primetimo da je to podstablo svake Delaunay-eve triangulacije od ''n'' tačaka, sa mnogo više redukovanim skupom grana:

1. Izračunavanje Delaunay-eve triangulacije u O(n log n) vremenu i O(n) prostoru. Zato što je Delaunay-eva triangulacija planarni graf i ne postoji više od tri puta koliko ima vrhova ili grana u bilo kom planarnom grafu, ovo generiše samo O(n) grana.

2. Obeležavanje svake grane svojom dužinom.

3. Pokretanje algoritma minimalnog razapinjućeg stabla grafa na ovom grafu da bi se našlo minimalno razapinjuće stablo. Pošto postoji O(n) grana, ovo zahteva O(n log n log n) vreme koristeći bilo koji od standardnih algoritama minimalnog razapinjućeg stabla kakvi su [[Boruvka algoritam|Borůvka]], [[Primov algoritam|Prim-ov]] ili [[Kruskalov algoritam|Kruskal-ov]] algoritam.

Konačan rezultat je algoritam koji uzima O(n log n) vremena i O(n) prostora.

Ako su unete koordinate celobrojne a mogu biti korišćene kao [[Niz (struktura podataka)|indeksi nizova]], mogući su i brži algoritmi: Delaunay-eva triangulacija može biti konstruisana nasumičnim algoritmom u očekivanom O(n log log n) vremenu. Dodatno, pošto je Delaunay-eva triangulacija planarni graf, njegovo minimalno razapinjće stablo može biti nađeno u linearnom vremenu varijantom Borůvka algoritma koji uklanja sve osim najjeftinije grane između svakog para komponenti posle svake faze algoritma. Stoga je ukupno očekivano vreme za ovaj algoritam O(n log log n).

== Više dimenzije ==
Problem može biti i uopšten do ''n'' tačaka ''d''-dimenzionog prostora ℝ<sup>''d''</sup>. U višim dimenzijama povezanost određena Delaunay-evom triangulacijom (koja, takođe, particioniše konveksan trup u ''d''-dimenzione jednostavnosti) minimalnog razapinjućeg stabla; kako god, triangulacija možda sadrži kompletan graf. Tako, nalazeći EMST kao razapinjuće stablo kompletnog grafa ili razapinjuće stablo Delaunay-eve triangulacije zahteva O(''dn''<sup>2</sup>) vreme. Za tri dimenzije moguće je pronaći minimalno razapinjuće stablo u vremenu O((''n''&nbsp;log&nbsp;''n'')<sup>4/3</sup>), i u bilo kojoj dimenziji većoj od tri moguće je rešiti u vremenu koje je brže od kvadratne vremenske granice za kompletne grafove i algoritme Delaunay-eve triangulacije. Za ravnomerno nasumične skupove tačaka moguće je izračunati minimalno razapinjuće drvo toliko brzo kao kod sortiranja.

== Podstablo Delaunay-eve triangulacije ==
[[Датотека:EMST Delaunay proof.png|right]]

Sve ivice EMST-a su ivice relativnog susedstva grafa, one su i ivice Gabriel-ovog grafa, i ivice u Delaunay-evoj triangulaciji tačaka, što može biti dokazano preko ekvivalentne kontrapozitivne izjave: svaka grana koja nije u Delaunay-evoj triangulaciji, takođe nije ni u jednom EMST. Dokaz je zasnovan na dva svojstva minimalnih razapinjućih stabala i Delaunay-eve triangulacije:

1. (kružno svojstvo minimalnih razapinjućih stabala - MRS): ''Za svaki cikl C u grafu, ako je težina grane ''e'' od ''C'' veća od težine druge dve grane u ''C'', onda ova grana ne može pripadati MRS''.

2. (svojstvo Delaunay-ih triangulacija): ''Ako postoji kružnica sa dve ulazne tačke na svojoj granici koja sadrži druge ulazne tačke, linija između te dve tačke je grana Delaunay-eve triangulacije''.

Razmotrimo granu ''e'' između dve ulazne tačke ''p'' i ''q'' koja nije grana Delaunay-eve triangulacije. Iz svojstva 2 sledi da kružnica ''C'' sa ''e'' kao svojim prečnikom mora da sadrži neku drugu tačku ''r'' unutar sebe. Ali onda je ''r'' blize i tački ''p'' i tački ''q'' nego što su one jedna drugoj, i tako je grana od ''p'' do ''q'' najduža grana u ciklu između tačaka ''p'' → ''q'' → ''r'' → ''p'', i po svojstvu 1 ''e'' nije ni u jednom EMST.

== Očekivana veličina ==
Očekivana veličina EMST-a za velike brojeve tačaka je određena od strane J. Michael Steele. Ako je <math>f</math> gustina verovatnoće funkcije odabira tačaka, onda za veliko <math>n</math> i <math>d \neq 1</math> veličina EMST-a je približno 

<math>c(d) n^{\frac{d-1}{d}} \int_{\mathbb{R}^d} f(x)^{\frac{d-1}{d}} dx </math>

gde je <math>c(d)</math> konstanta koja zavisi samo od dimenzije <math>d</math>. Tačne vrednosti konstanti su nepoznate ali mogu biti procenjene iz empirijskih dokaza.

== Aplikacije ==
Očigledan zahtev EMST-a je da pronađe najjeftiniju mrežu žica ili cevi koje povezuju niz mesta, pretpostavljajući da su cene veza po jedinici dužine fiksne. Kako god, dok ove daju apsolutnu donju granicu na iznos potrebnih veza, uglavnom takve mreže preferiraju ''k''-povezan graf u drvo, tako da neuspeh bilo koje veze pojedinačno neće podeliti mrežu na delove.

Drugi zahtev EMST-a je algoritam aproksimacije konstantnog faktora za približno rešenje Euklidovog problema trgovačkog putnika, verzija [[problem trgovačkog putnika|problema trgovačkog putnika]] na skupu tačaka u ravni sa ivicama obeleženim njihovim dužinama. Realistična varijanta problema može biti rešena sa faktorom 2 računanjem EMST-a, vršeći šetnju uz njegovu granicu koja ocrtava celo stablo, i onda uklanja sva osim jednog pojavljivanja svakog vrha iz ove šetnje.

== Ravanska realizacija ==
Problem ''realizacije'' za EMST-a je zadat na sledeći nacin: Dato je [[Stablo (teorija grafova)|drvo]] ''T'' = (''V'',''E''), naći lokaciju ''D''(''u'') za svaki vrh ''u''&nbsp;∈&nbsp;''V'' tako da je ''T'' minimalno razapinjuće stablo od ''D''(''u''):&nbsp;u&nbsp;∈&nbsp;V, ili pokazati da takva lokacija ne postoji. Testiranje postojanja realizacije u [[ravan|ravni]] je [[NP-teški problemi|NP-težak problem]].

{{normativna kontrola}}

{{СОРТИРАЊЕ:Еуклидово минимално разапињуће стабло}}
[[Категорија:Разапињућа стабла]]