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. +more * Ú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: # 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 = \emptyset. # 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. +more # 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:\mathit{E}\rightarrow\mathbb{R} (tzv. +more ohodnocení hran), má smysl hledat minimální kostru - tedy takovou kostru (\mathit{V}, \mathit{E}'), že výraz :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í 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).

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. +more 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

# Nechť |\mathit{V}| = n a |\mathit{E}| = m. Položme \mathit{E_0} = \empty\;, \mathit{V_0} = \{v\}, kde v je libovolný vrchol G. +more # 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}. # Položíme \mathit{V_i} = \mathit{V}_{i-1} \cup \{y_i\} a \mathit{E_i} = \mathit{E}_{i-1} \cup \{e_i\}. # Pokud žádná taková hrana neexistuje, algoritmus končí a 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, * Jakub Černý: [url=https://web. archive. +moreorg/web/20071018060717/http://kam. mff. cuni. cz/~kuba/ka/]Základní grafové algoritmy[/url] (texty v pdf).

Externí odkazy

[url=http://teorie-grafu. elfineer. +morecz/vybrane-problemy/minimalni-kostra. php]Kruskalův algoritmus[/url]- animace a příklady, bakalářská práce z MFF UK * [url=https://web. archive. org/web/20090120232242/http://www. zdenek-hejl. com/2009/01/link-building-maximalni-kostra-grafu. html]Maximální kostra grafu[/url] - využití algoritmu pro zjištění maximální kostry grafu pro link building.

Kategorie:Grafové pojmy