Razapinjuće stablo minimalnog stepena

Minimalno razapinjuće stablo je razapinjuće stablo nekog povezanog, težinskog i neusmerenog grafa koje sadrži sve čvorove tog grafa, a zbir težina njegovih grana je minimalan.

Planaran graf na kome je podebljanom linijom označeno njegovo minimalno razapinjuće stablo

Jedan graf može imati više ovakvih stabala, zavisno od svoje konfiguracije. Ukoliko svakoj grani dodelimo određenu težinu onda je zbir težina grana u nekom razapinjućem stablu u stvari težina tog stabla. Minimalno razapinjuće stablo ili minimalno težinsko razapinjuće stablo je razapinjuće stablo čija je težina manja ili jednaka u odnosu na ostala razapinjuća stabla nekog grafa. Uopštenije, svaki neusmeren graf (ne nužno povezan) ima minimalnu razapinjuću šumu, koja je unija minimalnih razapinjućih stabala.

Postoji dosta slučajeva kada se koriste minimalna razapinjuća stabla. Tipičan problem koji se vezuje za ovo stablo je dostavljanje usluga telekomunikacione kompanije na više lokacija na što isplatljiviji način. Ako se pretpostavi da se kablovi zakopavaju duž određenih puteva (npr. duž kolovoza) onda bismo mogli napraviti graf koji predstavlja koje lokacije su povezane tim putevima. Neki od puteva su duži, ili zahtevaju da kablovi budu dublje zakopani, zbog čega su i skuplji; ti putevi su predstavljeni granama veće težine. Težina grane odgovara troškovima postavljanja kablova - nije neophodno da se dužine grana pridržavaju pravila geometrije kao što je nejednakost trouglova. Razapinjuće stablo tog grafa je podskup onih puteva koji ne obrazuju ciklus, a ipak povezuju sve lokacije; moguće je da postoji nekoliko razapinjućih stabala. Minimalno razapinjuće stablo je ono razapinjuće stablo koje ima najmanju težinu, odnosno čiji je trošak postavljanja kablova najmanji.

Osobine

Mogućnost mnogobrojnosti

Ova slika pokazuje da graf može imati više od jednog minimalnog razapinjućeg stabla. Na slici, dva stabla ispod grafa su u stvari dve mogućnosti minimalnog razapinjućeg stabla za dati graf.

Moguće je da u nekom grafu postoji nekoliko minimalnih razapinjućih stabala iste težine sa minimalnim brojem grana; posebno, ako su sve grane zadatog grafa iste težine, onda je svako razapinjuće stablo tog grafa minimalno.

Ako graf ima $n$ čvorova, tada svako razapinjuće stablo ima $n-1$ grana.

Jedinstvenost

Ukoliko svaka grana ima različitu težinu, tada graf sadrži samo jedno jedinstveno minimalno razapinjuće stablo. Ovo je najčešći slučaj u realnim situacijama, kao što je gorenavedeni primer telekomunikacione kompanije, gde je malo verovatno da dva puta snose potpuno iste troškove. Opštije gledano ovo važi i za razapinjuće šume.

Ako težine grana nisu jedinstvene, onda je samo multiskup težina u minimalnom razapinjućem stablu jedinstven, to je zajedničko za sva minimalna razapinjuća stabla.

Dokaz:

1. Pretpostavimo suprotno, da postoje dva različita minimalna razapinjuća stabla $A$ i $B$.
2. Neka je $e_{1}$ grana najmanje težine koja se nalazi samo u jednom minimalnom razapinjućem stablu. Bez gubitka opštosti, pretpostavimo da se $e_{1}$ nalazi u $A$ i ne nalazi u $B$.
3. Kako $B$ jeste minimalno razapinjuće stablo ${e_{1}}\cup B$ mora sadržati ciklus $C$.
4. Tada $C$ sadrži neku granu $e_{2}$ čija je težina veća od težine grane $e_{1}$, s obzirom da sve grane koje su manje od {$e_{1}$} i nalaze se u $B$ sadrže se i u $A$, i ciklus $C$ mora imati barem jednu granu koja nije u $A$ jer u suprotnom $A$ bi sadržalo ciklus što je kontradikcija sa tim da je ono i minimalno razapinjuće stablo.
5. Zamenom $e_{2}$ sa $e_{1}$ u $B$ dobija se razapinjuće stablo manje težine.
6. Ovo je u suprotnosti sa pretpostavkom da je $B$ minimalno razapinjuće stablo.

Podgraf minimalne težine

