Minimální kostra konkrétního grafu

Úloha číslo: 4093

Určete minimální kostru grafu na obrázku:

vážený graf
  • Ř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:

    výsledná kostra

    Alternativní řešení má namísto hrany \((f,g)\) hranu \((i,j)\).

    V obou dvou případech je váha minimální kostry 69.

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