Minimální rozpínací strom
Řada problémů z teorie grafů se nazývá minimální rozpínací strom. V teorii grafů je strom způsob propojení všech vrcholů tak, aby z libovolného vrcholu vedla přesně jedna cesta do libovolného jiného vrcholu stromu. Pokud graf představuje řadu měst propojených silnicemi, lze zvolit takový počet cest, aby se do každého města dalo dostat z každého jiného, ale aby neexistovala více než jedna cesta z jednoho města do druhého.
Graf může mít více než jeden rozpínací strom, stejně jako může existovat více než jeden způsob výběru silnic mezi městy.
Grafy jsou většinou vážené; každé spojení mezi dvěma městy má určitou váhu: cesta po dané silnici může něco stát nebo jedno spojení může být delší než druhé, což znamená, že cesta po tomto spojení trvá déle. V jazyce teorie grafů se spojení nazývají hrany.
Minimální rozpínací strom je strom. Od ostatních stromů se liší tím, že minimalizuje součet vah připojených k hranám. V závislosti na tom, jak graf vypadá, může existovat více než jeden minimální rozpínací strom. V grafu, kde mají všechny hrany stejnou váhu, je každý strom minimálním rozpínacím stromem. Pokud mají všechny hrany různé váhy (to znamená: neexistují dvě hrany se stejnou váhou), existuje právě jeden minimální rozpínací strom.
Minimální spřádací strom rovinného grafu. Každá hrana je označena svou váhou, která je zde zhruba úměrná její délce.
Nalezení minimálního rozpínacího stromu
První pokus
Vytvořit algoritmus, který objeví minimální spřádací strom, může být velmi jednoduché:
funkce MST(G,W): T = {} dokud T netvoří protahovací strom: najděte minimální váženou hranu v E, která je bezpečná pro T T = T union {(u,v)} return TV tomto případě "bezpečný" znamená, že zahrnutí hrany nevytvoří v grafu cyklus. Cyklus znamená začít v jednom vrcholu, přejít do několika dalších vrcholů a skončit opět ve výchozím bodě, aniž by byla dvakrát použita stejná hrana.
Historie
Český vědec Otakar Borůvka vyvinul v roce 1926 první známý algoritmus pro nalezení minimálního protahovacího stromu. Chtěl vyřešit problém nalezení efektivního pokrytí Moravy elektrickou energií. Dnes je tento algoritmus známý jako Borůvkův algoritmus. Dnes se běžně používají dva další algoritmy. Jeden z nich vyvinul Vojtěch Jarník v roce 1930 a do praxe jej uvedl Robert Clay Prim v roce 1957. Edsger Wybe Dijkstra jej znovu objevil v roce 1959 a nazval jej Primův algoritmus. Druhý algoritmus se nazývá Kruskalův algoritmus a v roce 1956 jej vytáhl Joseph Kruskal. Všechny tři algoritmy jsou chamtivé a pracují v polynomiálním čase.
Dosud nejrychlejší algoritmus minimálního rozpětí stromů vyvinul Bernard Chazelle. Algoritmus je založen na měkké hromadě, přibližné prioritní frontě. Jeho doba běhu je O(m α(m,n)), kde m je počet hran, n je počet vrcholů a α je klasická funkční inverze Ackermannovy funkce. Funkce α roste extrémně pomalu, takže pro všechny praktické účely ji lze považovat za konstantu ne větší než 4; Chazellův algoritmus tedy trvá velmi blízko lineárnímu času.
Jaký je nejrychlejší možný algoritmus pro tento problém? To je jedna z nejstarších otevřených otázek v informatice. Je zřejmé, že existuje lineární dolní mez, protože musíme prozkoumat alespoň všechny váhy. Pokud jsou váhy hran celá čísla s omezenou bitovou délkou, pak jsou známy deterministické algoritmy s lineárním časem běhu. Pro obecné váhy existují randomizované algoritmy, jejichž očekávaná doba běhu je lineární.
K problému lze přistupovat i distribuovaným způsobem. Pokud je každý uzel považován za počítač a žádný uzel nezná nic jiného než své vlastní připojené spoje, lze i tak vypočítat distribuovaný minimální protahovací strom.
Otázky a odpovědi
Otázka: Co je v teorii grafů minimální rozpínací strom?
Odpověď: Minimální rozpínací strom je v teorii grafů strom, který minimalizuje celkové váhy přiřazené hranám.
Otázka: Co je to strom v teorii grafů?
Odpověď: Strom je způsob, jak v teorii grafů spojit všechny vrcholy dohromady tak, aby z kteréhokoli vrcholu vedla do kteréhokoli jiného vrcholu stromu pouze jedna cesta.
Otázka: Jaký je účel výběru cest ve scénáři teorie grafů, který představuje města?
Odpověď: Účelem výběru silnic ve scénáři teorie grafů, který představuje města, je umožnit, aby se do každého města dalo dostat z každého jiného města, ale aby neexistovala více než jedna možná cesta z jednoho města do druhého.
Otázka: Může mít graf více než jeden rozpínací strom?
Odpověď: Ano, graf může mít více než jeden rozpínací strom.
Otázka: Jaký je rozdíl mezi minimálním stromem rozpětí a jinými stromy v teorii grafů?
Odpověď: Minimální rozpínací strom minimalizuje celkové váhy připojené k hranám, zatímco ostatní stromy tuto vlastnost nemají.
Otázka: Co jsou v teorii grafů hrany?
Odpověď: Hrany jsou v teorii grafů spojení mezi dvěma vrcholy.
Otázka: Může v grafu existovat více než jeden minimální rozpínací strom s různě váženými hranami?
Odpověď: Ano, v závislosti na tom, jak graf vypadá, může existovat více než jeden minimální rozpínací strom.
