Euklidovo minimalno razapinjuće stablo

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 ravni (ili uopštenije u ℝ^d), 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 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 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 Θ(n²) grana za n različitih tačaka, konstrukcija već zahteva vreme Ω(n²). Ovo rešenje takođe zahteva Ω(n²) 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 Borůvka, Prim-ov ili 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 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 ℝ^d. 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²) vreme. Za tri dimenzije moguće je pronaći minimalno razapinjuće stablo u vremenu O((n log n)^4/3), 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

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 $f$ gustina verovatnoće funkcije odabira tačaka, onda za veliko $n$ i $d\neq 1$ veličina EMST-a je približno

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

gde je $c(d)$ konstanta koja zavisi samo od dimenzije $d$. 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 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 drvo T = (V,E), naći lokaciju D(u) za svaki vrh u ∈ V tako da je T minimalno razapinjuće stablo od D(u): u ∈ V, ili pokazati da takva lokacija ne postoji. Testiranje postojanja realizacije u ravni je NP-težak problem.