Kostra grafu
V teorii grafů je kostra souvislého grafu G takový podgraf souvislého grafu G na množině všech jeho vrcholů, který je stromem.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Spanning_tree.svg/220px-Spanning_tree.svg.png)
Příklady
editovat- Kružnice na n vrcholech (graf
) má právě n různých koster.
- Libovolný strom má jedinou kostru – sám sebe.
- Úplný graf na n vrcholech má právě
různých koster (tzv. Cayleyho vzorec).
Algoritmy pro hledání kostry
editovatLibovolná kostra
editovatNásledující základní algoritmus je schopen nalézt nějakou (blíže neurčenou) kostru:
- Nechť
je graf s n vrcholy a m hranami; seřaďme hrany G libovolně do posloupnosti
; položme
.
- Byla-li již nalezena množina
, spočítáme množinu
takto:
∪ {
}, neobsahuje-li graf (V,
∪
) kružnici,
jinak.
- Algoritmus se zastaví, jestliže buď
již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Graf
pak představuje kostru grafu G.
Minimální kostra
editovat![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/220px-Minimum_spanning_tree.svg.png)
Je-li navíc definována funkce (tzv. ohodnocení hran), má smysl hledat minimální kostru – tedy takovou kostru
, že výraz
nabývá minimální hodnoty.
Tuto úlohu řeší několik algoritmů, které jsou označovány jako hladové, neboť jednou provedená rozhodnutí už nikdy nemění, čili „hladově“ postupují přímo k řešení.
Předpokládejme, že je dán souvislý graf G = (V, E) s ohodnocením w:
Kruskalův algoritmus
editovatPředpokládejme navíc, že hrany jsou uspořádány tak, že platí .
Pro toto uspořádání provedeme algoritmus pro hledání libovolné kostry (viz výše).
Borůvkův algoritmus
editovatPředpokládejme, že ohodnocení hran v grafu je prosté. Algoritmus pracuje ve fázích tak, že postupně spojuje komponenty souvislosti (na počátku je každý vrchol komponentou souvislosti) do větších a větších celků, až zůstane jen jediný, a to je hledaná minimální kostra. V každé fázi vybere pro každou komponentu souvislosti hranu s co nejnižší cenou, která směřuje do jiné komponenty souvislosti a tu přidá do kostry.
Jarníkův algoritmus
editovat- Nechť
a
. Položme
, kde v je libovolný vrchol G.
- Nalezneme hranu
nejmenší možné váhy z množiny hran takových, že
.
- Položíme
a
.
- Pokud žádná taková hrana neexistuje, algoritmus končí a
, jinak pokračuj krokem 2.
Nejrychlejší známý deterministický algoritmus pro hledání minimální kostry grafu vytvořil Bernard Chazelle modifikací Borůvkova algoritmu. Asymptotická časová složitost tohoto algoritmu je O(E α(V)), kde α je inverzní Ackermannova funkce.
Literatura
editovat- Jiří Matoušek, Jaroslav Nešetřil: Kapitoly z diskrétní matematiky, nakladatelství Karolinum, Praha 2002, ISBN 80-246-0084-6
- Jakub Černý: Základní grafové algoritmy (texty v pdf)
Externí odkazy
editovatObrázky, zvuky či videa k tématu kostra grafu na Wikimedia Commons
- Kruskalův algoritmus- animace a příklady, bakalářská práce z MFF UK
- Maximální kostra grafu – využití algoritmu pro zjištění maximální kostry grafu pro link building