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í.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze