Kostra grafu

Z Wikipedie, otevřené encyklopedie

V teorii grafů je kostra grafu G takový podgraf grafu G na množině všech jeho vrcholů, který je stromem.

Obsah 1 Příklady 2 Algoritmy pro hledání kostry 2.1 Libovolná kostra 2.2 Minimální kostra 2.2.1 Kruskalův („hladový“) algoritmus 2.2.2 Jarníkův algoritmus 3 Reference

[editovat] 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).

[editovat] Algoritmy pro hledání kostry

[editovat] 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 ; 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.

[editovat] Minimální kostra

Je-li navíc definována funkce (tzv. ohodnocení hran), má smysl hledat minimální kostru – tedy takovou kostru (V,E'), že výraz

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):

[editovat] Kruskalův („hladový“) algoritmus

Podrobnější informace naleznete v článku Kruskalův algoritmusnaleznete v článcích [[{{{2}}}]] a [[{{{3}}}]]naleznete v článcích [[{{{4}}}]], [[{{{5}}}]] a [[{{{6}}}]]naleznete v článcích [[{{{7}}}]], [[{{{8}}}]], [[{{{9}}}]] a [[{{{10}}}]].

Předpokládejme navíc, že hrany jsou uspořádány tak, že platí .

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í.

[editovat] Jarníkův algoritmus

1. Nechť | V | = n a | E | = m. Položme , kde v je libovolný vrchol G.
2. Nalezneme hranu nejmenší možné váhy z množiny hran takových, že .
3. Položíme a .
4. Pokud žádná taková hrana neexistuje, algoritmus končí a T = (V_i,E_i), jinak pokračuj krokem 2.

[editovat] Reference

• Jiří Matoušek, Jaroslav Nešetřil: Kapitoly z diskrétní matematiky, nakladatelství Karolinum, Praha 2002, ISBN 80-246-0084-6