Minimalno vpeto drevo definicija, lastnosti in algoritmi Kruskal in Prim

Številni problemi iz teorije grafov se imenujejo minimalno raztezno drevo. V teoriji grafov je drevo način povezovanja vseh vrhov med seboj, tako da obstaja natanko ena pot od kateregakoli vrha do kateregakoli drugega vrha drevesa. Če graf predstavlja več mest, povezanih s cestami, lahko izberemo število cest tako, da je do vsakega mesta mogoče priti iz vsakega drugega, vendar da ni več kot ene poti iz enega mesta v drugo.

Graf ima lahko več kot eno razpetostno drevo, tako kot je lahko več načinov izbire cest med mesti.

Večinoma so grafi uteženi; vsaka povezava med dvema mestoma ima določeno utež: potovanje po določeni cesti lahko nekaj stane ali pa je ena povezava daljša od druge, kar pomeni, da potovanje po tej povezavi traja dlje časa. V jeziku teorije grafov se povezave imenujejo robovi.

Minimalno raztezno drevo je drevo. Od ostalih dreves se razlikuje po tem, da se pri njem zmanjšuje vsota uteži, pripisanih robovom. Odvisno od videza grafa lahko obstaja več kot eno minimalno raztezno drevo. V grafu, kjer imajo vsi robovi enako težo, je vsako drevo minimalno raztezno drevo. Če imajo vsi robovi različne uteži (to pomeni, da ni dveh robov z enako utežjo), obstaja natanko eno minimalno raztezno drevo.

Definicija

Naj bo G = (V, E) povezan utežen graf, kjer je vsaki rabi (robu) e ∈ E dodeljena utež w(e) (realno število). Minimalno raztezno drevo (MST - minimum spanning tree) je podmnožica robov T ⊆ E, za katero velja:

T povezuje vse vrhove (spanning): graf (V, T) je povezan,
(V, T) je acikličen (drevo),
vsota uteži Σ_{e∈T} w(e) je minimalna med vsemi takimi drevesi.

Če graf ni povezan, govorimo o minimalnem raztezno gozd (minimum spanning forest) — MST za vsak povezani komponent posebej.

Lastnosti MST

Acykličnost in povezljivost: Vsako MST je drevo, torej vsebuje natanko |V|-1 robov (če je graf povezan).
Krajnostne lastnosti (cut in cycle properties):
- Cut property: Za katerikoli razrez (cut) množice vrhov, najmanjši rob, ki povezuje dve različni strani razreza, je del nekega MST.
- Cycle property: Za katerikoli cikel v grafu, rob z največjo utežjo v tem ciklu ne more biti del MST (če je njegova utež strogo največja v ciklu).
Enoličnost: Če so uteži vseh robov med seboj različne, je MST enoličen. Če so uteži enake, lahko obstaja več MST-jev z enako skupno utežjo.
Optimalnost in lokalne odločitve: Algoritmi za MST temeljijo na dejstvu, da lokalno najboljši (najmanjši) rob ob nekem razrezu lahko vedno razširi delno rešitev do optimalne globalne rešitve.

Algoritmi za iskanje MST

Najbolj razširjena pristopa sta Kruskalov in Primov algoritem. Obe metodi uporabljata zgornji cut/cycle lastnosti, vendar se razlikujeta v pristopu in podatkovnih strukturah.

Kruskalov algoritem

Ideja: razvrstimo vse robove naraščajoče po uteži in jih postopoma dodajamo k rešitvi, kadar njihova dodaja ne tvori cikla.

