Některé algoritmy pro hledání minimální kostry fungují pouze na grafech, ve kterých je minimální kostra určena jednoznačně. Nemůžeme se tohoto předpokladu nějak zbavit, aby dané algoritmy fungovaly na všech grafech? Ano můžeme. Vysvětlíme si jak.


Který krok není jednoznačný?

Podívejme se na průběh meta-algoritmu. Do budované kostry postupně přidáváme nejlevnější hranu každého řezu. Bohužel se ale může stát, že je těch nejlevnějších hran více (například v grafu, kde mají všechny hrany stejné ohodnocení). Máme možnost volby. Rozhodnutí se pro jednu nejlevnější hranu může zamezit přidání ostatních nejlevnějších hran. Pro každou volbu můžeme dostat jinou minimální kostru.


Příklad: (minimální kostra v kružnici $C_n$ s konstantním ohodnocením hran) Pro libovolnou hranu $e\in C_n$ existuje minimální kostra, která $e$ obsahuje, ale i minimální kostra, která $e$ neobsahuje. Zkuste hledat minimální kostru $C_n$ meta-algoritmem. Prozkoumejte, kolik hran z nalezených řezů bude nakonec patřit do minimální kostry.

Lemma (o nejlevnější hraně řezu): Nechť $G$ je souvislý graf a $\delta(A)$ libovolný řez. Pokud je nejlevnější hrana $e$ řezu $\delta(A)$ určena jednoznačně, tak $e$ patří do minimální kostry.
Důkaz: Důkaz tohoto lemmatu je téměř shodný s důkazem lemmatu o nejlevnější hraně řezu pro meta algoritmus.

Graf $G$ je souvislý, takže má minimální kostru $T$. Pokud $e\in T$, tak jsme hotovi. Podívejme se na opačný případ a předpokládejme pro spor, že $e\not\in T$. Nechť $e=uv$. Přidáním $e$ do $T$ vznikne kružnice, která je tvořena hranou $uv$ a cestou $uTv$. Vrchol $u\in A$ a $v\not\in A$ a proto na cestě $uTv$ existuje hrana $f\in \delta(A)$. Protože $e$ je nejlevnější hrana řezu $\delta(A)$, tak $c(e)\lt c(f)$. Graf $T‘ := T-f+e$ je opět kostra. Navíc $c(T‘)=c(T)-c(f)+c(e)\lt c(T)$. To je spor s minimalitou kostry $T$.

Výhoda této verze lemmatu „o nejlevnější hraně řezu“ je, že nepotřebuje pojem rozšířitelnosti do minimální kostry.
Pokud mají všechny hrany v grafu různá ohodnocení, tak v každém řezu existuje právě jedna nejlevnější hrana. Potom je postup meta-algoritmu určen jednoznačně.

Lemma (jednoznačnost minimální kostry): Pokud mají všechny hrany v grafu $G$ různá ohodnocení, tak je minimální kostra určena jednoznačně.

Zkuste si toto lemma o jednoznačnosti minimální kostry dokázat. S využitím lemmatu „o nejlevnější hraně řezu“ je to lehké cvičení.

Jak si zajistit jednoznačnost?

Podle lemmatu „o jednoznačnosti minimální kostry“ víme, že když mají všechny hrany v grafu různá ohodnocení, tak už je minimální kostra určena jednoznačně. Proto si uspořádání na hranách podle ohodnocení rozšíříme do lineálního uspořádání1 tím, že každé hraně přidáme jednoznačné ohodnocení $c_2(e)$. Hrany budou ohodnoceny dvojicí $(c(e), c_2(e))$. Hrany budeme porovnávat lexikograficky—nejprve podle původního ohodnocení a pokud se hodnoty obou hran shodují, tak podle druhého pomocného uspořádání.

Jaké lineární uspořádání na hranách můžeme zvolit jako pomocné? První možností je jednoznačné očíslování hran (například indexem pole, ve kterém jsou uloženy). Druhou možností je, že máme vrcholy očíslovány čísly $1$ až $n$. Potom porovnáme hrany $e=xy$, $f=uv$ lexikograficky. Předpokládejme, že jsme si hrany označili tak, že $x\lt y$ a $u\lt v$. Platí $e \lt_{LEX} f$ právě tehdy když $x\lt u$ nebo když $x=u$ a $y\lt v$.