Motivace (prohrnování silnic): V království je $N$ měst a některá z nich jsou spojena přímou silnicí. Křižovatky jsou pouze ve městech. Mezi některými městy přímá silnice nevede, ale z každého města se dá po silnicích dostat do libovolného jiného. V noci se přihnala se pohádková vánice a zasněžila všechny silnice v celém království. Napadlo až metr sněhu. Odhrabovačů je málo a takovou sněhovou nadílku budou odklízet ještě hodně dlouho. Rozhodněte, které silnice se mají odhrabat jako první, aby mezi každýma dvěma městy vedla sjízdná silnice.
Motivace (elektrifikace): Vysoko v tibetských horách se rozhodli začít využívat výhod moderního světa1 a chtějí provést elektrifikaci všech $N$ vesnic krásného údolí. Dráty se nesmí větvit jinde než ve vesnici. Znají vzdálenost mezi každýma dvěma vesnicemi, ale nevědí, jak natahat dráty elektrického vedení, aby jich spotřebovali co nejméně. Poradíte jim? Větší množství drátů než je nejmenší možné jim rada starších pro ochranu životního prostředí nepovolí.
Úkol (grafový pohled): Je dán neorientovaný graf $G=(V,E)$ s ohodnocením hran $c:E\to\RR$. Najděte kostru $T\subseteq G$ s nejmenším ohodnocením hran, tj. s nejmenším $\sum_{e\in T} c(e)$. Výstupem bude množina hran $M=E(T)$ tvořících kostru.

Místo ohodnocení hrany $c(e)$ často používáme pojem cena hrany. Nejdražší, respektive nejlevnější hrana je ta s největším, respektive nejmenším ohodnocením.2

Připomeňte si (viz kapitola o grafech a stromech), že strom $T$ je souvislý graf bez kružnic. Strom na všech vrcholech je také minimální souvislý podgraf (přidáním libovolné hrany k $T$ vznikne kružnice). Mezi libovolnýma dvěma vrcholy stromu $T$ vede jednoznačně určená cesta. Jednoznačnou cestu z vrcholu $x$ do vrcholu $y$ ve stromě $T$ značíme $xTy$. Kostra grafu $G$ je strom $T\subseteq G$ na všech $n$ vrcholech. Také si připomeňte operace přidání a odebrání hrany z grafu $G$. Výsledky těchto operací značíme $G+e$, $G-e$.

Pro jednoduchost nebudeme v následujícím textu rozlišovat mezi množinou hran $M\subseteq E$ a podgrafem $G$ obsahujícím právě hrany $M$. Řez určený množinou $A\subseteq V$ je množina hran $\delta(A)=\{ uv\in E \,|\, u\in A \;\&\;v\not\in A\}$. Každá cesta z $u\in A$ do $v\not\in A$ prochází přes řez $\delta(A)$ (obsahuje hranu řezu). Platí, že graf je nesouvislý právě tehdy, když existuje řez $\delta(C)=\emptyset$ pro $\emptyset\not= C \subset V$.

Kostru v souvislém grafu najdeme jednoduše pomocí průchodu grafu do hloubky, protože DFS strom souvislého grafu je kostra. To dokazuje, že každý souvislý graf má alespoň jednu kostru. Taková kostra ovšem ještě nemusí být minimální, při hledání minimální kostry musíme postupovat malinko chytřeji. Pokud v zadání dostaneme nesouvislý graf, tak chceme najít řez $\delta(C)=\emptyset$ pro $C\not=\emptyset$, který je důkazem, že graf je nesouvislý a tedy že v grafu žádná kostra neexistuje. Stačí vzít řez určený jednou komponentou souvislosti.

Pozorování (o prohazování hran): Přidáním hrany $e$ do kostry $T$ vznikne právě jedna kružnice $C$. Vyhodíme-li z kružnice $C$ libovolnou hranu $f$, dostaneme graf $T+e-f$, který je opět kostrou. Pokud $c(e) < c(f)$, tak bude mít nová kostra menší cenu.

Podobných pozorování využijeme v následujících algoritmech. Nejprve si ukážeme meta-algoritmus a z něj pak snadno odvodíme ostatní algoritmy pro hledání minimální kostry.

Přehled algoritmů pro minimální kostru

Kruskalův hladový $\OO(m \log n)$
Kruskalův hladový (setříděné hrany) $\OO((n+m)\alpha(n))$
Jarníkův, Primův (pole) $\OO(n^2+m)$
Jarníkův, Primův (halda) $\OO((n+m)\log n)$
Borůvkův $\OO(m \log n)$

Asymptotické časové složitosti algoritmů pro nalezení minimální kostry se téměř neliší. Odhady můžeme zlepšit ve speciálních případech, kdy dostaneme dodatečná omezení na vstupní graf (více uvidíte v příkladech na konci kapitoly).

Nejrychlejší algoritmus na minimální kostru pochází od Chazelle [Chazelle2000:MST], který s využitím SoftHeaps navrhnul algoritmus s časovou složitost $\OO((n+m)\alpha(n))$. Pettie, Ramachandran [Pettie2002:MST] navrhli algoritmus, který už je optimální. Jen se dosud nepodařilo vyčíslit jeho časovou složitost. Je to někde mezi $\OO(m)$ a $\OO(m\alpha(n))$ (což už je prakticky jen multiplikativní konstanta).

Chong, Han, Lam [Chong2001:MST] ukázali paralelní algoritmus s časovou složitostí $\OO(\log n)$.

Hezky sepsaný přehled všech možných algoritmů týkajících se minimálních koster najdete v dizertační práci Martina Mareše [MaresSaga].