\input /home/pasky/school/fastex/lib.tex

\subchapter{Počet koster $K_n$}{

	\theorem{}{Cayleyho formule}{
		$\forall n \ge 2$: počet koster grafu $K_n$ je $n^{n-2}$
		(tedy počet stromů na $\{1,\ldots,n\}$).

		\example{
			$n=2$:
				${\bullet\atop1}-{\bullet\atop2}$

				\qquad$2^0 = 1$ kostra.

			$n=3$:
				${\bullet\atop1}-{\bullet\atop2}-{\bullet\atop3}$,
				${\bullet\atop2}-{\bullet\atop1}-{\bullet\atop3}$,
				${\bullet\atop1}-{\bullet\atop3}-{\bullet\atop2}$

				\qquad$3^1 = 3$ kostry.

			$n=4$:
				12 koster typu housenka, 4 kostry typu vějíř.
		}

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

			\scpart{Pozorování 1:}{
				Počet stromů na $\{1,\ldots,n\}$ je roven
				$$\textbox{počtu sluncí na $\{1,\ldots,n\}$}\over n$$

				\proof{
					Každý strom odpovídá $n$ sluncím
					(máme v každém stromu $n$ možností volby středu).
					\sqed
				}
			}

			\shortdef{Sousluní}{Orientovaný graf, kde každá komponenta je slunce.}

			\scpart{Pozorování 2:}{
				Po odstranění libovolných $k$ hran ze slunce dostaneme
				sousluní s $k+1$ komponentami (slunci).

				\proof{
					Zřejmý z obrázku. Vyhozením hrany ze slunce se slunce
					rozpadne na 2 další slunce. \sqed
				}
			}

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

				\proof{
					Z obrázku.
				}
			}

			\scpart{Důkaz věty:}{
				Z grafu izolovaných vrcholů 1,\dots,$n$ dostaneme
				slunce na $\{1,\ldots,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í. \dots\ Pro $(n-1)$. hranu
				máme $n\cdot1$ 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}$.

				\qed
			}
		}
	}

}

\bend