Minimalno vpeto drevo
Š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.
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 TV 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.