Koraki:
1. Razvrsti vse robove E po utežeh v naraščajočem vrstnem redu.
2. Inicializiraj prazno množico T = ∅ in strukturo za združevanje komponent (disjoint-set / union-find) z V posameznimi komponentami.
3. Za vsak rob e v sortiranem seznamu: če končna vozlišča robu e pripadajo različnim komponentam, dodaj e v T in združi ti dve komponenti.
4. Postopek končaj, ko T vsebuje |V|-1 rob ali ko so pregledani vsi robovi.
Potrebne podatkovne strukture: sortiranje robov in DSU (union-find) za testiranje ciklov.
Časovna zahtevnost: O(E log E) za sortiranje, kar je enako O(E log V) v povezanem grafu (E≥V-1). Z učinkovitim union-findom se amortizacijski čas za operacije združevanja zmanjša na skoraj konstantnega (inverse-Ackermannova funkcija).
Prednosti: enostaven za implementacijo, učinkovito za redke grafe in primeren, kadar imamo seznam robov že na voljo.

Primov algoritem

Ideja: raste drevo od izbranega začetnega vrha tako, da vedno izberemo najmanjši rob, ki povezuje trenutno drevo z ostalimi vrhovi.

Koraki:
1. Izberi poljuben začetni vrh r in označi ga kot del drevesa.
2. Med vsemi robovi, ki stopajo iz že vključenih vrhov v neoblike vrhove, izberi rob z najmanjšo utežjo in ga dodaj v drevo.
3. Ponavljaj, dokler niso vključeni vsi vrhovi.
Potrebne podatkovne strukture: prioritna vrsta (min-heap) za hitro izbiro najmanjšega robu; pogosto se uporablja tabela minimalnih razdalj (ključev) do vsakega vrha in heap za posodabljanje ključev.
Časovna zahtevnost: z binarnim kopičem (binary heap) O(E log V); z Fibonacci kopičem lahko zmanjšamo na O(E + V log V).
Prednosti: zelo učinkovit v gostih grafih in ko začnemo iz določenega vozlišča; deluje tudi z matriko sosednosti.

Zakaj algoritmi delujejo — skica dokaza

Oba algoritma sta pravilna zaradi cut property: kadar izberemo najmanjši rob, ki povezuje trenutno kompaktno množico vrhov z ostalimi, ta rob je vedno del nekaj MST. Kruskal obravnava robove globalno po utežeh, kar zagotavlja, da ne izpusti nujno potrebnih majhnih robov; Prim raste drevo in lokalno vedno izbere minimalen rob iz reza med vključeno množico in ostalimi vrhovi.

Implementacijske opombe in variacije

Če je graf neusmerjen in z utežmi celih števil, je pogosto priporočljivo uporabljati stabilno sortiranje ali natančno obravnavati primerke enakih uteži — kljub temu bodo rezultati pravilni, MST morda ne bo enoličen.
Za zelo velike grafe so pomembne implementacijske optimizacije: učinkoviti heapi, povezave in shranjevanje robov, zunanje sortiranje, porazdeljeni algoritmi ipd.
Variacije:
- Maximum spanning tree — po analogiji zgrajen tako, da maksimizira vsoto uteži (preprosto zamenjamo vrstni red sortiranja).
- Minimum spanning forest — če graf ni povezan, oba algoritma vrneta MST za vsak komponent posebej.

Uporabne praktične uporabe

Načrtovanje omrežij (električna omrežja, telekomunikacije, ceste) z minimalnimi stroški.
Klasifikacija in združevanje podatkov (hierarhično grozdenje) z minimizacijo povezovalnih stroškov.
Generiranje labirintov (randomizirani Kruskal ali Prim za generiranje naključnih dreves).
Optimizacija povezav v računalniških omrežjih in oblikovanje topologij z minimalno porabo kablov.

Za nadaljnje razumevanje se priporoča preučitev konkretnih primerov korak-po-korak (s shemami), eksperimentalna implementacija Kruskalovega in Primovega algoritma ter spoznavanje podatkovnih struktur, kot so union-find in prioritete/heapi.

Najmanjše razpetostno drevo ravninskega grafa. Vsak rob je označen z utežjo, ki je tukaj približno sorazmerna z njegovo dolžino.

Iskanje minimalnega razteznega drevesa

Prvi poskus

Algoritem, ki bo odkril minimalno raztezno drevo, je lahko zelo preprost:

