Počet koster bipartitního grafu
Úloha číslo: 4538
Kolik má graf \(K_{2,n}\) různých koster? Kolik z nich je neizomorfních?
Řešení
Označme vrcholy menší části \(u,v\). Ty musejí být spojené cestou, tu lze volit \(n\) způsoby. Každý ze zbylých \(n-1\) vrcholů lze spojit s \(u\) nebo s \(v\), což dává celkem \(n2^{n-1}\) možností.
Neizomorfní kostry se liší jen rozdělením \(n-1\) vrcholů na dvě skupiny. Těch je \(\lfloor\frac{n}2\rfloor\).
Odpověď
Všech koster je \(n2^{n-1}\), neizomorfních jen \(\lfloor\frac{n}2\rfloor\).
