— — Počet koster K_{n}

Počet koster K_{n}

VĚTA (Cayleyho formule):

∀n ≥ 2: počet koster grafu K_{n} je n^{n−2} (tedy počet stromů na {1, …, n}).

Příklad:

n = 2: {• \atop 1} − {• \atop 2}

2^{0} = 1 kostra. n = 3: {• \atop 1} − {• \atop 2} − {• \atop 3}, {• \atop 2} − {• \atop 1} − {• \atop 3}, {• \atop 1} − {• \atop 3} − {• \atop 2}

3^{1} = 3 kostry. n = 4: 12 koster typu housenka, 4 kostry typu vějíř.

DŮKAZ:

Slunce: Strom, v němž všechny hrany jsou zorientovány směrem od jediného vrcholu (středu slunce).

Pozorování 1:

Počet stromů na {1, …, n} je roven

\frac{počtu sluncí na \{1, …, n\}}{n}

DŮKAZ:

Každý strom odpovídá n sluncím (máme v každém stromu n možností volby středu). Q.E.D.

Sousluní: Orientovaný graf, kde každá komponenta je slunce.

Pozorování 2:

Po odstranění libovolných k hran ze slunce dostaneme sousluní s k+1 komponentami (slunci).

DŮKAZ:

Zřejmý z obrázku. Vyhozením hrany ze slunce se slunce rozpadne na 2 další slunce. Q.E.D.

Pozorování 3:

Přidáním orientované hrany do sousluní dostaneme opěr sousluní, právě když přidaná hrana vede do středu libovolné jiné komponenty (slunce).

DŮKAZ:

Z obrázku.

Důkaz věty:

Z grafu izolovaných vrcholů 1,…,n dostaneme slunce na {1, …, n} postupným přidáváním n − 1 orientovaných hran právě, když přidaná hrana vždy vede z libovolného vrcholu do středu jiné komponenty.

Máme n(n − 1) možností volby první hrany. Možností volby druhé hrany máme n(n − 2). Pro třetí hranu máme n(n − 3) možností. … Pro (n − 1). hranu máme n · 1 možností.

Celkem máme n^{n−1}(n − 1)! možností, jak zvolit 1. až (n − 1). hranu. Každé slunce dostaneme (n − 1)!-krát. Sluncí tedy dostaneme n^{n−1} a stromů tak bude n^{n−2}.

Q.E.D.

/L:1 1