Verze z 15. 1. 2012, 12:51

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Stromy}
 
\begin{defn}
Graf, který neobsahuje kružnice, nazýváme \textbf{les} (angl. \emph{forest}).
Souvislý les nazýváme \textbf{strom} (angl. \emph{tree}).
\end{defn}
\begin{rem*}
Každý les je bipartitní graf.
\end{rem*}
\begin{obs}
Graf $G=(V,E)$ je strom právě tehdy, když pro každé $u,v\in V,u\neq v$
existuje právě jedna cesta z $u$ do $v$.
\end{obs}
\begin{proof}
$\boxed{{\Rightarrow:}}$
 
$G$ je strom $\Rightarrow$ $G$ je souvislý $\Rightarrow$ pro každé
dva různé vrcholy $u,v$ existuje cesta z $u$ do $v$. Dále postupujme
sporem: nechť existují $2$ různé cesty z $u$ do $v$. Potom najdeme
první vrchol ve směru od $u$, kde se obě cesty rozdělí, a dále najdeme
první vrchol, kde se opět spojí. Úseky obou cest mezi nalezenými vrcholy
tvoří zřejmě kružnici, což je spor.
 
$\boxed{{\Leftarrow:}}$
 
Mezi každými dvěma vrcholy vede právě $1$ cesta $\Rightarrow$ $G$
je souvislý. Nyní opět sporem: nechť v $G$ existuje kružnice. Vezmeme-li
libovolné dva vrcholy z této kružnice, je zřejmé, že mezi nimi existují
dvě různé cesty.
\end{proof}
\begin{thm}
Nechť $G=(V,E)$ je souvislý, $n=\# V$. Potom $G$ je strom, právě
když $\# E=n-1$.
\end{thm}
\begin{proof}
Při důkazech obou směrů ekvivalence postupujme indukcí podle $n$:
 
$\boxed{{\Rightarrow:}}$
 
Nechť $G$ je strom.
 
Pro $n=1$ máme zřejmě $E=\emptyset$, takže $\# E=0=1-1$.
 
Indukční krok: Nechť $G$ je strom na $n$ vrcholech, $e=\{ u,v\}\in E$
jeho libovolná hrana. Sestrojíme graf $\tilde{G}=(V,E\backslash e)$.
Potom $\tilde{G}$ je les, neboť určitě není souvislý: mezi každými
dvěma vrcholy existovala totiž jediná cesta, tudíž i mezi $u$ a $v$
existovala cesta jen po hraně $e$. Počet komponent grafu $\tilde{G}$
je $2$, kdyby to bylo více, nemohli bychom vrácením jedné hrany $e$
získat souvislý graf. Tyto komponenty jsou tedy stromy, nechť mají
počty vrcholů $k$ a $n-k$. Potom mají počty hran $k-1$ a $n-k-1$
, a po přidání hrany $e$ do $\tilde{G}$ získáme zpět graf $G$,
jenž má počet hran $(k-1)+(n-k-1)+1=n-1$.
 
$\boxed{{\Leftarrow:}}$
 
Nechť $\# E=n-1$. Platí $\sum_{i\in V}d(i)=2\# E=2(n-1)$, a $G$
je souvislý, tudíž $d(i)\geq1$ pro každý $i\in V$. Proto existuje
vrchol $i$ takový, že $d(i)=1$. Sestrojíme graf $\tilde{G}=(V\backslash i,E\backslash\{ i,x\})$,
kde $x$ je vrchol, do nějž vede jediná hrana z $i$. Potom je $\tilde{G}$
stále souvislý (žádná cesta mezi dvěma vrcholy $u,v$ ($u\neq i,v\neq i)$
samozřejmě nevedla přes $i$), a tudíž z indukčního předpokladu je
to strom, jenž má $n-1$ vrcholů a $n-2$ hran. Přidáme-li zpětně
vrchol $i$ a hranu $\{ i,x\}$ do $\tilde{G}$, kružnici nevytvoříme,
a tedy vznikne strom na $n$ vrcholech s $n-1$ hranami.
\end{proof}
\begin{thm}
\label{thm:pocet_stromu}Nechť $n\geq2$. Potom existuje $n^{n-2}$
stromů na $n$ vrcholech.
\end{thm}
Než tuto větu dokážeme, vyslovíme a dokážeme následující lemma:
 
