Movatterモバイル変換

[0]ホーム
URL:

Přeskočit na obsah
WikipedieWikipedie: Otevřená encyklopedie
Hledání

Kostra grafu

Z Wikipedie, otevřené encyklopedie
Kostra (červeně) grafu (černě)
Tři příklady na mřížkovém grafu 8x8

Vteorii grafů jekostra souvislého grafuG takovýpodgrafsouvislého grafuG namnožině všech jehovrcholů, který jestromem.

Příklady

[editovat |editovat zdroj]

Algoritmy pro hledání kostry

[editovat |editovat zdroj]

Libovolná kostra

[editovat |editovat zdroj]

Následující základníalgoritmus je schopen nalézt nějakou (blíže neurčenou) kostru:

  1. NechťG=(V,E){\displaystyle G=(V,E)} je graf sn vrcholy amhranami; seřaďme hrany G libovolně doposloupnosti(e1,e2,…,em){\displaystyle (e_{1},e_{2},\ldots ,e_{m})}; položmeE0=∅{\displaystyle E_{0}=\emptyset }.
  2. Byla-li již nalezenamnožinaEi−1{\displaystyle E_{i-1}}, spočítáme množinuEi{\displaystyle E_{i}} takto:
  3. Algoritmus se zastaví, jestliže buďEi{\displaystyle E_{i}} již obsahujen − 1 hran neboi = m, tedy se probraly všechny hrany zG. GrafT=(V,Ei){\displaystyle T=(V,E_{i})} pak představuje kostru grafuG.

Minimální kostra

[editovat |editovat zdroj]
Minimální kostra grafu

Je-li navíc definována funkcew:E→R{\displaystyle w:{\mathit {E}}\rightarrow \mathbb {R} } (tzv.ohodnocení hran), má smysl hledatminimální kostru – tedy takovou kostru(V,E′){\displaystyle ({\mathit {V}},{\mathit {E}}')}, že výraz

w(E′)=∑e∈E′w(e){\displaystyle 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 jakohladové, neboť jednou provedená rozhodnutí už nikdy nemění, čili „hladově“ postupují přímo k řešení.

Předpokládejme, že je dánsouvislý grafG = (V, E) s ohodnocenímw:

Kruskalův algoritmus

[editovat |editovat zdroj]
Podrobnější informace naleznete v článku Kruskalův algoritmus.

Předpokládejme navíc, že hrany jsou uspořádány tak, že platíw(e1)≤w(e2)≤…≤w(em){\displaystyle w(e_{1})\leq w(e_{2})\leq \ldots \leq w(e_{m})}.

Pro toto uspořádání provedeme algoritmus pro hledání libovolné kostry (viz výše).

Borůvkův algoritmus

[editovat |editovat zdroj]
Podrobnější informace naleznete v článku 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

[editovat |editovat zdroj]
Podrobnější informace naleznete v článku Jarníkův algoritmus.
  1. Nechť|V|=n{\displaystyle |{\mathit {V}}|=n} a|E|=m{\displaystyle |{\mathit {E}}|=m}. PoložmeE0=∅,V0={v}{\displaystyle {\mathit {E_{0}}}=\emptyset \;,{\mathit {V_{0}}}=\{v\}}, kdev je libovolný vrcholG.
  2. Nalezneme hranuei={xi,yi}∈E(G){\displaystyle e_{i}=\{x_{i},y_{i}\}\in {\mathit {E(G)}}} nejmenší možné váhy z množiny hran takových, žexi∈Vi−1,yi∈V∖Vi−1{\displaystyle x_{i}\in {\mathit {V}}_{i-1},y_{i}\in {\mathit {V}}\setminus {\mathit {V}}_{i-1}}.
  3. PoložímeVi=Vi−1∪{yi}{\displaystyle {\mathit {V_{i}}}={\mathit {V}}_{i-1}\cup \{y_{i}\}} aEi=Ei−1∪{ei}{\displaystyle {\mathit {E_{i}}}={\mathit {E}}_{i-1}\cup \{e_{i}\}}.
  4. Pokud žádná taková hrana neexistuje, algoritmus končí aT=(Vi,Ei){\displaystyle 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řilBernard Chazelle modifikací Borůvkova algoritmu.Asymptotická časová složitost tohoto algoritmu je O(E α(V)), kde α je inverzníAckermannova funkce.

Literatura

[editovat |editovat zdroj]

Externí odkazy

[editovat |editovat zdroj]
Autoritní dataEditovat na Wikidatech
Citováno z „https://cs.wikipedia.org/w/index.php?title=Kostra_grafu&oldid=24107831“
Kategorie:
Skryté kategorie:
[8]ページ先頭
©2009-2025 Movatter.jp