Foreground plně podporuje – RWD, HTML 5.0, Super Galerii a YouTube 2.0 !
Kostra grafu
Z Multimediaexpo.cz
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.
Obsah |
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:
- 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.
- 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
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 \((\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
- Podrobnější informace naleznete na stránce: 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
- Podrobnější informace naleznete na stránce: 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
- Podrobnější informace naleznete na stránce: Jarníkův algoritmus
- Nechť \(|\mathit{V}| = n\) a \(|\mathit{E}| = m\). Položme \(\mathit{E_0} = \emptyset \;, \mathit{V_0} = \{v\}\), kde v je libovolný vrchol G.
- 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, ISBN: 80-246-0084-6
- Jakub Černý: Základní grafové algoritmy (PDF texty)
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
|
| Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010 |
|---|
| Informace o článku.
Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. |