Ako su sve težine pozitivne tada je minimalno razapinjuće stablo u stvari podgraf minimalne težine koji sadrži sve čvorove, kako podgrafovi sadrže cikluse uglavnom su i veće težine.

Osobina ciklusa

Za svaki ciklus $C$ u nekom grafu važi da ako je grana $e$ koja se nalazi u ciklusu $C$ veće težine od svih drugih grana tog ciklusa, onda ta grana ne može pripadati minimalnom razapinjućem stablu.

Dokaz: Pretpostavimo suprotno, tj. da $e$ pripada minimalnom razapinjućem stablu $T_{1}$. Tada brisanjem grane $e$ $T_{1}$ se deli na dva podstabla kod kojih se jedan kraj grane $e$ nalazi u jednom, a drugi kraj u drugom podstablu. Ostatak ciklusa $C$ ponovo povezuje podstabla, pošto postoji grana $f$ iz $C$ koja ima krajeve u različitim podstablima, tj. ona ponovo povezuje podstabla u stablo $T_{2}$ težine manje nego $T_{1}$, jer je težina $f$ manja od težine $e$.

Osobina odsecanja

Na slici se vidi osobina odsecanja za minimalno razapinjuće stablo.

Za svaki odsečak $C$ iz nekog grafa važi da ako je težina grane $e$ (koja se nalazi u tom odsečku $C$) striktno manja od težina svih grana iz tog odsečka, onda ta grana $e$ pripada svim minimalno razapinjućim stablima tog grafa.

Grana minimalne težine

Ako je grana $e$ jedinstvena grana minimalne težine nekog grafa, onda se ona nalazi u svim minimalnim razapinjućim stablima tog grafa.

Dokaz: Pretpostavimo da se $e$ ne nalazi u minimalnom razapinjućem stablu, tada uklanjanjem bilo koje grane (veće težine) iz ciklusa $C$ koji je formiran nakon što je grana $e$ dodana u minimalno razapinjuće stablo se formira novo razapinjuće stablo manje težine.

Kontrakcija

Ako je $T$ stablo sastavljeno od grana iz minimalnog razapinjućeg stabla, onda možemo kontrahovati $T$ u jedan čvor dok održavamo invarijantu da minimalno razapinjuće stablo kontrahovanog grafa zajedno sa $T$ daje minimalno razapinjuće stablo grafa pre kontrakcije.

Algoritmi

U svim algoritmima ispod $m$ predstavlja broj grana u grafu dok $n$ predstavlja broj čvorova.

Klasičani algoritmi

Prvi algoritam za traženje minimalnog razapinjućeg stabla je razvio Češki naučnik Otakar Boruvka 1926. godine (videti Boruvkin algoritam). Njegova svrha je bila izgradnja električne mreže za Moravsku. Algoritam se izvršava u nekoliko faza. U svakoj fazi, nazvanoj Boruvkin korak, identifikuje se šuma $F$ koja se sastoji od grana incidentnih sa svakim čvorom u grafu $G$, zatim formira graf $G1=G\setminus F$ kao ulaz u sledećem koraku. Ovde $G\setminus F$ označava graf dobijen od $G$ odsecanjem grana u $F$ (Osobina odsecanja). Svaki Boruvkin korak je linearne složenosti. Pošto je broj čvorova redukovan za barem polovinu u svakom koraku, Boruvkin algoritam je složenosti $O(m\log n)$.

Drugi algoritam je Primov algoritam, koji je 1930. godine izumeo Vojteh Jarnik, a kasnije nezavisno od njega informatičar Robert Prim 1957, i ponovo Edsger Dajkstra 1959. Algoritam postepeno povećava veličinu stabla počevši od jednog čvora, dok ne poveže sve čvorove. Složenost Primovog algoritma je $O(m\log n$) ili $O(m+n\log n)$ u zavisnosti od strukture podataka koja se koristi.

Treći algoritam koji se često koristi je Kruskalov algoritam koji takođe ima složenost $O(m\log n)$.

Četvrti ne tako često korišćen algoritam je Algoritam obrnutog brisanja koji je suprotan Kruskalovom algoritmu. Njegova složenost je $O(m\log n(\log \log n)^{3})$.

Sva četiri algoritma spadaju u pohlepne algoritme.

Brži algoritmi

Nekoliko istraživanja su pokušala da pronađu više računski-efikasnijih algoritama.

U modelu poređenja, u kom su jedine dozvoljene operacije nad težinama grana operacije poređenje parova, Karger, Klejn i Tardžan 1995. godine pronašli su nasumični algoritam u linearnom vremenu baziran na kombinaciji Borvukinog algoritma i algoritma obrnutog brisanja.

