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\).