Nastavení

Graf $T$ konstruovaný algoritmem vzniká z jednoho vrcholu postupným přidáváním listů.

Takže $T$ je v každém okamžiku výpočtu strom.

V každé iteraci se $|V(T)|$ zvětší o 1.

Dokud $V(T) \neq V(G)$, musí díky souvislosti $G$ existovat hrana mezi $V(T)$ a $V(G) \setminus V(T)$, kterou může algoritmus přidat do $T$.

To znamená, že algoritmus se zastaví, až když $V(T) = V(G)$.

Tehdy je ale $T$ kostra.

$\square$

Dokážeme obměněnou implikaci: Pokud nějaká kostra $T$ neobsahuje hranu $e$, pak není minimální.

Označme $A$ a $B$ množiny vrcholů určující elementární řez $R$.

Hrana $e = \{a, b\}$, $a \in A, b \in B$, je nejlehčí v $R$.

Nechť T je kostra neobsahující e.

Protože $T$ je strom, existuje v něm jediná cesta $P(a, b)$ a ta musí alespoň jednou překročit elementární řez $R$.

Nechť $f = \{a', b'\}$, $a' \in A$, $b' \in B$, je libovolná hrana, kde se to stalo.

Nyní z kostry $T$ odebereme hranu $f$.

Tím se kostra rozpadne na dva stromy $T_a$, $T_b$, z nichž jeden obsahuje $a$ a druhý $b$.

Přidáním hrany e stromy opět propojíme a tím získáme jinou kostru $T'$.

Platí $w(T') = w(T) − w(f) + w(e)$.

Protože $e$ je nejlehčí hrana v elementárním řezu a váhy jsou unikátní, musí platit $w(f) > w(e)$.

Proto $w(T') < w(T)$ a tudíž $T$ není minimální kostra.

$\square$

Jarníkův algoritmus v každém kroku vybere jedinečnou nejlehčí hranu elementárního řezu mezi vrcholy dosud vytvořeného stromu a zbytkem grafu, která je vždy dle lemmatu obsažena v každé minimální kostře.

To ale znamená, že kostra vytvořená Jarníkovým algoritmem je podgrafem každé minimální kostry.

Protože ale všechny kostry daného grafu mají stejný počet hran, znamená to, že vytvořená kostra je všem minimálním kostrám rovna a je tudíž unikátní.

$\square$

Jarníkův algoritmus váhy hran mezi sebou pouze porovnává.

$\square$

Označme $A$ a $B$ množiny vrcholů, kterými je určen elementární řez $R$.

Nechť $T'$ neobsahuje $e$ a nechť $e = \{a, b\}$.

Buď $P$ unikátní cesta mezi vrcholy $a$ a $b$ v $T'$.

Cesta $P$ prochází elementárním řezem $R$.

Nechť $f$ je libovolná hrana v $E(P) \cap R$.

Potom $T := T' − f + e$ je kostra a platí, že $w(T) \le w(T')$.

$\square$

Inicializace zabere $O(|V|)$.

Operace s binární haldou:

1. Provedeme $|V| − 1$ krát operaci HeapExtractMin – celkem $O(|V| \cdot log(|V|))$.

2. Každá hrana může způsobit volání operace HeapDecreaseKey – celkem $O(|E| \cdot log(|V|))$.

Dohromady dostáváme $O(|V|) + O(|V| \cdot log(|V|)) + O(|E| \cdot log(|V|)) = O(|E| \cdot log(|V|))$.

$\square$

Cyklus se vykoná m-krát.

$\square$

Ukážeme nejdříve, že pokud algoritmus přidá hranu $e = \{u, v\}$ do $T$, pak $e$ leží v minimální kostře.

Pokud algoritmus e přidá, stane se tak v okamžiku, kdy se vrcholy u a v nacházejí v nějakých dvou rozdílných stromech $T_u$ a $T_v$ lesa $T$.

Hrana $e$ přitom leží v elementárním řezu oddělujícím strom $T_u$ od zbytku grafu.

Hrana $e$ musí být nejlehčí hrana elementárního řezu oddělujícího strom $T_u$ od zbytku grafu, neboť případnou lehčí hranu by algoritmus potkal dříve a přidal by ji do $T$.

Hrana $e$ tedy leží v minimální kostře podle lemmatu o řezech.

Nyní si ukážeme, že výsledný $T$ je souvislý.

Pokud by nebyl, uvažme dva rozdílné stromy $T_u$ a $T_v$ lesa $T$ a elementární řez oddělující strom $T_u$ od zbytku grafu.

Protože je graf $G$ souvislý, je tento elementární řez neprázdný a má nějakou hranu $e$.

Když algoritmus zkoumal hranu $e$, nemohla tvořit cyklus (netvoří ho ani ve výsledném $T$), takže by ji algoritmus musel přidat, což je spor.

Výstupem algoritmu je tedy kostra, která je podgrafem minimální kostry – tedy minimální kostra.

$\square$

Indukcí podle počtu operací Union.

Na počátku algoritmu mají všechny keříky jednu hladinu a $1$ vrchol (a $1 \ge 2^{1−1} = 1$).

Nechť nyní provádíme Union ($u$, $v$) a počet hladin obou keříků je různý.

Připojením mělčího keříku pod kořen toho hlubšího se počet hladin nezmění a počet vrcholů neklesne, takže nerovnost stále platí.Pokud mají oba keříky h hladin, platí z indukčního předpokladu, že každý z nich obsahuje minimálně $2^{h−1}$ vrcholů.

Jejich sloučením tudíž vznikne keřík s $h + 1$ hladinami o alespoň $2 \cdot 2^{h−1} = 2^h$ vrcholech.

$\square$

Strom s větším počtem hladin by podle invariantu obsahoval více než $n$ vrcholů

$\square$

Algoritmus nejdříve seřadí hrany v čase $O(m \cdot \log n)$

Následně strukturu Union-Find v čase $T_i(n)$.

Při testování hran se nejvýše $2m$-krát zavolá Find ($2m \cdot T_f(n)$) a $(n − 1)$-krát se zavolá Union ($(n-1) \cdot T_u(n)$).

$\square$