\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
