Grafové algoritmy – hledání minimální kostry

Primův algoritmus, Kruskalův algoritmus – principy algoritmů, složitost

Minimální kostra grafu je důležitým pojmem, využití má např. při řešení elektrických obvodů (při řešení pomocí Kirchhoffových zákonů potřebujeme sestavit dostatek lineárně nezávislých rovnic a získáme-li minimální kostru obvodu, je to poměrně jednoduché) nebo v Christofidově algoritmu pro heuristické řešení úlohy obchodního cestujícího.

Definice potřebných pojmů:

  • kostra souvislého grafu - takový faktor grafu, který je zároveň stromem
    • faktor - je takový podgraf, který obsahuje všechny vrcholy grafu
    • strom - je minimální souvislý graf s daným počtem vrcholů (neobsahuje cykly)
  • minimální kostra souvislého grafu - je kostra souvislého grafu (s ohodnocenými hranami), která má nejnižší váhu
    • váha kostry - součet vah všech hran kostry

Algoritmy pro hledání minimální kostry se nazývají hladové (greedy). To je dáno tím, že se v každém kroku snaží získat co nejvýhodnější kus (zde hranu s nejmenším ohodnocením). U spousty problémů je tento přístup horší než porovnávání mezi různými variantami (spokojit se někdy s méně výhodným kusem), avšak u hledání minimální kostry vede vždy k optimálnímu výsledku.

Primův algoritmus

V roce 1929 vylepšil Vojtěch Jarník tzv. Borůvkův algoritmus. V roce 1957 ten samý algoritmus vymyslel i Robert Prim, podle kterého je ve světě znám.

Princip

Máme souvislý graf \( G \) s \( n \) vrcholy a s nezápornými vahami hran \( w \).

  1. začneme z jednoho libovolného vrcholu.
  2. přidáme takovou hranu, která má nejmenší váhu mezi hranami, které vedou z již vytvořeného podstromu do některého z dosud nepřipojených vrcholů grafu
  3. opakujeme krok 3, dokud neprovedeme \( n - 1 \) kroků, poté algoritmus končí

Výhodné je, že nemusíme před začátkem hrany řadit a rovněž že nemusíme kontrolovat, zdali nevznikají cykly (vždy přidáváme nepřipojený vrchol), což je výpočetně náročné.

Složitost

Časová složitost algoritmu závisí na datové struktuře, která uchovává ohodnocení hran:

  • matice sousednosti - \( O(|U|^2) \)
  • binární halda a seznam sousedů - \( O(|H| \cdot \log{|U|}) \)
  • fibonacciho halda a seznam sousedů - \( O(|H| + |U| \cdot \log{|U|}) \)

\( |H| \) je počet hran a \( |U| \) počet vrcholů.

Kruskalův algoritmus

Dalším algoritmem je ten popsaný Josephem B. Kruskalem v roce 1956. Kruskal, podovně jako Jarník, vycházel z práce Otakara Borůvky.

Princip

Máme les \( F \) (množinu stromů), ve kterém je každý vrchol grafu \( G \) samostatným podstromem a množinu \( S \) obsahující všechny hrany grafu \( G \).

  1. z množiny \( S \) odebereme hranu s minimální váhou
    • pokud tato hrana spojuje dva různé podstromy (dosud nespojené), přidáme ji do lesa \( F \) = tyto podstromy sloučíme do jednoho
    • pokud ne, hranu zahodíme
  2. krok jedna opakujeme do té doby, dokud je množina \( S \) neprázdná

Po skončení obsahuje les \( F \) jediný strom - minimální kostru grafu.

Složitost

  • je \( O(|H| \cdot \log{|U|}) \), kde \( |H| \) je počet hran a \( |U| \) počet vrcholů, pokud:
    • seřadíme hrany podle vah v čase \( O(|H| \cdot \log{|H|}) \)
    • použijeme primitivnější datové struktury pro zaznamenávání příslušnosti hran k vrcholům (nevím které, ale pravděpodobně by to mohl být disjoint-set)
  • je \( O(|H| \cdot \alpha(|U|)) \), kde \( |H| \) je počet hran, \( |U| \) počet vrcholů a \( \alpha \) inverzní Ackermannova funkce, pokud:
    • máme hrany již seřazené nebo jsme schopni je seřadit v lineárním čase
    • použijeme sofistikovanější datové struktury pro zaznamenávání příslušnosti hran k vrcholům

Zdroje