Najbrži nenasumični baziran na poređenju algoritam sa poznatom složenošću napravljen od strane Bernard Šazela je baziran na približnom prioritetu soft hipa. Njegovo vreme izvršavanja je $O(m\alpha (m,n))$, gde $\alpha$ predstavlja klasičnu inverznu funkciju Akermanove funkcije. Funkcija $\alpha$ raste ekstremno sporo, tako da se za sve praktične svrhe može posmatrati kao konstanta ne veća od 4; stoga je Šazelov algoritam veoma blizu linearne složenosti.

Algoritam linearne sloeonsti u specijalnim slučajevima

Gusti grafovi

Ako je graf gust tj. $(m{/}n\geq \log \log \log n)$, onda Fredmanov i Tardžanov deterministički algoritam pronalazi minimalno razapinjuće stablo za vreme $O(m)$. Algoritam izvršava niz faza. Svaka faza izvršava Primov algoritam mnogo puta, svaki put za ograničen broj koraka. Vreme izvršavanja svake faze je $O(m+n)$. Ako je broj čvorova pre izvršavanja faze $n'$, onda je broj čvorova nakon izvršavanja faze $n'/2^{m/n'}$. Stoga je potrebno da se izvrši najviše $\log *{n}$ faza, što nam daje linearno vreme izvršavanja za guste grafove.

Postoje i drugi algoritmi koji rade sa gustim grafovima.

Celobrojne težine

Ako je težina grane ceo broj predstavljen u binarnom zapisu, onda je poznato da deterministički algoritmi rešavaju problem u $O(m+n)$ celobrojnih operacija. Iako se problem može rešiti deterministički za opšti graf u linearnoj složenosti, za algoritme bazirane na poređenju to ostaje otvoreno pitanje.

Stabla odlučivanja

Za zadat graf $G$ kod koga su čvorovi i grane fiksirane ali je težina nepoznata, moguće je konstruisati binarno stablo odlučivanja za računanje minimalnog razapinjućeg stabla za bilo koju permutaciju težina. Svaki unutrašnji čvor iz stabla odlučivanja sadrži poređenje između dve grane, npr. „ Da li je težina grane između čvorova $x$ i $y$ veća od težine grane između čvorova $w$ i $z$?“. Dva deteta čvora odgovaraju odgovorima „da“ ili „ne“. U svakom listu stabla odlučivanja postoji lista grana koja odgovara minimalnom razapinjućem stablu. Složenost izvršavanja stabla odlučivanja jednaka je najvećem broju upita potrebnim da se nađe minimalno razapinjuće stablo, što je u stvari dubina stabla odlučivanja. Stablo odlučivanja za graf $G$ je optimalno ako ima najmanju dubinu u odnosu na sva ispravna stabla odlučivanja iz grafa $G$.

Za svaki ceo broj $r$, moguće je pronaći optimalna stabla odlučivanja za sve grafove sa $r$ čvorova, pomoću iscrpne pretrage.

A. Generisanje svih potencijalnih stabala odlučivanja

• Postoji $2^{r \choose 2}$ različitih grafova sa $r$ čvorova.
• Za svaki graf, minimalno razapinjuće stablo se može naći pomoću $r\cdot (r-1)$ poređenja, npr. pomoću Primovog algoritma.
• Stoga, dubina optimalnog stabla odlučivanja je $r^{2}$.
• Dakle, broj čvorova u optimalnom stablu odlučivanja je manji od $2^{r^{2}}$.
• Svaki unutrašnjni čvor poredi dve grane. Broj grana je najviše $r^{2}$, tako da postoji najviše $r^{4}$ različitih poređenja.
• Dakle, broj potencijalnih stabala odlučivanja je manji od: ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$.

B. Pronalaženje ispravnih stabala odlučivanja

Da bismo proverili da li je stablo odlučivanja ispravno, potrebno je proveriti ga za sve moguće permutacije težina grana.

• Broj takvih permutacija je najviše $(r^{2})!$.
• Za svaku permutaciju rešava se problem minimalnog razapinjućeg stabla za dat graf koristeći bilo koji postojeći algoritam, i rezultat se poredi sa odgovorom dobijenim iz stabla odlučivanja.
• Vreme izvršavanja bilo kog algoritma za minimalno razapinjuće stablo je najviše $(r^{2})$, tako da je ukupno vreme da se provere sve permutacije najviše $(r^{2}+1)!$.

Stoga, ukupno vreme koje je potrebno da se pronađe optimalno stablo odlučivanja za sve grafove sa $r$ čvorova iznosi: $2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!$ što je manje od: $2^{2^{r^{2}+o(r)}}$.

Optimalan algoritam

Seth Petit i Vidžaja Ramačandran su pronašli optimalni deterministički baziran na komparaciji algoritam koji pronalazi minimalno razapinjuće stablo. U nastavku je opisan pojednostavljen prikaz algoritma.

1. Neka je $r=\log \log \log n$, gde $n$ predstavlja broj čvorova. Potrebno je pronaći sva optimalna stabla odlučivanja sa $r$. Ovo se može uraditi za vreme $O(n)$.
2. Podeliti graf na komponente, tako da u svakoj komponenti ima najviše $r$ čvorova. Ova podela se može izvršiti za $O(m)$ vremena.
3. Koristimo optimalno stablo odlučivanja da bismo našli minimalno razapinjuće stablo u svakoj komponenti.
4. Kontrahujemo svaku povezanu komponentu obuhvaćenu minimalnim razapinjućim stablom u po jedan čvor.
5. Moguće je dokazati da dobijeni graf ima najviše $n{/}r$ čvorova. Dakle, graf je gust i mi možemo koristiti bilo koji algoritam koji se koristi kod gustih grafova u vremenu $O(m)$.

Vreme izvršavanja svih koraka u algoritmu je $O(m)$, izuzev koraka gde se koriste stabla odlučivanja. Mi ne znamo vreme izvršavanja ovog koraka, ali znamo da je optimalno - nijedan algoritam ne može dati bolji rezutat od optimalnog stabla odlučivanja.

Prema tome, ovaj algoritam ima čudnu osobinu da je dokazivo optimalan iako je njegova složenost nepoznata.

Paralelni i raspodeljeni algoritmi

Pri istraživanju problema minimalnog razapinjućeg stabla uzeti su u obzir i paralelni algoritmi. Sa linearnim brojem procesora moguće je rešiti ovaj problem za $O(\log n)$ vremena. Bader i Čong 2006. godine su demonstrirali algoritam koji može da pronađe minimalna razapinjuća stabla 5 puta brže na 8 procesora nego optimizovani sekvencijalni algoritam.

Ostali specijalizovani algoritmi dizajnirani za nalaženje minimalnog razapinjućeg stabla su toliko veliki da većim delom moraju biti čuvani na disku sve vreme. Ovi algoritmi sa spoljašnjim skladištenjem, kao na primer oni koji su opisani u radu „Konstrukcija algoritma za pronalaženje minimalnog razapinjućeg stabla koji koristi eksternu memoriju“ od Romana Dementijeva mogu, se izvršavati, kako autor tvrdi, 2 do 5 puta sporije nego tradicionalni algoritmi koji koriste unutrašnju memoriju. Oni se oslanjaju na efikasno spoljašnje sortiranje i na kontrakciju grafa - tehniku za efikasno smanjenje veličine grafa.

Problemu se takođe može pristupiti pomoću raspodeljenog izračunavanja. Ako se svaki čvor posmatra kao računar i nijedan čvor ne zna ništa sem veza sa kojima je povezan, jedan sigurno može pronaći distribuirano minimalno razapinjuće stablo.

Minimalno razapinjuće stablo u kompletnim grafovima

Alan M. Friz je pokazao da zadat kompletan graf sa $n$ čvorova, koji ima grane čije su težine nezavisne identično raspoređene slučajne promenljive sa funkcijom raspodele $F$ zadovoljava $F'(0)>0$, i kako $n$ prilazi +∞ očekivana težina minimalnog razapinjućeg stabla se približava $\zeta (3)/F'(0)$, gde $\zeta$ predstavlja Rimanovu zeta-funkciju. Friz i Stil su takođe dokazali konvergenciju u verovatnoći. Svante Janson je dokazao centralnu graničnu teoremu za težinu minimalnog razapinjućeg stabla.

Za nasumično odabrane težine iz intervala $[0,1]$,tačna očekivana veličina minimalnog razapinjućeg stabla je izračunata za male kompletne grafove.

Čvorovi	Očekivana veličina	Približna očekivana veličina
2	1 / 2	0.5
3	3 / 4	0.75
4	31 / 35	0.8857143
5	893 / 924	0.9664502
6	278 / 273	1.0183151
7	30739 / 29172	1.053716
8	199462271 / 184848378	1.0790588
9	126510063932 / 115228853025	1.0979027