Kostra grafu

Z Wikipedie, otevřené encyklopedie

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

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

Obsah

[editovat] Příklady

  • Kružnice na n vrcholech (graf Cn) má právě n různých koster.
  • Libovolný strom má jedinou kostru – sám sebe.
  • Úplný graf na n vrcholech má právě nn − 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 (e_1, e_2, \ldots, e_m); položme E0 = 0.
  2. Byla-li již nalezena množina Ei − 1, spočítáme množinu Ei takto:
    • Ei = Ei − 1 ∪ {ei}, neobsahuje-li graf (V, Ei − 1ei) kružnici,
    • Ei = Ei − 1 jinak.
  3. Algoritmus se zastaví, jestliže buď Ei již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Graf T = (V,Ei) pak představuje kostru grafu G.

[editovat] Minimální kostra

Minimální kostra grafu
Minimální kostra grafu

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 (V,E'), že výraz

w(E') = \sum_{e \in \mathit{E}'} w(e)

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í 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). 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 \mathit{E_0} = \empty\;, \mathit{V_0} = \{v\}, kde v je libovolný vrchol G.
  2. 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}.
  3. Položíme \mathit{V_i} = \mathit{V}_{i-1} \cup \{y_i\} a \mathit{E_i} = \mathit{E}_{i-1} \cup \{e_i\}.
  4. Pokud žádná taková hrana neexistuje, algoritmus končí a T = (Vi,Ei), 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
V jiných jazycích