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.