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.

Příklady

• Kružnice na n vrcholech (graf ${\displaystyle 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ě ${\displaystyle 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ť ${\displaystyle G=(V,E)}$ je graf s n vrcholy a m hranami; seřaďme hrany G libovolně do posloupnosti ${\displaystyle (e_{1},e_{2},\ldots ,e_{m})}$; položme ${\displaystyle E_{0}=\emptyset }$.
2. Byla-li již nalezena množina ${\displaystyle E_{i-1}}$, spočítáme množinu ${\displaystyle E_{i}}$ takto:
   • ${\displaystyle E_{i}=E_{i-1}}$ ∪ {${\displaystyle e_{i}}$}, neobsahuje-li graf (V, ${\displaystyle E_{i-1}}$ ∪ ${\displaystyle {e_{i}}}$) kružnici,
   • ${\displaystyle E_{i}=E_{i-1}}$ jinak.
3. Algoritmus se zastaví, jestliže buď ${\displaystyle E_{i}}$ již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Graf ${\displaystyle T=(V,E_{i})}$ pak představuje kostru grafu G.

Minimální kostra

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

${\displaystyle w(E')=\sum _{e\in {\mathit {E}}'}w(e)}$

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

Předpokládejme navíc, že hrany jsou uspořádány tak, že platí ${\displaystyle w(e_{1})\leq w(e_{2})\leq \ldots \leq w(e_{m})}$.

Pro toto uspořádání provedeme algoritmus pro hledání libovolné kostry (viz výše).

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

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

Literatura

• 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

• Obrá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