Minimalus besidriekiantis medis
Keletas grafų teorijos uždavinių yra vadinami minimaliuoju besidriekiančiu medžiu. Grafų teorijoje medis - tai būdas sujungti visas viršūnes taip, kad iš bet kurios viršūnės į bet kurią kitą medžio viršūnę būtų lygiai vienas kelias. Jei grafas vaizduoja kelis miestus, sujungtus keliais, galima parinkti tokį kelių skaičių, kad kiekvieną miestą būtų galima pasiekti iš kiekvieno kito, bet kad iš vieno miesto į kitą būtų galima keliauti tik vienu keliu.
Grafe gali būti daugiau nei vienas besidriekiantis medis, lygiai taip pat, kaip gali būti daugiau nei vienas būdas pasirinkti kelius tarp miestų.
Dažniausiai grafikai yra svertiniai; kiekvienas susisiekimas tarp dviejų miestų turi svorį: kelionė tam tikru keliu gali kainuoti arba vienas susisiekimas gali būti ilgesnis už kitą, o tai reiškia, kad kelionė tuo susisiekimu užtrunka ilgiau. Grafų teorijos kalba jungtys vadinamos briaunomis.
Mažiausias besidriekiantis medis yra medis. Jis skiriasi nuo kitų medžių tuo, kad minimizuoja briaunų svorių sumą. Priklausomai nuo grafo išvaizdos, gali būti daugiau nei vienas minimalus erdvinis medis. Grafe, kuriame visos briaunos turi vienodą svorį, kiekvienas medis yra minimalus medis. Jei visos briaunos turi skirtingus svorius (t. y. nėra dviejų briaunų su vienodais svoriais), yra lygiai vienas minimalus medis.
Plokščiojo grafo minimalus ištęstinis medis. Kiekviena briauna pažymėta jos svoriu, kuris čia maždaug proporcingas jos ilgiui.
Minimalaus besidriekiančio medžio radimas
Pirmasis bandymas
Gali būti labai paprasta sukurti algoritmą, kuris atrastų minimalųjį ištęstinį medį:
funkcija MST(G,W): T = {} kol T nesudaro medžio: suraskite mažiausią E svertinę briauną, kuri yra saugi T T = T sąjunga {(u,v)} grąžinti TŠiuo atveju "saugus" reiškia, kad, įtraukus briauną, grafas nesudaro ciklo. Ciklas reiškia, kad pradedama nuo viršūnės, keliaujama į kelias kitas viršūnes ir vėl baigiama pradiniame taške, nenaudojant tos pačios briaunos du kartus.
Istorija
1926 m. čekų mokslininkas Otakaras Borůvka sukūrė pirmąjį žinomą algoritmą, skirtą mažiausiam medžiui rasti. Jis norėjo išspręsti efektyvaus Moravijos padengimo elektra problemą. Šiandien šis algoritmas žinomas kaip Borůvkos algoritmas. Šiandien plačiai naudojami dar du algoritmai. Vieną iš jų 1930 m. sukūrė Vojtěchas Jarnikas (Vojtěch Jarník), o 1957 m. jį praktiškai pritaikė Robertas Klėjus Primas (Robert Clay Prim). Edsgeris Vybe Dijkstra jį iš naujo atrado 1959 m. ir pavadino Prim'o algoritmu. Kitas algoritmas vadinamas Kruskalio algoritmu, jį 1956 m. ištraukė Josephas Kruskalis. Visi trys algoritmai yra godūs ir veikia per polinominį laiką.
Greičiausią iki šiol minimalaus besidriekiančio medžio algoritmą sukūrė Bernardas Chazelis. Algoritmas pagrįstas minkštąja krūva - apytiksle prioritetų eile. Jo veikimo laikas yra O(m α(m,n)), kur m - briaunų skaičius, n - viršūnių skaičius, o α - klasikinė funkcinė atvirkštinė Ackermanno funkcija. Funkcija α auga labai lėtai, todėl visais praktiniais tikslais ją galima laikyti konstanta, ne didesne kaip 4; taigi Chazelle'io algoritmas trunka labai arti tiesinio laiko.
Koks yra greičiausias įmanomas šio uždavinio algoritmas? Tai vienas seniausių atvirų informatikos klausimų. Akivaizdu, kad yra tiesinė apatinė riba, nes turime bent jau patikrinti visus svorius. Jei briaunų svoriai yra sveikieji skaičiai su ribotu bitų ilgiu, tada žinomi deterministiniai algoritmai su tiesiniu veikimo laiku. Bendriesiems svoriams yra atsitiktinių imčių algoritmų, kurių tikėtinas vykdymo laikas yra tiesinis.
Problemą taip pat galima spręsti paskirstytuoju būdu. Jei kiekvienas mazgas laikomas kompiuteriu ir nė vienas mazgas nežino nieko, išskyrus savo sujungtas jungtis, vis tiek galima apskaičiuoti paskirstytąjį minimalųjį ištęstinį medį.
Klausimai ir atsakymai
Klausimas: Kas grafų teorijoje yra mažiausias apimantis medis (angl. minimum spanning tree)?
Atsakymas: Grafų teorijoje minimalus medis - tai medis, kuris minimizuoja bendrą briaunoms priskirtų svorių sumą.
K: Kas yra medis grafų teorijoje?
A: Grafų teorijoje medis yra būdas sujungti visas viršūnes taip, kad iš bet kurios viršūnės į bet kurią kitą medžio viršūnę būtų tik vienas kelias.
K: Kokiu tikslu grafų teorijos scenarijuje, kuriame vaizduojami miestai, pasirenkami keliai?
A: Grafų teorijos scenarijuje, kuriame vaizduojami miestai, keliai parenkami taip, kad kiekvieną miestą būtų galima pasiekti iš kiekvieno kito miesto, tačiau iš vieno miesto į kitą būtų galima keliauti tik vienu keliu.
Klausimas: Ar grafas gali turėti daugiau nei vieną besidriekiantį medį?
A: Taip, grafas gali turėti daugiau nei vieną atraminį medį.
K: Kuo skiriasi minimalus medis nuo kitų grafų teorijoje naudojamų medžių?
A: Minimalus medis minimizuoja bendrą briaunų svorį, o kiti medžiai šios savybės neturi.
K: Kas grafų teorijoje yra briaunos?
Atsakymas: Grafų teorijoje briaunos yra ryšiai tarp dviejų viršūnių.
Klausimas: Ar gali būti daugiau nei vienas minimalus medis grafe su skirtingais briaunų svoriais?
A: Taip, priklausomai nuo grafo išvaizdos, gali būti daugiau nei vienas minimalus erdvinis medis.
