Otevřít hlavní menu

PříkladyEditovat

  • Kružnice na n vrcholech (graf  ) má právě n různých koster.
  • Libovolný strom má jedinou kostru – sám sebe.
  • Úplný graf na n vrcholech má právě   různých koster (tzv. Cayleyho vzorec).

Algoritmy pro hledání kostryEditovat

Libovolná kostraEditovat

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

  1. Nechť   je graf s n vrcholy a m hranami; seřaďme hrany G libovolně do posloupnosti  ; položme  .
  2. Byla-li již nalezena množina  , spočítáme množinu   takto:
    •   ∪ { }, neobsahuje-li graf (V,   ) kružnici,
    •   jinak.
  3. Algoritmus se zastaví, jestliže buď   již obsahuje n − 1 hran nebo i = m, tedy se probraly všechny hrany z G. Graf   pak představuje kostru grafu G.

Minimální kostraEditovat

 
Minimální kostra grafu

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

 

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 algoritmusEditovat

Podrobnější informace naleznete v článku Kruskalův algoritmus.

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

Borůvkův algoritmusEditovat

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 algoritmusEditovat

Podrobnější informace naleznete v článku Jarníkův algoritmus.
  1. Nechť   a  . 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  , 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.

ReferenceEditovat

Externí odkazyEditovat