Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Pravděpodobnostní důkazy v teorii grafů}
Následující věty udávají příklady tvrzení dokazatelných pomocí tzv.
pravděpodobnostních důkazů. Jeden takový jsme již viděli u věty \ref{thm:odhad-poctu-krizeni}.
Jiné důkazy tohoto typu se vyskytnou i dále, tyto věty však byly první,
u nichž jsme se \emph{v průběhu přednášky} s pravděpodobnostními důkazy
setkali. Na jejich tvrzení již další látka nezávisí, a proto mají
skutečně spíše demonstrativní účel. Jsou zde tedy zařazeny do poněkud
umělé podkapitoly.
\begin{thm}
\[
\frac{\textrm{po\v{c}et bipartitních graf\r{u} na }n\textrm{ vrcholech}}{\textrm{po\v{c}et v\v{s}ech graf\r{u} na }n\textrm{ vrcholech}}\xrightarrow[n\to\infty]{}0\]
\end{thm}
\begin{proof}
Buď $G=(\hat{n},E)$ náhodný graf na $n$ vrcholech. To znamená, že
$E$ vznikne tak, že $\forall i,j\in\hat{n},i\neq j$ je $\{ i,j\}\in E$
s pravděpodobností $\frac{1}{2}$ (pro každé dva vrcholy si hodíme
mincí, a pokud padne líc, spojíme je hranou). Ptejme se, jaká je pravděpodobnost,
že pro pevně daný rozklad $\hat{n}=V_{1}\cup V_{2}$ ($V_{1}\cap V_{2}=\emptyset$
a $V_{1},V_{2}\neq\emptyset$) platí $E\cap\binom{V_{1}}{2}=\emptyset,E\cap\binom{V_{2}}{2}=\emptyset$,
tj. že ve $V_{1}$ ani ve $V_{2}$ nevede hrana.
Označme $k=\# V_{1}$. Potom tato pravděpodobnost je rovna\[
P_{V_{1},V_{2}}=\left(\frac{1}{2}\right)^{\binom{k}{2}}\cdot\left(\frac{1}{2}\right)^{\binom{n-k}{2}},\]
protože $\binom{k}{2}$ je počet různých dvojic vrcholů ve $V_{1}$
a $\binom{n-k}{2}$ je počet různých dvojic vrcholů ve $V_{2}$.
$G$ je bipartitní právě tehdy, když existuje rozklad $\hat{n}=V_{1}\cup V_{2}$
takový, že ve $V_{1}$ ani ve $V_{2}$ nevedou hrany. Využijeme-li
známý vztah z teorie pravděpodobnosti platný pro jevy $A_{j}$\[
\Pr\left(\bigcup A_{j}\right)\leq\sum\Pr A_{j},\]
můžeme odhadnout pravděpodobnost $P$, že $G$ je bipartitní:\[
P\leq\sum_{\begin{matrix}{\scriptstyle \emptyset\neq V_{1}\subsetneqq\hat{n}}\\
{\scriptstyle V_{2}=\hat{n}\backslash V_{1}}\end{matrix}}P_{V_{1},V_{2}}=\sum_{\begin{matrix}{\scriptstyle \emptyset\neq V_{1}\subsetneqq\hat{n}}\\
{\scriptstyle V_{2}=\hat{n}\backslash V_{1}}\\
{\scriptstyle k=\# V_{1}}\end{matrix}}\left(\frac{1}{2}\right)^{\binom{k}{2}}\cdot\left(\frac{1}{2}\right)^{\binom{n-k}{2}}\leq...\]
Nyní použijeme nerovnost $\binom{n/2}{2}\leq\binom{k}{2}+\binom{n-k}{2}$,
která je zřejmá, protože pro každé $k$ je $k\geq\frac{n}{2}$ nebo
$(n-k)\geq\frac{n}{2}$.\[
...\leq\sum_{\begin{matrix}{\scriptstyle \emptyset\neq V_{1}\subsetneqq\hat{n}}\\
{\scriptstyle V_{2}=\hat{n}\backslash V_{1}}\\
{\scriptstyle k=\# V_{1}}\end{matrix}}\left(\frac{1}{2}\right)^{\binom{n/2}{2}}\leq\sum_{V_{1}\subset\hat{n}}\left(\frac{1}{2}\right)^{\binom{n/2}{2}}=2^{n}\left(\frac{1}{2}\right)^{\binom{n/2}{2}}=2^{n-\binom{n/2}{2}}\xrightarrow[n\to\infty]{}0\]
Pravděpodobnost, že na $n$ vrcholech náhodně vybereme graf, který
je bipartitní, tedy klesá s rostoucím $n$ k nule. Protože pravděpodobnost
a relativní četnost v limitě (se vzrůstajícím počtem možných jevů)
splývají, dokázali jsme tím i tvrzení věty.
\end{proof}
\begin{thm}
\emph{(Existence velkých bipartitních grafů)}
Nechť $G=(V,E)$ je (pevně daný) graf na $2n$ vrcholech. Potom existuje
rozklad $V=A\cup B$ takový, že $\# A=\# B=n$ a navíc počet hran
mezi $A$ a $B$ je alespoň $\frac{1}{2}\# E$.
\end{thm}
\begin{proof}
Vybereme náhodně podmnožinu $A$ velikosti $n$, zvolíme $B=V\backslash A$.
Zavedeme náhodnou veličinu $X=X(A)$ jako počet hran mezi $A$ a $B$.
Když nyní ukážeme, že střední hodnota $\E X>\frac{1}{2}\# E$, pak
musí existovat konkrétní realizace $A$ tak, že $X(A)\geq\frac{1}{2}\# E$,
a tím bude důkaz hotov. Tuto myšlenku využijeme i u důkazů dalších
vět.
Pro každou hranu $e\in E$ zavedeme náhodnou veličinu (indikátor jevu)\[
I_{e}=\begin{cases}
1 & e\textrm{ vede mezi }A\textrm{ a }B\\
0 & \textrm{jinak}\end{cases}.\]
Potom \[
X=\sum_{e\in E}I_{e}.\]
Střední hodnota je z definice lineární funkcionál, takže\begin{equation}
\E X=\sum_{e\in E}\E\left(I_{e}\right),\label{eq:aditivita-stredni-hodnoty}\end{equation}
přičemž\[
\E\left(I_{e}\right)=1\cdot\Pr(I_{e}=1)+0\cdot\Pr(I_{e}=0)=\Pr(I_{e}=1)=\Pr(e\textrm{ vede mezi }A\textrm{ a }B)=2\frac{\binom{2n-2}{n-1}}{\binom{2n}{n}}=\frac{n}{2n-1}>\frac{1}{2}.\]
Kombinatorickou úvahu vysvětlíme. Nechť $e=\{ u,v\}$. Potom $\binom{2n-2}{n-1}$
je počet výběrů množiny $A$ tak, že (právě) $u\in A$ a (právě) $v\notin A$.
Tyto dva vrcholy jsou totiž dány pevně a potom už do $A$ vybíráme
jen $n-1$ vrcholů ze zbylých $2n-2$. Dále $2\binom{2n-2}{n-1}$
je počet výběrů množiny $A$ tak, že jeden vrchol ($u$ nebo $v$)
hrany $e$ leží v $A$ a ten druhý neleží. Konečně $\binom{2n}{n}$
je počet všech různých výběrů množiny $A$.
Pokud nyní dosadíme do (\ref{eq:aditivita-stredni-hodnoty}), dostaneme\[
\E X=\# E\cdot\E\left(I_{e}\right)>\frac{1}{2}\# E.\]
\end{proof}