\begin{lem}
Nechť $(d_{1},...,d_{n})$ jsou přirozená čísla taková, že $\sum d_{i}=2(n-1)$.
Potom existuje \[
N_{(d_{1},...,d_{n})}=\frac{(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots(d_{n}-1)!}\]
stromů na $n$ vrcholech $\{1,...,n\}$ takových, že $\forall i\in\hat{n}$
je $d(i)=d_{i}$.
\end{lem}
\begin{proof}
Podmínka $\sum d_{i}=2(n-1)$ je nutná pro to, aby $(d_{1},...,d_{n})$
bylo skóre. Dále důkaz vedeme indukcí podle $n$:
 
Pro $n=2$ je $d_{1}=d_{2}=1$ a vztah platí zřejmě.
 
Indukční krok $n-1\to n$: Ze stejného důvodu jako v minulém důkazu
existuje $k$ tak, že $d_{k}=1$. Bez újmy na obecnosti (,,BÚNO{}``)
předpokládejme, že $d_{n}=1$ a mějme tedy graf se skóre $(d_{1},...,d_{n-1},1)$.
Ubereme-li nyní $n$-tý vrchol, z něhož jediná hrana vedla do vrcholu
$i$ (kde nutně $d_{i}\geq2$), získáme graf na $n-1$ vrcholech se
skóre $(d_{1},...,d_{i}-1,...,d_{n-1})$. Ke každému stromu na $n$
vrcholech se skóre $(d_{1},...,d_{n-1},1)$ tedy existuje $i\geq2$
tak, že se tento strom skládá ze stromu na $n-1$ vrcholech se skóre
$(d_{1},...,d_{i}-1,...,d_{n-1})$, z vrcholu $n$ a z hrany $\{ i,n\}$.
Počet stromů na $n-1$ vcholech s uvedeným skóre ale umíme spočítat
dle indukčního předpokladu. Proto platí:\[
N_{(d_{1},...,d_{n})}=\sum_{\begin{matrix}{\scriptstyle i=1}\\
{\scriptstyle d_{i}\geq2}\end{matrix}}^{n-1}N_{(d_{1},...,d_{i}-1,...,d_{n-1})}=\sum_{\begin{matrix}{\scriptstyle i=1}\\
{\scriptstyle d_{i}\geq2}\end{matrix}}^{n-1}\frac{(n-3)!}{(d_{1}-1)!\cdots(d_{i}-2)!\cdots(d_{n}-1)!}=\]
...rozšíříme $(d_{i}-1)$ a díky tomu můžeme sčítat již přes všechna
$i$...\[
=\sum_{i=1}^{n-1}\frac{(d_{i}-1)(n-3)!}{(d_{1}-1)!\cdots(d_{i}-1)!\cdots(d_{n}-1)!}=\frac{(n-3)!\overbrace{\sum\limits _{i=1}^{n-1}(d_{i}-1)}^{\left(\left(\sum_{1}^{n}d_{i}\right)-1\right)-(n-1)=2(n-1)-1-(n-1)=n-2}}{\underbrace{0!}_{(d_{n}-1)!}\prod\limits _{k=1}^{n-1}(d_{k}-1)!}=\]
\[
=\frac{(n-2)!}{\prod\limits _{k=1}^{n}(d_{k}-1)!}\]
 
\end{proof}
Nyní můžeme provést důkaz věty \ref{thm:pocet_stromu}:
 
\begin{proof}
Označme si \[
\left(\forall i\in\hat{n}\right)\left(\alpha_{i}=d_{i}-1\right).\]
Počet stromů na $n$ vrcholech je roven\[
N=\sum_{\begin{matrix}{\scriptstyle \left(\forall i\in\hat{n}\right)\left(d_{i}\geq1\right)}\\
{\scriptstyle \sum d_{i}=2(n-1)}\end{matrix}}N_{(d_{1},...,d_{n})}=\sum_{\begin{matrix}{\scriptstyle \left(\forall i\in\hat{n}\right)\left(d_{i}\geq1\right)}\\
{\scriptstyle \sum d_{i}=2(n-1)}\end{matrix}}\frac{(n-2)!}{\prod\limits _{k=1}^{n}(d_{k}-1)!}=\]
\[
=\sum_{\begin{matrix}{\scriptstyle \left(\forall i\in\hat{n}\right)\left(\alpha_{i}\geq0\right)}\\
{\scriptstyle \sum\alpha_{i}=n-2}\end{matrix}}\frac{(n-2)!}{\prod\limits _{k=1}^{n}\alpha_{k}!}=n^{n-2}.\]
 
\end{proof}
\begin{rem*}
Poslední rovnost je aplikací zobecněné binomické věty, tzv. ,,$k$-nomické
věty{}``, kterou lze celkem snadno dokázat indukcí použitím ,,standardní{}``
binomické věty. Jedná se o vztah\[
\sum_{\begin{matrix}{\scriptstyle \left(\forall i\in\hat{k}\right)\left(\alpha_{i}\geq0\right)}\\
{\scriptstyle \sum\alpha_{i}=n}\end{matrix}}\frac{n!}{\prod\limits _{j=1}^{n}\alpha_{j}!}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{k}^{\alpha_{k}}=\sum_{\begin{matrix}{\scriptstyle \left(\forall i\in\hat{k}\right)\left(\alpha_{i}\geq0\right)}\\
{\scriptstyle \sum\alpha_{i}=n}\end{matrix}}\binom{n}{\alpha_{1}}\binom{n-\alpha_{1}}{\alpha_{1}}\cdots\binom{n-\sum_{1}^{k-1}\alpha_{j}}{\alpha_{1}}x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{k}^{\alpha_{k}}=\]
\[
=(x_{1}+x_{2}+...+x_{k})^{n}.\]
 
\end{rem*}
\begin{example*}
Molekuly acyklických uhlovodíků si lze představit jako stromy, kde
vrcholy představují atomy uhlíku (C) a vodíku (H). Hrany pak představují
vazby mezi nimi. Jak známo, uhlík je čtyřvazný a vodík je jednovazný.
Naskýtá se otázka, jak na základě této znalosti vyjádřit sumární vzorec
uhlovodíků ve tvaru\[
\mathrm{C}_{a}\mathrm{H}_{b}.\]
Využijeme vztahu \[
\sum d_{i}=2\# E=2(n-1)\]
který je pro náš případ možno přepsat do podoby\[
4a+1b=2(a+b-1).\]
Z toho dostaneme, že $b=2a+2$, takže sumární vzorce acyklických uhlovodíků
mají tvar\[
\mathrm{C}_{n}\mathrm{H}_{2n+2}.\]
 
\end{example*}