Minimální kostra konkrétního grafu
Úloha číslo: 4093
Určete minimální kostru grafu na obrázku:
Řešení
Hrany utřídíme podle vah vzestupně. Hrany stejných vah uspořádáme mezi sebou libovolně, což však může vést k jinému řešení. Jedna z možných posloupností začíná hranami \((g,j)\) - 1, \((g,k)\) - 2, \((j,k)\) - 3, \((a,f)\) - 3, …
Podle této posloupnosti vybíráme hrany do kostry a to za podmínky, že s dříve vybranými hranami nevytvoří cyklus. Tedy první hrana, která nebude vybrána do kostry je hrana \((j,k)\), protože by s dříve vybranými hranami \((g,j)\) a \((g,k)\) vytvořila cyklus na vrcholech \(g,j,k\) .
Takto postupujeme dokud vybrané hrany nevytvoří souvislý graf – kostru.
Odpověď
Jedna ze dvou možných minimálních koster je vyznačena zeleně na obrázku:
Alternativní řešení má namísto hrany \((f,g)\) hranu \((i,j)\).
V obou dvou případech je váha minimální kostry 69.
