Kostra grafu

Kostra (červeně) grafu (černě)

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.

Příklady

• Kružnice na n vrcholech (graf C_n) má právě n různých koster.
• Libovolný strom má jedinou kostru – sám sebe.
• Úplný graf na n vrcholech má právě n^{n − 2} různých koster (tzv. Cayleyho vzorec).

Algoritmy pro hledání kostry

Libovolná kostra

Následující základní algoritmus je schopen nalézt nějakou (blíže neurčenou) kostru:

1. Nechť G = (V,E) je graf s n vrcholy a m hranami; seřaďme hrany G libovolně do posloupnosti $(e_1, e_2, \ldots, e_m)$; položme E₀ = 0.
2. Byla-li již nalezena množina E_{i − 1}, spočítáme množinu E_i takto:
   • E_i = E_{i − 1} ∪ {e_i}, neobsahuje-li graf (V, E_{i − 1} ∪ e_i) kružnici,
   • E_i = E_{i − 1} jinak.
3. Algoritmus se zastaví, jestliže buď E_i již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Graf T = (V,E_i) pak představuje kostru grafu G.

Minimální kostra

Algoritmy hledající minimální kostru grafu Jarníkův algoritmus Borůvkův algoritmus Kruskalův algoritmus

Minimální kostra grafu

Je-li navíc definována funkce $w:\mathit{E}\rightarrow\mathbb{R}$ (tzv. ohodnocení hran), má smysl hledat minimální kostru – tedy takovou kostru (V,E'), že výraz

$w(E') = \sum_{e \in \mathit{E}'} w(e)$

nabývá minimální hodnoty.

Tuto úlohu řeší několik algoritmů (předpokládejme, že je dán souvislý graf G = (V, E) s ohodnocením w):

Kruskalův („hladový“) algoritmus

Související informace naleznete v článku Kruskalův algoritmus.

Předpokládejme navíc, že hrany jsou uspořádány tak, že platí $w(e_1) \le w(e_2) \le \ldots \le w(e_m)$.

Pro toto uspořádání provedeme algoritmus pro hledání libovolné kostry (viz výše). Algoritmus se označuje jako hladový, neboť jednou dosažená rozhodnutí už nikdy nezmění, „hladově“ postupuje přímo k řešení.

Borůvkův algoritmus

Související informace naleznete v článku Borůvkův algoritmus.

Př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

Související informace naleznete v článku Jarníkův algoritmus.

1. Nechť | V | = n a | E | = m. Položme $\mathit{E_0} = \empty\;, \mathit{V_0} = \{v\}$, kde v je libovolný vrchol G.
2. Nalezneme hranu $e_i = \{x_i, y_i\} \in \mathit{E(G)}$ nejmenší možné váhy z množiny hran takových, že $x_i \in \mathit{V}_{i-1}, y_i \in \mathit{V} \setminus \mathit{V}_{i-1}$.
3. Položíme $\mathit{V_i} = \mathit{V}_{i-1} \cup \{y_i\}$ a $\mathit{E_i} = \mathit{E}_{i-1} \cup \{e_i\}$.
4. Pokud žádná taková hrana neexistuje, algoritmus končí a T = (V_i,E_i), 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.

Reference

• 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

• 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