funkcija MST(G,W): T = {} dokler T ne tvori razteznega drevesa: poišči najmanjši obteženi rob v E, ki je varen za T T T = T union {(u,v)} vrni T

V tem primeru "varen" pomeni, da vključitev roba ne tvori cikla v grafu. Cikel pomeni, da se začne v nekem vrholu, potuje do več drugih vrholov in se spet konča v začetni točki, ne da bi se dvakrat uporabil isti rob.

Zgodovina

Češki znanstvenik Otakar Borůvka je leta 1926 razvil prvi znani algoritem za iskanje minimalnega razpetega drevesa. Želel je rešiti problem iskanja učinkovite pokritosti Moravske z električno energijo. Danes je ta algoritem znan kot Borůvkov algoritem. Danes se pogosto uporabljata še dva druga algoritma. Enega je leta 1930 razvil Vojtěch Jarník, v praksi pa ga je leta 1957 uporabil Robert Clay Prim. Edsger Wybe Dijkstra ga je ponovno odkril leta 1959 in ga poimenoval Primov algoritem. Drugi algoritem se imenuje Kruskalov algoritem, leta 1956 pa ga je razvil Joseph Kruskal. Vsi trije algoritmi so požrešni in se izvajajo v polinomskem času.

Najhitrejši algoritem minimalnega razteznega drevesa do zdaj je razvil Bernard Chazelle. Algoritem temelji na mehkem kupu, približni prioritetni vrstici. Njegov čas delovanja je O(m α(m,n)), kjer je m število robov, n število vrhov in α klasična funkcionalna inverzija Ackermannove funkcije. Funkcija α raste izredno počasi, tako da jo za vse praktične namene lahko štejemo za konstanto, ki ni večja od 4; tako Chazellov algoritem traja zelo blizu linearnega časa.

Kateri je najhitrejši možni algoritem za ta problem? To je eno najstarejših odprtih vprašanj v računalništvu. Jasno je, da obstaja linearna spodnja meja, saj moramo pregledati vsaj vse uteži. Če so uteži robov cela števila z omejeno dolžino bitov, so znani deterministični algoritmi z linearnim časom delovanja. Za splošne uteži obstajajo randomizirani algoritmi, katerih pričakovani čas delovanja je linearen.

Težave se lahko lotimo tudi na porazdeljen način. Če se vsako vozlišče obravnava kot računalnik in nobeno vozlišče ne pozna ničesar razen svojih povezanih povezav, lahko še vedno izračunamo porazdeljeno minimalno raztezno drevo.

Vprašanja in odgovori

V: Kaj je v teoriji grafov najmanjše raztezno drevo?

O: Minimalno raztezno drevo je drevo, ki v teoriji grafov zmanjšuje skupne uteži, pripisane robovom.

V: Kaj je drevo v teoriji grafov?

O: Drevo je način povezovanja vseh vrhov v teoriji grafov, tako da obstaja samo ena pot od kateregakoli vrha do kateregakoli drugega vrha drevesa.

V: Kakšen je namen izbire cest v scenariju teorije grafov, ki predstavlja mesta?

O: Namen izbire cest v scenariju teorije grafov, ki predstavlja mesta, je omogočiti, da je vsako mesto dosegljivo iz vsakega drugega mesta, vendar z največ eno možno potjo iz enega mesta v drugo.

V: Ali ima lahko graf več kot eno raztezno drevo?

O: Da, graf ima lahko več kot eno raztezno drevo.

V: Kakšna je razlika med minimalnim razteznim drevesom in drugimi drevesi v teoriji grafov?

O: Minimalno raztezno drevo zmanjšuje skupne uteži robov, medtem ko druga drevesa te lastnosti nimajo.

V: Kaj so robovi v teoriji grafov?

O: V teoriji grafov so robovi povezave med dvema vrhovoma.

V: Ali je v grafu lahko več kot eno minimalno raztezno drevo z različno obteženimi robovi?

O: Da, odvisno od videza grafa je lahko več kot eno minimalno raztezno drevo.