Kostra se zápornými hranami

Úloha číslo: 4130

Rozhodněte, zdali Kruskalův algoritmus bude fungovat korektně i na grafech se záporně ohodnocenými hranami, nebo zdali na některém takovém selže.

  • Řešení

    Algoritmus neselže. Pokud je \(c\) nejmenší váha, pak zvýšíme-li váhy o \(-c\), dostaneme graf s nezápornými váhami a na nich Kruskalův algoritmus neselže. Jeho průběh bude stejný jeko na originálním grafu.

    Ve skutečnosti je důležité jen uspořádání hran podle vah, nikoli konkrétní hodnoty vah.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze