Minimálna kostra grafu
Viaceré problémy z teórie grafov sa nazývajú minimálny rozprestierajúci sa strom. V teórii grafov je strom spôsob spojenia všetkých vrcholov tak, aby z ľubovoľného vrcholu do ľubovoľného iného vrcholu stromu viedla presne jedna cesta. Ak graf predstavuje niekoľko miest spojených cestami, možno vybrať taký počet ciest, aby sa do každého mesta dalo dostať z každého iného, ale aby neexistovala viac ako jedna cesta z jedného mesta do druhého.
Graf môže mať viac ako jeden strom rozpätí, rovnako ako môže existovať viac ako jeden spôsob výberu ciest medzi mestami.
Väčšinou sú grafy vážené; každé spojenie medzi dvoma mestami má určitú váhu: cesta po danej ceste môže niečo stáť alebo jedno spojenie môže byť dlhšie ako druhé, čo znamená, že cesta týmto spojením trvá dlhšie. V jazyku teórie grafov sa spojenia nazývajú hrany.
Minimálny rozprestierajúci sa strom je strom. Od ostatných stromov sa líši tým, že minimalizuje súčet váh priradených k hranám. V závislosti od toho, ako graf vyzerá, môže existovať viac ako jeden minimálny rozpínací strom. V grafe, v ktorom majú všetky hrany rovnakú váhu, je každý strom minimálnym rozpínacím stromom. Ak majú všetky hrany rôzne váhy (to znamená, že neexistujú dve hrany s rovnakou váhou), existuje presne jeden minimálny rozprestierajúci sa strom.
Minimálny strom rovinného grafu. Každá hrana je označená svojou váhou, ktorá je tu približne úmerná jej dĺžke.
Nájdenie minimálneho rozprestierajúceho sa stromu
Prvý pokus
Môže byť veľmi jednoduché vytvoriť algoritmus, ktorý objaví minimálny rozprestierajúci sa strom:
funkcia MST(G,W): T = {} kým T netvorí rozprestierajúci sa strom: nájdite minimálnu váženú hranu v E, ktorá je bezpečná pre T T = T union {(u,v)} return TV tomto prípade "bezpečné" znamená, že zahrnutie hrany nevytvára v grafe cyklus. Cyklus znamená, že sa začína v určitom vrchole, prechádza sa do niekoľkých ďalších vrcholov a končí sa opäť vo východiskovom bode bez toho, aby sa dvakrát použila tá istá hrana.
História
Český vedec Otakar Borůvka vyvinul v roku 1926 prvý známy algoritmus na nájdenie minimálneho rozvetvenia stromu. Chcel vyriešiť problém nájdenia efektívneho pokrytia Moravy elektrickou energiou. Dnes je tento algoritmus známy ako Borůvkov algoritmus. Dnes sa bežne používajú ďalšie dva algoritmy. Jeden z nich vyvinul Vojtěch Jarník v roku 1930 a do praxe ho uviedol Robert Clay Prim v roku 1957. Edsger Wybe Dijkstra ho znovu objavil v roku 1959 a nazval ho Primov algoritmus. Druhý algoritmus sa nazýva Kruskalov algoritmus a v roku 1956 ho vytiahol Joseph Kruskal. Všetky tri algoritmy sú chamtivé a bežia v polynomiálnom čase.
Doteraz najrýchlejší algoritmus minimálneho rozprestierajúceho sa stromu vyvinul Bernard Chazelle. Algoritmus je založený na mäkkej halde, približnom prioritnom fronte. Jeho čas behu je O(m α(m,n)), kde m je počet hrán, n je počet vrcholov a α je klasická funkčná inverzia Ackermannovej funkcie. Funkcia α rastie extrémne pomaly, takže pre všetky praktické účely ju možno považovať za konštantu nie väčšiu ako 4; Chazelleho algoritmus teda trvá veľmi blízko lineárneho času.
Aký je najrýchlejší možný algoritmus pre tento problém? To je jedna z najstarších otvorených otázok v informatike. Jednoznačne existuje lineárna dolná hranica, pretože musíme preskúmať aspoň všetky váhy. Ak sú váhy hrán celé čísla s ohraničenou bitovou dĺžkou, potom sú známe deterministické algoritmy s lineárnym časom behu. Pre všeobecné váhy existujú randomizované algoritmy, ktorých očakávaný čas behu je lineárny.
K problému možno pristupovať aj distribuovaným spôsobom. Ak je každý uzol považovaný za počítač a žiadny uzol nepozná nič okrem svojich vlastných pripojených spojení, stále je možné vypočítať distribuovaný minimálny rozprestierajúci sa strom.
Otázky a odpovede
Otázka: Čo je v teórii grafov strom minimálneho rozpätia?
Odpoveď: Minimálny rozpínací strom je v teórii grafov strom, ktorý minimalizuje celkové váhy priradené k hranám.
Otázka: Čo je to strom v teórii grafov?
Odpoveď: Strom je spôsob spojenia všetkých vrcholov v teórii grafov tak, aby z ktoréhokoľvek vrcholu do ktoréhokoľvek iného vrcholu stromu viedla len jedna cesta.
Otázka: Aký je účel výberu ciest v scenári teórie grafov, ktorý predstavuje mestá?
Odpoveď: Účelom výberu ciest v scenári teórie grafov, ktorý predstavuje mestá, je umožniť, aby sa do každého mesta dalo dostať z každého iného mesta, ale aby neexistovala viac ako jedna možná cesta z jedného mesta do druhého.
Otázka: Môže mať graf viac ako jeden rozprestierajúci sa strom?
Odpoveď: Áno, graf môže mať viac ako jeden strom rozpätí.
Otázka: Aký je rozdiel medzi minimálnym stromom rozpätia a inými stromami v teórii grafov?
Odpoveď: Minimálny strom minimalizuje celkové váhy priradené k hranám, zatiaľ čo ostatné stromy túto vlastnosť nemajú.
Otázka: Čo sú hrany v teórii grafov?
Odpoveď: Hrany sú v teórii grafov spojenia medzi dvoma vrcholmi.
Otázka: Môže v grafe existovať viac ako jeden minimálny rozpínací strom s rôznymi váhami hrán?
Odpoveď: Áno, v závislosti od toho, ako graf vyzerá, môže existovať viac ako jeden minimálny rozpínací strom.
