01ZTGA:Kapitola2 2

Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 14:12, kterou vytvořil Karel.brinda (diskuse | příspěvky)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
PDF [ znovu generovat, výstup z překladu ] Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly [ znovu generovat, výstup z překladu ] Přeložení pouze této kaptioly.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214:22 cast3_kapitola2.tex

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}

Citováno z „https://wikiskripta.fjfi.cvut.cz/wiki/index.php?title=01ZTGA:Kapitola2_2&oldid=4532“