Kostry grafů s málo cykly

Úloha číslo: 4082

Spočtěte kolik má různých koster cyklus na \(n\) vrcholech.

Kolik jich má činka, t.j. dva cykly délek \(m\) a \(n\) spojené cestou délky \(l\).

Kolik koster má tzv \(\Theta\)-graf, tedy dva vrcholy stupně tři spojené cestami délek \(m,n\) a \(l\).

  • Řešení

    Cykly: odebráním libovolné hrany vznikne kostra, je jich tedy \(n\). Odebráním více hran by se stal nesouvislý.

    Činky: Z každého z obou cyklů je třeba odebrat po jedné hraně. Tyto výběry jsou nezávislé, výsledných koster je \(mn\).

    \(\Theta\)-grafy: Ze dvou cest odebereme po jedné hraně, třetí cestu necháme celou, aby graf zůstal souvislý. Výsledný počet koster je \(mn+ml+nl\).

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