Kostra grafu

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

Tři příklady na mřížkovém grafu 8x8

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,\dots ,e_m)$; položme $E_0=\mathrm{\varnothing }$.
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

Minimální kostra grafu

Je-li navíc definována funkce $w:𝐸\to ℝ$ (tzv. ohodnocení hran), má smysl hledat minimální kostru – tedy takovou kostru $(𝑉,{𝐸}^{\prime })$, že výraz

$w(E^{\prime })=\sum _{e\in {𝐸}^{\prime }}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

Šablona:Podrobně Předpokládejme navíc, že hrany jsou uspořádány tak, že platí $w(e_1)\le w(e_2)\le \dots \le 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ť $|𝑉|=n$ a $|𝐸|=m$. Položme ${𝐸}_0=\mathrm{\varnothing },{𝑉}_0=\{v\}$, kde v je libovolný vrchol G.
2. Nalezneme hranu $e_i=\{x_i,y_i\}\in 𝐸\mathit{(}𝐺\mathit{)}$ nejmenší možné váhy z množiny hran takových, že $x_i\in {𝑉}_{i-1},y_i\in 𝑉\setminus {𝑉}_{i-1}$.
3. Položíme ${𝑉}_{𝑖}={𝑉}_{i-1}\cup \{y_i\}$ a ${𝐸}_{𝑖}={𝐸}_{i-1}\cup \{e_i\}$.
4. Pokud žádná taková hrana neexistuje, algoritmus končí a $T=({𝑉}_{𝑖},{𝐸}_{𝑖})$, 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, Šablona:ISBN
• Jakub Černý: Základní grafové algoritmy (texty v pdf)

Externí odkazy

• Šablona:Commonscat
• 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