Jednoznačnost minimální kosty
Úloha číslo: 4092
Ukažte, že pokud je ohodnocení grafu prosté (jakožto funkce), tak je minimální kostra jednoznačná.
Řešení
Nechť \(T\) je minimální kostra a \(T’\) je libovolná jiná kostra. Zvolme \(e\) hranu nejmenší váhy z \(T’\setminus T\).
Odebráním \(e=(u,v)\) se \(T’\) rozpadne na dvě komponenty \(C\) a \(C’\). Každý konec \(e\) je v jiné z nich. Na druhou stranu, v \(T\) jsou \(u\) a \(v\) spojeny cestou, tedy nějaká hrana \(f\) této cesty spojuje \(C\) s \(C’\). Protože je \(T\) minimální a váhy jsou různé, má \(f\) menší váhu než \(e\).
Náhradou \(e\) za \(f\) v \(T’\) získáme kostru menší váhy, tedy \(T’\) není minimální.