# Kombinatorika a grafy 1

## Odhady na kombinatorické funkce

- $n!=\prod_{i=1}^ni$
- lemma: $n^{n/2}\leq n!\leq n^n$
	- horní odhad jednoduchý
	- dolní odhad
		- součin prvního a posledního, druhého a předposledního, … prvku součinu faktoriálu je vždy $\geq n$
		- aby byl počet činitelů faktoriálu sudý, použijeme $(n!)^2$
		- takže $(n!)^2=\prod_{i=1}^n(i\cdot(n+1-i))\geq n^n$
		- proto $n!\geq n^{n/2}$
		- to, že $i(n+1-i)\geq n$, lze dokázat graficky pomocí funkce $f(x)=x(n+1-x)$
	- důsledek $\sqrt n\leq \sqrt[n]{n!}\leq n$
	- $\sqrt[n]{n!}$ se chová trochu jako $\frac n2$
- věta: $e(\frac ne)^n\leq n!\leq en(\frac ne)^n$
	- u zkoušky můžeme použít libovolný korektní důkaz (obecně u všech vět)
	- důkaz 1: indukcí s využitím $e^x\geq 1+x$
	- důkaz 2: odhad pomocí integrálu $\ln(n!)=\sum_{i=1}^n\ln(i)=\sum_{i=2}^n\ln(i)$
		- schodovitá plocha, kde schod má šířku 1 a výšku $\ln(i)$ má obsah daný uvedeným součtem
		- obsah schodovité plochy je zdola odhadnutý obsahem plochy pod křivkou logaritmu
		- $\ln(n!)\geq\int_1^n\ln(x)\,dx=[x\ln(x)-x]^n_1=(n\ln n-n+1)=:I_n$
		- $n!\geq e^{I_n}=e^{n\ln n-n+1}=e(\frac ne)^n$
		- obdobně dolní odhad
			- $\ln((n-1)!)\leq I_n$
			- $e^{I_n}\geq(n-1)!\implies n\cdot e^{I_n}\geq n!\implies n\cdot e(\frac ne)^n\geq n!$
	- důkaz 3: jen $(\frac ne)^n\leq n!$
		- víme z analýzy, že $e^x=1+x+\frac{x^2}{2}+\frac{x^3}{3!}+\dots+\frac{x^k}{k!}+\dots=\sum^\infty_{k=0}\frac{x^k}{k!}$
		- pro $x\geq 0:e^x\geq\frac {x^n}{n!}$ (protože Taylorova řada určitě někde obsahuje $x^n\over n!$)
		- tedy $n!\geq \frac{x^n}{e^x}\implies n!\geq \frac{n^n}{e^n}=(\frac ne)^n$ (platí to pro libovolné $x\geq 0$, takže dosadíme $x=n$)
- kombinační číslo ${n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot(n-1)\cdots(n-k+1)}{k\cdot(k+1)\cdots1}$
	- jeho odhad…
- pozorování: ${n\choose k}={n\choose n-k}$
- ${2m\choose m}$
- fakt: kombinační čísla v jednom řádku Pascalova trojúhelníku zleva doprava do poloviny rostou, od poloviny klesají
- fakt: $\sum_{k=0}^n{n\choose k}=2^n=(1+1)^n$
- pozorování: $\frac{2^{2m}}{2m+1}\leq{2m\choose m}\leq 2^{2m}$
- věta: $\forall m\in\mathbb N:\frac{2^{2m}}{2\sqrt{m}}\leq {2m\choose m}\leq {2^{2m}\over\sqrt{2m}}$
- důkaz
	- definujme $P:=\frac{2m\choose m}{2^{2m}}$ a dokažme $\frac1{2\sqrt{m}}\leq P\leq \frac{1}{\sqrt{2m}}$
	- …

## Vytvořující (generující) funkce

- definice: vytvořující funkce posloupnosti $(a_n)_{n=0}^\infty$ reálných čísel je funkce proměnné $x$ definovaná jako součet $f(x)=\sum_{n=0}^\infty a_n(x^n)$
	- tato funkce nemusí být dobře definovaná pro všechna reálná čísla (dokonce se může stát, že nebude definovaná pro žádné reálné číslo kromě nuly)
	- pro nás bude praktické, když bude definovaná na okolí nuly (více než jednobodovém)
- fakt: pokud existuje $K\gt 0$ taková, že $\forall n:|a_n|\leq K^n$ (posloupnost se dá shora odhadnout nějakou exponenciální funkcí), tak řada $\sum_{n=0}^\infty a_nx^n$ konverguje na $(-\frac 1K,\frac 1K)$ absolutně stejnoměrně
- navíc má $f(x)=\sum_{n=0}^\infty a_nx^n$ derivace všech řádů na $(-\frac 1K,\frac 1K)$, které se dají spočítat „derivováním člen po členu“
	- $f'(x)=\sum_{n=0}^\infty a_nnx^{n-1}$
	- $f''(x)=\sum_{n=0}^\infty a_nn(n-1)x^{n-2}$
	- $f(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots$
	- $f'(x)=a_1+2a_2x+3a_3x^2+\dots$
	- $f''(x)=2a_2+3\cdot 2a_3+\dots$
	- $f^{(n)}(x)=n!\cdot a_n+\dots$
- důsledek
	- $f(0)=a_0$
	- $f'(0)=a_1$
	- $f''(0)=2a_2$
	- $f^{(n)}(0)=n!\cdot a_n$
	- takže $a_n=\frac{1}{n!} f^{(n)}(0)$
- fakt: vytvořující funkce lze mezi sebou násobit jako polynomy, výsledek je vytvořující funkcí posloupnosti $a_0b_0,a_0b1+a_1b0,\dots$, této posloupnosti se říká konvoluce posloupností $(a_n)_{n=0}^\infty$ a $(b_n)_{n=0}^\infty$
- užití vytvořujících funkcí
	- kombinatorické počítání
	- asymptotické odhady
	- dokazování identit u posloupností
	- řešení rekurencí
- příklad na kombinatorické počítání – platíme $n$ Kč pomocí mincí s hodnotami 1, 2 a 5 Kč, na pořadí nezáleží ($a_n$ je počet způsobů, jak $n$ korun zaplatit)
	- $f(x)=\sum_{n=0}^\infty a_nx^n=$
	- $=(1+x+x^2+x^3+\dots)(1+x^2+x^4+x^6+\dots)(1+x^5+x^{10}+\dots)$
	- $=\frac1{1-x}\cdot\frac1{1-x^2}\cdot\frac1{1-x^5}$
	- pak lze zjistit koeficient u $x^n$, ten se bude rovnat $a_n$

### Řešení rekurencí

- Fibonacciho čísla $F_0:=0,\,F_1:=1,\,F_n:=F_{n-1}+F_{n-2}$ pro $n\geq 2$
	- chceme získat explicitní vzorec pro $f(x)=\sum_{n=0}^\infty F_nx^n$
	- obecná metoda řešení rekurencí
		- vezmi rekurenci pro $n\geq n_0$
		- vynásob ji $x^n$
		- sečti pro $n\geq n_0$
		- vyjádři všechny sumy pomocí hledané vytvořující funkce $f(x)$
		- dopočítej $f(x)$
	- aplikace na $F_n$
		- $F_n=F_{n-1}+F_{n-2}$ pro $n\geq 2$
		- $F_nx^n=F_{n-1}x^n+F_{n-2}x^n$ pro $n\geq 2$
		- $\underbrace{\sum_{n=2}^\infty F_nx^n}_{S_1}=\underbrace{\sum_{n=2}^\infty F_{n-1}x^n}_{S_2}+\underbrace{\sum_{n=2}^\infty F_{n-2}x^n}_{S_3}$
			- $S_1=F_2x^2+F_3x^3+F_4x^4+\dots=f(x)-F_0-F_1x$
			- $S_2=F_1x^2+F_2x^3+F_3x^4+\dots=x(f(x)-F_0)$
			- $S_3=F_0x^2+F_1x^3+F_2x^4+\dots=x^2f(x)$
			- $S_1=S_2+S_3$
			- $f(x)-F_0-F_1x=x(f(x)-F_0)+x^2f(x)$
			- $f(x)-xf(x)-x^2f(x)=F_0+F_1x-F_0x$
			- $f(x)\cdot(1-x-x^2)=F_0+F_1x-F_0x$
			- $f(x)=\frac{F_0+F_1x-F_0x}{1-x-x^2}=\frac x{1-x-x^2}$
- obecnější příklad – mějme posloupnost $a_0,a_1,a_2,\dots$, která splňuje $a_n=\alpha_1a_{n-1}+\alpha_2a_{n-2}+\dots+\alpha_da_{n-d}$ pro každé $n\geq d$, kde $d\in\mathbb N$, $\alpha_1,\dots,\alpha_d\in\mathbb R,\,\alpha_d\neq 0$; najděme vzorec pro $f(x)=\sum_{n=0}^\infty a_nx^n$
	- $\sum_{n=d}^\infty a_nx^n=$
	- $=\sum_{n=d}^\infty\alpha_1a_{n-1}x^n+\sum_{n=d}^\infty\alpha_2a_{n-2}x^n+\dots+\sum_{n=d}^\infty\alpha_da_{n-d}x^n$
	- $f(x)-(a_0+a_1x+\dots+a_{d-1}x^{d-1})=$
	- $=a_1x(f(x)-(a_0+a_1x+\dots+a_{d-2}x^{d-2}))+$
	- $+a_2x^2(f(x)-(a_0+\dots+a_{d-3}x^{d-3}))+\dots+a_dx^df(x)$
	- …
- pro $\alpha,\beta,\gamma\in\mathbb R,\,\beta\neq0:\frac\alpha{\beta+\gamma x}=\frac\alpha\beta\cdot\frac1{1-(-\frac\gamma\beta x)}$
	- z toho už umím najít původní vzorec vytvořující funkce pomocí $\frac1{1-x}$
- víme: binomická věta
	- pro $d\in\mathbb N_0:(1+x)^d=\sum_{n=0}^d{d\choose n}x^n$
	- tedy $(1+x)^d$ je vytvořující funkcí pro ${d\choose 0},{d\choose1},{d\choose2},\dots,{d\choose d},0,0,0,\dots$
- df: pro $\delta\in\mathbb R$ a $n\in\mathbb N_0$ definujeme zobecněné kombinační číslo ${\delta\choose n}:=\frac{\delta(\delta-1)\cdot(\delta-2)\cdot\ldots\cdot(\delta-n+1)}{n!}$
- věta: zobecněná binomická věta
	- pro $\delta\in\mathbb R$ platí $(1+x)^\delta=\sum_{n=0}^\infty{\delta\choose n}x^n$
	- nekonečno bychom mohli použít i u základní binomické věty, pokud bychom použili zobecněné kombinační číslo
	- celkově ignorujeme otázky konvergence, ale aby věta platila, tak bychom chtěli $|x|\lt1$
- dk: označme $f(x)=(1+x)^\delta$
	- vidíme
		- $f'(x)=\delta(1+x)^{\delta-1}$
		- $f''(x)=\delta(\delta-1)(1+x)^{\delta-2}$
		- $\quad\vdots$
		- $f^{(n)}(x)=\delta(\delta-1)\cdot\ldots\cdot(\delta-n+1)(1+x)^{\delta-n}$
		- $\quad\vdots$
	- nechť $a_0,a_1,\dots$ je posloupnost s vytvořující funkcí $f(x)$
	- potom $a_n=\frac{f^{(n)}(0)}{n!}={\delta\choose n}\quad\square$
- důsledek
	- pro $d\in\mathbb N_0:\frac1{(1-x)^d}=(1+(-x))^{-d}=_{\text{ZBV}}$
	- …
- důsledek důsledku
	- $\frac\alpha{(\beta+\gamma x)^d}=\frac\alpha{\beta^d}\cdot\frac1{(1-(-\frac\gamma\beta x))^d}=\sum_{n=0}^\infty\frac{\alpha}{\beta^d}{n+d-1\choose d-1}(-\frac\gamma\beta)^nx^n$
	- čeho je vytvořující funkce $f(x)=\frac\alpha{\gamma x}$? ničeho, protože $f(x)$ nelze spojitě dodefinovat v nule (kromě $\alpha=0$, potom $f(x)=0$)
- df: pro $d\in\mathbb N$ a $\rho\in\mathbb R$, parciální zlomek stupně $d$ pro kořen $\rho$ je výraz tvaru $\frac{\alpha}{(x-\rho)^d}$, kde $\alpha$ je reálná konstanta
- poznámka: pokud $p\neq 0$, tak parciální zlomek lze přepsat do tvaru $\frac{\alpha}{(1-\frac x\rho)}\cdot\frac1{(-\rho)^d}=\frac{\tilde\alpha}{(1-\frac{x}{\rho})^d}=\sum_{n=0}^\infty\tilde\alpha\frac1{\rho^n}{n+d-1\choose d-1}x^n$
- fakt
	- mějme funkci $f(x)=\frac{P(x)}{Q(x)}$, kde $P(x)$ a $Q(x)$ jsou polynomy a stupeň $P(x)$ je menší než stupeň $Q(x)$
	- nechť $Q(x)$ má navzájem různé reálné kořeny $\rho_1,\rho_2,\dots,\rho_k$ a nechť $n_i$ označuje násobnost kořenu $\rho_i$
	- předpokládejme, že $Q(x)$ nemá nereálné kořeny, tedy $Q(x)=\gamma\cdot(x-\rho_1)^{n_1}\cdot(x-\rho_2)^{n_2}\cdot\ldots\cdot(x-\rho_k)^{n_k}$, kde $\gamma\in\mathbb R$
	- potom $f(x)$ se dá vyjádřit jako součet parciálního zlomků pro kořeny $\rho_1,\dots,\rho_k$, kde parciální zlomky pro $\rho_i$ mají stupeň nejvýš $n_i$
	- jinými slovy $\exists\alpha_{ij}\in\mathbb R:f(x)=\sum_{i=1}^k\sum_{j=1}^{n_i}\frac{\alpha_{ij}}{(x-\rho_i)^j}$
	- tohle je „dětská verze“ parciálních zlomků, důkaz nemusíme znát
	- poznámka
		- pokud $P(x)$ má aspoň tak velký stupeň jako $Q(x)$, tak pomocí dělení se zbytkem lze $P(x)$ vyjádřit jako $P'(x)\cdot Q(x)+Z(x)$ pro nějaké $P'(x)$ a $Z(x)$, kde $Z(x)$, kde $Z(x)$ má menší stupeň než $Q(x)$, a tedy $\frac{P(x)}{Q(x)}=P'(x)+\frac{Z(x)}{Q(x)}$
	- tohle všechno nám umožňuje najít posloupnost k dané vytvořující funkci (která je podílem dvou polynomů)
	- (jednodušší) rozklad na parciální zlomky bychom mohli umět ke zkoušce
- příklad: Fibonacciho čísla $f(x)=\sum F_nx^n=\frac x{1-x-x^2}$
	- kořeny $1-x-x^2:\rho_1=\frac{1-\sqrt5}{-2}=\frac{\sqrt5-1}{2},\,\rho_2=\frac{1+\sqrt5}{-2}=\frac{-1-\sqrt5}2$
	- $1-x-x^2=\gamma(x-\rho_1)(x-\rho_2)=-(x-\rho_1)(x-\rho_2)=$
	- $=-\rho_1\rho_2(1-\frac x{\rho_1})(1-\frac x{\rho_2})=(1-\frac x{\rho_1})(1-\frac x{\rho_2})$
	- $\frac{x}{1-x-x^2}=\frac{\alpha}{1-\frac{x}{\rho_1}}+\frac{\beta}{1-\frac x{\rho_2}}$ pro nějaké $\alpha,\beta\in\mathbb R$
	- $x=\alpha(1-\frac{x}{\rho_2})+\beta(1-\frac{x}{\rho_1})$
		- dosazením $x=0:\quad0=\alpha+\beta$
		- dosazením $x=\rho_2:\quad\rho_2=\beta(1-\frac{\rho_2}{\rho_1})$
		- z toho se dá vyjádřit $\alpha$ i $\beta$ pomocí $\rho$
	- $\alpha=\frac1{\sqrt5}$
	- $\beta=-\frac1{\sqrt5}$
	- tak se dá dojít k explicitnímu vzorci pro Fibonacciho čísla
- df: binární strom je zakořeněný strom, jehož každý vnitřní vrchol má 2 potomky, na pořadí potomků záleží
	- $C_n$ … počet binární stromů s $n$ vnitřními vrcholy
		- $C_0=1$
		- $C_1=1$
		- $C_2=2$
		- $C_3=5$
	- $(C_n)_{n=0}^\infty$ jsou Catalanova čísla
	- $C(x):=\sum_{n=0}^\infty C_nx^n$
	- $C_0=1$
	- mějme kořen, levý syn je list, pravý podstrom má $n-1$ vnitřních vrcholů → počet možných pravých podstromů je $C_{n-1}$
	- nebo levý podstrom má jeden vnitřní vrchol a pravý $n-2$, pak $C_1\cdot C_{n-2}$ možností
	- obecně levý podstrom $i$ vnitřních vrcholů, pravý $n-1-i$ vnitřních vrcholů, pak $C_i\cdot C_{n-1-i}$ možností
	- $C_n=C_0C_{n-1}+C_1C_{n-2}+\dots+C_{n-1}C_0=\sum_{i=0}^{n-1}C_iC_{n-1-i}$
		- pro $n\geq 1$
	- $\sum_{n=1}^\infty C_nx^n=\sum_{n=1}^\infty\left(\sum_{i=0}^{n-1}C_iC_{n-1-i}\right)x^n$
	- $C(x)-1=x\sum_{n=0}^\infty\left(\sum_{i=0}^{n}C_iC_{n-i}\right)x^n$
	- $C(x)-1=x\cdot C^2(x)$
	- $xC^2(x)-C(x)+1=0$
	- 2 řešení
		- $\frac{1+\sqrt{1-4x}}{2x}=:C^+(x)$
		- $\frac{1-\sqrt{1-4x}}{2x}=:C^-(x)$
	- chceme $C(0)=C_0=1$
	- $C^-(x)$ lze spojitě dodefinovat v nule, takže $C(x)=C^-(x)$
	- značení: $[x^n]f(x)$ je člen s indexem $n$ v posloupnosti, jejíž vytvořující funkce je $f(x)$
	- $C_n:=[x^n]\frac{1-\sqrt{1-4x}}{2x}=[x^{n+1}]\frac{1-\sqrt{1-4x}}{2}=[x^{n+1}](\frac12-\frac{\sqrt{1-4x}}{2})=$
		- konstanta nám ovlivňuje koeficient u $C_0$, můžeme se jí zbavit
	- $=-\frac12[x^{n+1}]\sqrt{1-4x}=$
		- …

## Projektivní roviny

- df: hypergraf je dvojice $(V,H)$, kde $H$ je množina podmnožin $V$, tj. $H\subseteq\mathcal P(V)$
	- prvky $V$ … vrcholy
	- prvky $H$ … hyperhrany
	- graf incidence hypergrafu $(V,H)$ je bipartitní graf s partitami $V$ a $H$, kde mezi $x\in V$ a $h\in H$ vede hrana $\iff x\in h$
	- hyperhrany jsou jakoby množiny vrcholů
- df: projektivní rovina je hypergraf $(X,\mathcal P)$ takový, že platí tři axiomy:
	- A1: $(\forall x,y\in X,\;x\neq y)(\exists! p\in\mathcal P):\set{x,y}\subseteq p$
		- dva různé body určují právě jednu přímku
	- A2: $\forall p,q\in\mathcal P,\;p\neq q:|p\cap q|=1$
		- každé dvě přímky mají jeden průsečík
	- A3: $(\exists Č\subseteq X,\;|Č|=4)(\forall p\in\mathcal P):|p\cap Č|\leq 2$
		- existuje množina čtyř bodů „v obecné poloze“ (žádné tři z nich neleží na přímce)
	- prvky $X$ … body
	- prvky $\mathcal P$ … přímky
- df: konečná projektivní rovina (KPR) je projektivní rovina $(X,\mathcal P)$, v níž $X$ je konečná (a tudíž i $\mathcal P$ je konečná)
- příklady projektivních rovin
	- Fanova rovina
	- rozšířená reálná eukleidovská rovina
		- musíme dodefinovat „body v nekonečnu“ – pro každý možný směr rovnoběžek přidáme abstraktní bod, tyhle abstraktní body spojíme přímkou
	- karetní hra Dobble (splňuje alespoň jeden axiom – možná všechny?)
- příklad projektivní roviny
	- mějme body $a,b,c,d$
	- přímky
		- $\set{a,b,e}$
		- $\set{b,c,g}$
		- $\set{c,d,e}$
		- $\set{a,d,g}$
		- $\set{a,c,f}$
		- $\set{b,d,f}$
	- $e,f,g$ jsou průsečíky kvůli druhému axiomu
	- musíme dodat přímku $\set{e,f,g}$
	- tím dostáváme Fanovu rovinu (7 bodů, 7 přímek)
- značení: pro $(X,\mathcal P)$ KPR, $x,y\in X,\; x\neq y:\overline{xy}$ značí přímku obsahující $x$ a $y$
- tvrzení: v každé KPR mají všechny přímky stejný počet bodů
- dk: sporem
	- nechť v KPR $(X,\mathcal P)$ existují přímky $p,q$ takové, že $|p|\lt |q|$
	- označme $x$ společný bod $p,q$
	- nechť $p$ obsahuje body $x,y_1,y_2,\dots,y_k$ a $q$ obsahuje body $x,z_1,z_2,\dots,z_l$, kde $k\lt l$
	- tvrdím, že existuje bod $w\in X$, který nepatří do $p\cup q$: volme $Č$ dle A3
	- pokud $Č\setminus(p\cup q)\neq\emptyset$, volme $w\in Č\setminus(p\cup q)$
	- pokud $Č\subseteq p\cup q$, pak $|Č\cap p| = |Č\cap q|=2$, BÚNO $Č=\set{y_1,y_2,z_1,z_2}$
		- v tom případě zvolíme za $w$ společný bod $\overline{y_1z_1}$ a $\overline{y_2z_2}$
	- kdyby $w\in p$, tak $w$ je jediný společný bod $p$ a $\overline{y_1z_1}$, a tedy $w=y_1$, ale $w\in\overline{y_2z_2}$, tedy $y_1=w\in\overline{y_2z_2}$, tedy $|Č\cap \overline{y_2z_2}|\geq |\set{y_1,y_2,z_2}|=3$, což je spor s volbou $Č$
	- uvažme přímky $\overline{w,z_1},\overline{w,z_2},\dots,\overline{w,z_l},\overline{w,x}$, každá z nich protíná $p$, jsou navzájem různé, tedy existuje bod $v\in p$, který je obsažen v aspoň dvou z těch přímek $\overline{wz_1},\dots,\overline{wz_l},\overline{wx}$
	- spor: $w$ a $v$ mají aspoň 2 společné přímky $\quad\square$
- def: KPR má řád $n\in\mathbb N$, pokud každá její přímka má $n+1$ bodů
	- tedy řád KPR := velikost přímky – 1
- lemma: v projektivní rovině $(X,\mathcal P)$ platí $(\forall x\in X)(\exists p\in\mathcal P):x\notin p$
- důkaz
	- volme Č dle A3
	- volme 3 různé body $a,b,c\in Č\setminus\set x$
	- tvrdím, že alespoň jedna z přímek $\overline{ab},\overline{ac}$ neobsahuje $x$
	- jinak by $\set{a,x}\subseteq\overline{ac}\cap\overline{ab}$, což je spor
- tvrzení: pro KPR $(X,\mathcal P)$ řádu $n$ platí následující
	- každý bod patří do právě $n+1$ přímek
	- $|X|=n^2+n+1$
	- $|\mathcal P|=n^2+n+1$
- důkaz
	- první bod
		- volme $x\in X$
		- dle lemmatu $\exists p\in\mathcal P:x\notin p$
		- označme $p=\set{y_1,y_2,\dots,y_{n+1}}$
		- definujme přímky $q_1,q_2,\dots,q_{n+1}$, kde $q_i=\overline{xy_i}$
		- tvrdíme, že pro $i\neq j$ je $q_i\neq q_j$
			- kdyby ne, tak $\set{y_i,y_j}\subseteq q_i\cap p$, což je spor
		- tvrdíme, že $\forall r\in\mathcal P:$ pokud $x\in r$, tak $r\in\set{q_1,\dots,q_{n+1}}$
		- volme $r\in\mathcal P$ takovou, že $x\in r$, jistě $|r\cap p|=1$, nechť $y_i$ je prvek $r\cap p$, potom $r=\overline{xy_i}=q_i$
		- tedy bodem $x$ prochází právě $n+1$ přímek
	- druhý bod
		- volme $x\in X$, nechť $p_i$ jsou přímky procházející $x$
		- všimněme si, že každý bod $y\in X\setminus\set{x}$ patří do právě jedné z přímek $p_i$
		- $|X|=|\set{x}|+|p_1\setminus\set{x}|+|p_2\setminus\set{x}|+\dots+|p_{n+1}\setminus\set{x}|=$
		- $=1+(n+1)\cdot n=n^2+n+1$
	- třetí bod
		- graf incidence – bipartitní graf, nahoře přímky, dole body
		- každý vrchol dolní partity má stupeň $n+1$
		- každý vrchol horní partity má stupeň $n+1$
		- celá dolní partita má $n^2+n+1$ vrcholů
		- to už stačí
		- počítání dvěma způsoby
			- počítáme počet dvojic $(x,p)\in X\times \mathcal P$ takových, že $x\in p$
				- těch je $|X|\cdot(n+1)=(n^2+n+1)(n+1)$
				- je jich taky $|\mathcal P|\cdot(n+1)$
				- tudíž $(n^2+n+1)(n+1)=|\mathcal P|\cdot(n+1)$
				- proto $|\mathcal P|=(n^2+n+1)$
- df: mějme projektivní rovinu $(X,\mathcal P)$; potom duální projektivní rovina k $(X,\mathcal P)$ je hypergraf $(X^*,\mathcal P^*)$, kde
	- $X^*=\mathcal P$,
	- pro $x\in X$ definujme $x^*:=\set{p\in\mathcal P:x\in p}$
	- $\mathcal P^*=\set{x^*:x\in X}$
- tvrzení: $(X^*,\mathcal P^*)$ je projektivní rovina
	- důkaz viz záznam
	- idea: první dva axiomy stačí prohodit
	- A3: nejvýše dvě přímky z Č* (množina 4 přímek) procházejí skrz x
		- existuje množina 4 přímek takových, že žádné tři z nich neprocházejí jedním bodem
		- máme 4 body z A3 v původní projektivní rovině – označíme $a,b,c,d$
		- zvolíme přímky $\overline{ab},\overline{bc},\overline{cd}$
			- průnik prvních dvou je $b$
			- průnik druhých dvou je $c$
			- společný bod nemají
- konstrukce KPR řádu $n\in \mathbb N$
	- nechť $T$ je konečné těleso s $n$ prvky (tedy $n$ musí být kladná celá mocnina prvočísla), uvažujme vektorový prostor $V=T^3=\set{(x,y,z):x,y,z\in T}$, $|V|=n^3$
	- nechť $X$ je mmnožina podprostorů dimenze 1 ve $V$
	- $|X|=\frac{n^3-1}{n-1}$
		- protože máme $n^3-1$ nenulových vektorů, každý patří do jednoho podprostoru dimenze 1
		- podprostor dimenze 1 má $n-1$ nenulových vektorů
	- $|X|=\frac{n^3-1}{n-1}=n^2+n+1$
	- pro každý podprostor $p\subseteq V$ dimenze 2 definuji $\tilde{p}:=\set{x\in X: x\subseteq p}$
	- $\mathcal P=\set{\tilde p:p\text{ je podprostor V dimenze 2}}$
	- $|\mathcal P|=|X|$, protože podprostor dimenze 2 je ortogonálním doplňkem podprostoru dimenze 1 a protože existuje bijekce mezi podprostory a jejich ortogonálními doplňky
	- $(X,\mathcal P)$ je projektivní rovina
		- důkaz jednoduchý, viz záznam
- neví se, jestli existuje projektivní rovina řádu 12

## Toky v sítích

- tokovou síť tvoří
	- $V$ … množina vrcholů
	- $E$ … množina orientovaných hran, $E\subseteq V\times V$
	- $z\in V$ … zdroj
	- $s\in V\setminus\set{z}$ … spotřebič / stok
	- $c:E\to [0,+\infty)$ … $c(e)$ je kapacita hrany $e$
- definice umožňuje mít hrany oběma směry, připouští také smyčky, ty však z hlediska toků v sítích nejsou nijak užitečné
- poznámka: ze stoku může vycházet orientovaná hrana, podobně do zdroje může vést hrana
- tok v síti $(V,E,z,s,c)$ je funkce $f:E\to[0,+\infty)$ splňující
	- $\forall e\in E:0\leq f(e)\leq c(e)$
	- $\forall x\in V\setminus \set{z,s}:$ součet toků do vrcholu $x$ se rovná součtu toků z vrcholu (formálně pomocí sum) … Kirchhoffův zákon
- konvence: $f(x,y)$ je zkratka pro $f((x,y))$
- pro vrchol $x\in V$:
	- $\text{In}(x):=\set{(y,x)\in E}$
	- $\text{Out}(x):=\set{(x,y)\in E}$
- pro $A\subseteq V$:
	- $\text{In}(A):=\set{(u,v)\in E;\,u\notin A,\, v\in A}$
	- $\text{Out}(A):=\set{(u,v)\in E;\,u\in A,\, v\notin A}$
- pro $F\subseteq E:f[F]:=\sum_{e\in F}f(e)$
- tj. Kirchhoffův zákon lze vyjádřit takto $\forall x\in V\setminus \set{z,s}:f[\text{In}(x)]=f[\text{Out}(x)]$
- df: velikost toku $f$ v síti $(V,E,z,s,c)$ je $w(f):=f[\text{Out}(z)]-f[\text{In}(z)]$
- maximální tok je tok, který má největší velikost
- fakt: v každé tokové síti existuje maximální tok
	- poznámka: obecně na přednášce uvažujeme konečné tokové sítě, grafy apod.
	- idea důkazu: mějme síť, očíslujme hrany (od $1$ do $m$), tok $f$ reprezentujme jako uspořádanou $m$-tici hodnot → množina všech toků je uzavřená a omezená podmnožina $\mathbb R^m$, je tedy kompaktní; funkce, která toku $f$ přiřadí $w(f)$, je spojitá; víme z analýzy, že spojitá funkce na kompaktní množině nabývá maxima
- lemma: pro tok $f$ v síti $(V,E,z,s,c)$ a pro množinu $A\subseteq V$ takovou, že $z\in A$ a $s\notin A$ platí $w(f)=f[\text{Out}(A)]-f[\text{In}(A)]$
- důkaz
	- víme
		- $w(f)=f[\text{Out}(z)]-f[\text{In}(z)]$
		- $\forall x\in A\setminus\set{z}:0=f[\text{Out}(x)]-f[\text{In}(x)]$
	- sečteme rovnosti: $w(f)=\sum_{x\in A}f[\text{Out}(x)]-\sum_{x\in A}f[\text{In}(x)]$
	- $\sum_{x\in A}f[\text{Out}(x)]$ … sčítá všechny hrany, které vycházejí ze všech vrcholů $A$ – tyto hrany jsou dvou typů, buď končí opět v $A$, nebo končí mimo $A$
	- $E_A:=\set{(u,v)\in E:u\in A,\,v\in A}=E\cap(A×A)$ (hrany, které začínají v $A$ a končí v $A$)
	- $w(f)=f[\text{Out}(A)]+f[E_A]-(f[\text{In}(A)]+f[E_A])$
- df: řez v síti $(V,E,z,s,c)$ je množina hran $R\subseteq E$ taková, že každá orientovaná cesta ze $z$ do $s$ obsahuje aspoň jednu hranu $R$
- kapacita řezu $R:c(R)=\sum_{e\in R}c(e)$
- minimální řez je řez, který má ze všech řezů nejmenší kapacitu
- nechť $A\subseteq V$ je množina vrcholů taková, že $z\in A$ a $s\notin A$; potom zjevně $\text{Out}(A)$ tvoří řez; každý takový řez je elementární řez
- lemma: každý řez $R$ obsahuje nějaký elementární řez jako podmnožinu
- dk: nechť $R$ je řez; $A:=\set{x\in V:\text{existuje orientovaná cesta ze }z\text{ do }x\text{ neobsahující hrany }R}$
- zjevně $z\in A$, zjevně $s\notin A$ (z definice řezu), zjevně $\text{Out}(A)\subseteq R$
- lemma: nechť $f$ je tok a $R$ je řez v síti $(V,E,z,s,c)$; potom $w(f)\leq c(R)$
- df: nechť $f$ je tok v síti $(V,E,z,s,c)$; nenasycená cesta pro $f$ je neorientovaná cesta $x_1e_1x_2e_2\dots x_ke_kx_{k+1}$, kde $\forall i:$ buď $e_i=(x_i,x_{i+1})$ ($e_i$ je dopředná hrana), nebo $e_i=(x_{i+1},x_i)$ ($e_i$ je zpětná hrana) a navíc platí
	- pro každou dopřednou hranu $e_i$ platí $f(e_i)\lt c(e_i)$
	- pro každou zpětnou hranu $e_i$ platí $f(e_i)\gt 0$
- zlepšující cesta pro $f$ je nenasycená cesta ze $z$ do $s$
- pozorování: pokud má tok $f$ zlepšující cestu, tak není maximální
- dk: máme zlepšující cestu pro tok $f$, označme $\varepsilon$ možné zlepšení (je to minimum přes všechny rozdíly od kapacit na dopředných hranách a od nuly na zpětných hranách), přičtením/odečtením $\varepsilon$ dostaneme lepší tok $g$, takže $f$ nemohl být maximální
- důkaz, že $w(f)\leq c(R)$
	- definujme $A:=$ vrcholy $x\in V$ takové, že existuje orientovaná cesta ze $z$ do $x$ nepoužívající hrany $R$
	- $z\in A$, $s\notin A$, $\text{Out}(A)\subseteq R$
	- $w(f)=f[\text{Out}(A)]-f[\text{In}(A)]\leq f[\text{Out}(a)]\leq c(\text{Out}(A)) \leq c(R)$
- věta: nechť $f$ je tok v síti; potom následující tvrzení ekvivalentní
	- $f$ je maximální
	- $f$ nemá zlepšující cestu
	- existuje řez $R$ takový, že $w(f)=c(R)$
- dk
	- $1\implies 2:$ jednoduše obměnou
	- $3\implies 1:$ pro libovolný řez $R'$ a libovolný tok $f'$ platí, že $w(f')\leq c(R')$; kdyby $f$ nebyl maximální, tak existuje $f^+$ tok splňující $w(f^+)\gt w(f)$, potom pro každý řez $R$ platí, že $c(R)\geq w(f^+)\gt w(f)$, tedy neexistuje žádný řez $R$ splňující $c(R)=w(f)$
	- $2\implies 3$
		- nechť $f$ je tok, který nemá zlepšující cestu
		- definujme množinu $A:=\set{x\in V,\,\text{ze }z\text{ do }x\text{ vede nenasycená cesta}}$
		- zjevně $z\in A,\,s\notin A$
		- definujme $R:=\text{Out}(A)=\set{uv\in E,\,u\in A,\,v\notin A}$
		- všimněme si $\forall e\in\text{Out}(A):f(e)=c(e)$
		- $\forall e'\in\text{In}(A):f(e')=0$
		- z lemmatu výše víme, že pro $A\subseteq V$, kde $z\in A,\,s\notin A$, platí $w(f)=\underbrace{f[\text{Out}(A)]}_{c(\text{Out}(A))=c(R)}-\underbrace{f[\text{In}(A)]}_{0}=c(R)\quad\square$
- důsledek („Minimaxová věta o toku a řezu“): nechť $f_\max$ je maximální tok a $R_\min$ je minimální řez v $(V,E,z,s,c)$, potom $w(f_\max)=c(R_\min)$
- dk: $w(f_\max)\leq c(R_\min)$ – víme, viz výše; $w(f_\max)\geq c(R_\min)$ … dle věty $w(f_\max)=c(R)\geq c(R_\min)$
- důsledek 2: v síti, kde všechny kapacity jsou celočíselné, Fordův-Fulkersonův algoritmus najde maximální tok, který bude celočíselný (celočíselnost vyvozujeme ze znalosti FF algoritmu)

### Aplikace toků

- df: párování v grafu $G=(V,E)$ je množina hran $M\subseteq E$ taková, že žádný vrchol nepatří do více než jedné hrany $M$
- df: vrcholové pokrytí v $G=(V,E)$ je množina vrcholů $C\subseteq V$ taková, že každá hrana obsahuje aspoň 1 vrchol z $C$
- pozorování: pokud $M$ je párování a $C$ vrcholové pokrytí v $G=(V,E)$, tak $|M|\leq |C|$; to proto, že každá hrana z $M$ musí být pokrytá vrcholem z $C$, zároveň každý vrchol z $C$ pokryje nejvýš 1 hranu z $M$
- věta (Kőnig-Egerváry): v každém **bipartitním** grafu má největší párování stejnou velikost jako nejmenší vrcholové pokrytí
- dk:
	- nechť $G=(V,E)$ je bipartitní graf s partitami $A,B$
	- vytvořme tokovou síť $(V\cup\set{z,s},E^+,z,s,c)$, kde $E^+=\set{zx\mid x\in A}\cup\set{ys\mid y\in B}\cup \set{xy\mid \set{x,y}\in E\land x\in A\land y\in B}$ (nestačí použít $E$, protože orientujeme hrany z ) a $c(zx)=c(ys)=1$ pro $x\in A,\,y\in B$ a $c(xy)=|A|+|B|+1$ (prakticky nekonečno)
	- nechť $C_\min$ je nejmenší vrcholové pokrytí v $G$, $M_\max$ největší párování v $G$
	- jistě $|M_\max|\leq |C_\min|$
	- nechť $f$ je maximální tok v té síti a $R$ minimální řez
	- dle minimaxové věty $w(f)=c(R)$
	- BÚNO $f$ má celočíselné hodnoty
	- definujme $M_f:=\set{\set{x,y}\in E:f(xy)\gt 0}$
		- jistě $M_f$ párování v $G$, navíc $|M_f|=w(f)$
	- definujme $C_R:=\set{x\in A:zx\in R}\cup\set{y\in B:ys\in R}$
		- pozorování: $R$ neobsahuje žádnou hranu z $A$ do $B$
		- jistě $C_R$ je vrcholové pokrytí $G$
		- kdyby $C_R$ nebylo pokrytí, tak existuje nepokrytá hrana $\set{x,y}\in E$, potom cesta $z\to x\to y\to s$ je ve sporu s tím, že $R$ je řez
		- navíc $|C_R|=|R|=c(R)$
		- máme $|C_\min|\leq |C_R|=c(R)=w(f)=|M_f|\leq |M_\max|\leq |C_\min|$
- pozorování: v bipartitním grafu s partitami $A,B$ má každé párování velikost nejvýše $|A|$ (i nejvýše $|B|$)
- df: pro graf $G=(V,E)$ a množinu $X\subseteq V$ označím $N(X):=\set{y\in V\setminus X\mid \exists x\in X:\set{x,y}\in E}$
- věta (Hallova věta … bipartitní grafová verze): nechť $G$ je bipartitní graf s partitami $A,B$, potom $G$ má párování velikosti $|A|$ $\iff\underbrace{\forall X\subseteq A:|N(X)|\geq |X|}_{\text{„Hallova podmínka“}}$
- dk:
	- $\implies$
		- pokud existuje párování velikosti $|A|$, tak pro každou $X\subseteq A$ existuje $|X|$ vrcholů spárovaných s $X$, ty patří do $N(X)$, tedy $|N(X)|\geq |X|$
	- $\impliedby$
		- nechť $M$ je největší párování v $G$
		- pro spor nechť $|M|\lt|A|$
		- dle K-E věty: existuje pokrytí $C$, kde $|C|=|M|\lt |A|$
		- $C_A:= C\cap A$
		- $C_B:=C\cap B$
		- $X:=A\setminus C_A$
		- zjistím, že $N(X)\subseteq C_B$
		- navíc $|X|=|A|-|C_A|\gt |C_B|\geq |N(x)|$
		- to je spor s Hallovou podmínkou$\quad\square$
- další verze Hallovy věty
	- df: systém různých reprezentantů (SRR) v hypergrafu $H=(V,E)$ je funkce $r:E\to V$ taková, že
		- $\forall e\in E: r(e)\in e$
		- $\forall e,v\in E:e\neq f\implies r(e)\neq r(f)$ … tj. $r$ je prostá
	- $r(e)$ … „reprezentant hypergrany $e$“
	- analogie s předsedy spolků
	- jakmile uvnitř hypergrafu je množina čtyř hyperhran, které ve svém sjednocení mají tři vrcholy, tak nemůžu najít systém různých reprezentantů
		- platí to obecně pro množinu $k$ hyperhran – když budou mít ve sjednocení méně než $k$ vrcholů, tak nenajdu SRR
		- implikace platí i obráceně, lze vyslovit jako větu
	- Hallova věta (hypergrafová verze): Hypergraf $H=(V,E)$ má SRR, právě když $\forall F\subseteq E:\left|\bigcup_{e\in F} e\right|\geq |F|$
	- důkaz
		- nechť $H=(V,E)$ je hypergraf, nechť $I_H$ je jeho graf incidence
		- pozorování: $H$ má SRR $\iff$ $I_H$ má párování velikosti $|E|$
		- pozorování: Hallova podmínka pro $H$: $\forall F\subseteq E: \left|\bigcup_{e\in F}e\right|\geq |F|\iff$ bipartitní Hallova podmínka pro $I_H$ a partitu $E$

### Hranová a vrcholová souvislost grafů

- mějme $G=(V,E)$ neorientovaný konečný graf, přičemž $|V|\geq 2$
- df
	- pro $F\subseteq E:G-F:=(V,E\setminus F)$
	- $F\subseteq E$ je hranový řez v $G$, pokud $G-F$ je nesouvislý
	- $G$ je hranově $k$-souvislý, pokud neobsahuje žádný hranový řez velikosti menší než $k$
- pozorování: $G$ je hranově 1-souvislý $\iff$ $G$ je souvislý
- pozorování: $G$ je hranově $k$-souvislý, $k\geq 2\implies G$ je hranově $(k-1)$-souvislý
- df: stupeň hranové souvislosti (nebo jen hranová souvislost) grafu $G$, značený $k_e(G)$, je největší $k$ takové, že $G$ je hranově $k$-souvislý
- pozorování: $k_e(G)=$ velikost nejmenšího hranového řezu v $G$
- df: pokud $x,y$ jsou různé vrcholy $G$, tak hranový $xy$-řez je množina $F\subseteq E$ taková, že $x$ a $y$ jsou v různých komponentách $G-F$
- věta (Menger, hranová $xy$-verze): pro dva různé vrcholy $x,y$ grafu $G$ platí, že $G$ obsahuje $k$ hranově disjunktních cest z $x$ do $y$ $\iff G$ neobsahuje hranový $xy$-řez velikosti menší než $k$
- důkaz
	-  $\implies:$ pokud máme $k$ hranově disjunktních cest z $x$ do $y$, tak každý hranový $xy$-řez musí obsahovat aspoň jednu hranu z každé té cesty
	- $\impliedby$
		- nechť $G$ neobsahuje hranový $xy$-řez velikosti menší než $k$
		- vyrobíme tokovou síť $(V,\vec E,x,y,c)$, kde $\vec E=\set{uv,vu\mid \set{u,v}\in E},\; \forall e\in \vec E: c(e)=1$
		- pozorování: v té síti není žádný řez velikosti menší než $k$
		- tedy v té síti existuje tok velikosti aspoň $k$
		- nechť $f$ je celočíselný maximální tok
		- navíc mezi všemi celočíselnými maximální toky volme $f$ tak, aby množina $\underbrace{\set{e\in\vec E:f(e)=1}}_{S(f)}$ byla co nejmenší
		- pozorování: $S(f)$ neobsahuje žádný orientovaný cyklus jinak spor s minimalitou $S(f)$
		- pomocí $S(f)$ vyrobím k hranově disjunktních cest z $x$ do $y$ takto:
			- opakuj $k$-krát
				- začni v $x$
				- jdi po hranách z $S(f)$, dokud nedojdeš do $y$
					- tenhle krok bude konečný, protože $S(f)$ neobsahuje orientované cykly
				- použité hrany odstraň z $S(f)$
- věta (Menger, globální hranová verze): graf $G$ je hranově $k$-souvislý $\iff$ mezi každými dvěma různými vrcholy existuje $k$ hranově disjunktních cest
- dk: $G$ je hranově $k$-souvislý $\iff$ neexistuje hranový řez velikosti menší než $k\iff\forall x,y$ různé: neexistuje hranový $xy$-řez velikosti menší než $k\iff\forall x,y$ různé: $\exists k$ hranově disjunktních cest z $x$ do $y$ $\quad\square$
- df: $G=(V,E),\;A\subseteq V,\; G-A=(V\setminus A,E\cap {V\setminus A\choose 2})$; $A\subseteq V$ je vrcholový řez, pokud $G-A$ je nesouvislý
- pozorování: $K_n$ nemá vrcholový řez
- df: graf $G$ je vrcholově $k$-souvislý, pokud má aspoň $k+1$ vrcholů a neobsahuje žádný vrcholový řez velikosti menší než $k$
- df: vrcholová souvislost grafu $G$, značená $k_v(G)$, je největší $k$ takové, že $G$ je vrcholově $k$-souvislý
- pozorování: $k_v(K_n)=n-1$
- pozorování: $G$ není úplný … $k_v(G)=$ velikost nejmenšího vrcholového řezu
- df: pro dva různé vrcholy $x,y\in V$, vrcholový $xy$-řez je množina $A\subseteq V\setminus\set{x,y}$ taková, že $x$ a $y$ jsou v různých komponentách $G-A$
- df: dvě cesty v $G$ z $x$ do $y$ jsou navzájem vnitřně vrcholově disjunktní (VVD), pokud nemají žádný společný vrchol kromě $x,y$
- pozorování: dvě VVD cesty z $x$ do $y$ jsou i hranově disjunktní
- věta ($xy$-verze Mengerovy věty pro vrcholovou souvislost): nechť $G=(V,E)$ je graf, nechť $x,y$ jsou různé **nesousední** vrcholy, nechť $k\in\mathbb N$; potom $G$ obsahuje $k$ navzájem VVD cest z $x$ do $y\iff G$ neobsahuje vrcholový $xy$-řez velikosti $\lt k$
- dk:
	- $\implies$ zřejmá
	- $\impliedby$
		- nechť $G$ nemá vrcholový $xy$-řez velikosti $\lt k$
		- vyrobíme síť $\mathcal S$ takto
			- za každý vrchol $u\in V$ dáme do $\mathcal S$ dva vrcholy $u^+,u^-$ a hranu $u^+u^-$ s kapacitou 1
			- za každou hranu $\set{u,v}\in E$ dáme do $\mathcal S$ dvě orientované hrany $u^-v^+$ a $v^-u^+$ s kapacitami "$\infty$"
			- zdroj: $x^-$, stok: $y^+$
		- tvrdím, že $\mathcal S$ nemá řez kapacity $c\lt k$
			- sporem: nechť takový řez existuje
			- potom všechny jeho hrany jsou tvaru $u^+u^-$ pro nějaké $u\in V$ a odpovídající vrcholy v $G$ tvoří vrcholový $xy$-řez velikosti $c\lt k$, což je spor
		- podle minimaxové věty o toku a řezu v $\mathcal S$ existuje tok velikosti $\geq k$, BÚNO je ten tok celočíselný, říkejme mu $f$
		- z existence takového $f$ plyne, že $\mathcal S$ obsahuje $k$ hranově disjunktních cest z $x^-$ do $y^+$ (viz hranová verze), označme je $\vec P_1,\dots,\vec P_k$
		- ty cesty $\vec P_1,\dots,\vec P_k$ jsou i vnitřně vrcholově disjunktní, protože každá cesta (orientovaná) z $x^-$ do $y^+$ v $\mathcal S$, která obsahuje vrchol $u^+$ nebo $u^-$ pro nějaké $u\in V\setminus\set{x,y}$, musí obsahovat i hranu $u^+u^-$
		- když v cestách $\vec P_1,\dots,\vec P_k$ nahradíme každou hranu tvaru $u^+u^-$ jedním vrcholem $u$, tak dostaneme $k$ VVD cest z $x$ do $y$ v $G\quad\square$
- lemma: nechť $G=(V,E)$ je graf s hranou $e=\set{x,y}$; nechť $G^-:=(V,E\setminus\set e)$; potom $k_v(G^-)\geq k_v(G)-1$
- dk:
	- nechť $A$ je nejmenší vrcholový řez v $G^-$ 
	- potom $k_v(G^-)=|A|$
	- chceme $k_v(G)\leq k_v(G^-)+1=|A|+1$
	- rozlišme případy
		- pokud existuje komponenta $G^--A$, která neobsahuje $x$ ani $y$, tak $A$ je vrcholový řez v $G$, tedy $k_v(G)\leq |A|$
		- jinak má $G^--A$ 2 komponenty, jedna obsahuje $x$ (říkejme jí $G^-_x$), druhá $y$ ($=: G_y^-$)
		- (zbytek viz záznam)
- věta (vrcholová globální verze Mengerovy věty): $G$ je vrcholově $k$-souvislý $\iff$ mezi každými dvěma různými vrcholy $x,y$ existuje $k$ navzájem VVD cest
- dk:
	- pro $K_n$ věta zjevně platí (jedna cesta je přímá, další vždy přes jiný vrchol, těch je $n-2$)
	- nechť $G$ není úplný (byť by tahle větev důkazu fungovala i pro $K_n$)
		- $\impliedby:$ mezi každými dvěma vrchol je $k$ VVD cest $\implies$ G má $\geq k+1$ vrcholů, žádný řez velikosti $\lt k\implies G$ je $k$-souvislý
		- $\implies:$ nechť $x,y$ jsou různé vrcholy; případy
			- $\set{x,y}\notin E$ … viz $xy$-verze M. věty
			- $\set{x,y}\in E:$ nechť $G^-:=(V,E\setminus\set e)$
				- podle lemmatu: $k_v(G^-)\geq k-1$
				- podle $xy$-verze M. věty pro $G^-$ existuje $k-1$ VVD cest $x\to y$
				- přidám k nim hranu $e$ a mám $k$ VVD cest $x\to y\quad\square$
- konvence: „$k$-souvislý graf“ znamená „vrcholově $k$-souvislý“
- df: přidání ucha ke grafu $G=(V,E)$ je tato operace
	- zvol dva různé vrcholy $x,y\in V$
	- pro $d\geq 0$ přidej vrcholy $z_1,z_2,\dots,z_d$
	- přidej hranu cesty $xz_1z_2\dots z_dy$
- věta („lemma o uších“): graf $G$ je 2-souvislý $\iff G$ se dá vyrobit z kružnice pomocí přidávání uší
- důkaz
	- $\impliedby$ kružnice je 2-souvislá a přidání ucha nevytvoří řez velikosti $\leq 1$
	- $\implies$
		- nechť $G=(V,E)$ je 2-souvislý, nechť $C$ je libovolná kružnice v $G$, nechť $G_\max=(V_\max,E_\max)$ je největší podgraf $G$, který se dá vyrobit přidáváním uší k $C$
		- tvrdíme, že $G_\max=G$
		- kdyby ne:
			- $V_\max=V,\,E_\max\subsetneq E:$ spor s maximalitou $G_\max$, protože přidání hrany je přidání ucha
			- $V_\max\subsetneq V:G$ je souvislý, tak $\exists e=\set{xy}\in E$ taková, že $x\in V_\max$ a $y\notin V_\max$
			- $G-x$ je souvislý, protože $G$ je 2-souvislý
			- takže bude existovat ještě další cesta do $V_\max$
			- tato cesta + hrana $xy$ = další ucho

## Cayleyho vzorec

- strom … souvislý graf bez kružnic
- $s_n:=$ počet stromů na množině vrcholů $[n]:=\set{1,2,\dots,n}$
- $s_1=1,\;s_2=1,\;s_3=3,\;s_4 = 16,\;s_5 = 125$
- věta (Cayleyho vzorec, Borchardt)
	- $s_n=n^{n-2}$
- důkaz
	- nebudu počítat stromy, ale kořenové stromy
	- df: kořenový strom je strom, ve kterém se jeden vrchol určil jako kořen a všechny hrany se zorientovaly směrem ke kořeni
	- $k_n:=$ počet kořenových stromů
	- pozorování: $k_n=n\cdot s_n$
	- pozorování: pokud ve stromě zorientuji hrany tak, aby z každého vrcholu odcházela nejvýš jedna hrana, tak potom existuje právě jeden vrchol („kořen“), z něhož žádná hrana neodchází, a navíc všechny hrany jsou orientované směrem ke kořeni
	- df: povykos (postup vytváření kořenového stromu) je posloupnost $n-1$ orientovaných hran $(e_1,e_2,\dots,e_{n-1})$ na vrcholech $[n]$ taková, že $([n],\set{e_1,\dots,e_{n-1}})$ je kořenový strom
	- $p_n:=$ počet povykosů
	- pozorování: $p_n=(n-1)!\cdot k_n$
	- pozorování (pravidla): posloupnost orientovaných hran $(e_1,e_2,\dots,e_{n-1})$ je povykos $\iff\forall k\in[n-1]:$
		- hrana $e_k$ spojuje vrcholy z různých komponent grafu tvořeného hranami $e_1,\dots,e_{k-1}$
		- hrana $e_k$ vychází z vrcholu, z něhož nevychází žádná z hran $e_1,\dots,e_{k-1}$
	- chci vyrobit povykos $(e_1,\dots,e_{n-1})$
		- mám $n\cdot (n-1)$ možností, jak zvolit $e_1$
			- vybírám dva vrcholy, mezi kterými povedu hranu
		- mám $n\cdot (n-2)$ možností, jak zvolit $e_2$, když už znám $e_1$
			- mám $n$ možností, jak zvolit konec hrany
			- začátek hrany musí být v jiné komponentě než konec
			- je tam $n-2$ komponent, které můžu zvolit (dohromady je komponent $n-1$, z toho jednu zvolit nemůžu)
			- v každé komponentě je „kořen komponenty“ (vrchol, z nějž žádná hrana nevychází)
			- hrana musí nutně začínat v „kořeni komponenty“ (podle druhého pravidla)
			- tedy mám $n-2$ možností, jak zvolit začátek hrany
		- pokud už jsem vybral $e_1,\dots,e_{k-1}$ v souladu s oběma pravidly, tak mám $n\cdot (n-k)$ možností, jak vybrat $e_k$
			- $n$ … vyberu konec $e_k$
			- $n-k$ … vyberu začátek v kořeni nějaké komponenty neobsahující konec $e_k$
			- $p_n=n\cdot(n-1)\cdot n\cdot(n-2)\cdot\ldots\cdot n\cdot 1=$
			- $=\prod_{k=1}^{n-1}n(n-k)=n^{n-1}(n-1)!$
			- $k_n=\frac{p_n}{(n-1!)}=n^{n-1}$
			- $s_n=\frac{k_n}{n}=n^{n-2}\quad\square$

## Počítání dvěma způsoby

- pozorování: když $G=(V,E)$ je bipartitní graf s partitami $A,B$, tak $|E|=\sum_{x\in A}\deg(x)=\sum_{y\in B}\deg(y)$
- příklad: fakulta má 1000 studujících, 50 předmětů, každý studující má zapsáno $\geq 10$ předmětů; dokažte, že existuje předmět, který má zapsáno $\geq 200$ lidí
	- řešení: sporem, nechť každý předmět má zapsáno $\lt 200$ lidí
	- počítejme počet dvojic $(x,y)$, kde $x$ je studující, $y$ je předmět, $x$ má zapsán předmět $y$, dvěma způsoby
		- první způsob: těch dvojic je $\geq 1000\cdot 10$
		- druhý způsob: těch dvojic je $\lt 50\cdot 200$
	- to je spor
- značení
	- $\mathcal P([n])$ … množina všech podmnožin množiny $[n]$
	- ${[n]\choose k}$ … množina všech $k$-prvkových podmnožin $[n]$
- df: antiřetězec v $\mathcal P([n])$ je množina $\mathcal A\subseteq\mathcal P([n])$ taková, že $\forall M,M'\in\mathcal A:M\neq M'\implies M\not\subseteq M'\land M'\not\subseteq M$
- věta (Sperner): největší antiřetězec v $\mathcal P([n])$ má velikost ${n\choose\lfloor n/2\rfloor}={n\choose\lceil n/2\rceil}$
- důkaz
	- antiřetězec velikosti ${n\choose\lfloor n/2\rfloor}$ je např. ${[n]\choose\lfloor n/2\rfloor}$
	- dokažme, že neexistuje větší antiřetězec
		- nechť $\mathcal A$ je aniřetězec, označme $\mathcal A=\set{A_1,A_2,\dots,A_k}$, kde $k=|\mathcal A|$, chceme $k\leq{n\choose\lfloor n/2\rfloor}$
		- df: nasycený řetězec v $\mathcal P([n])$ je posloupnost $M_0,M_1,\dots,M_n\subseteq[n]$, kde $M_0\subseteq M_1\subseteq\dots\subseteq M_n\subseteq [n]$ a $|M_i|=i$
		- máme $n!$ nasycených řetězců v $\mathcal P([n])$
			- začínám s prázdnou množinou, postupně do ní přidávám prvky
			- mám $n-i+1$ možností, jak do ní přidat $i$-tý prvek
		- každý nasycený řetězec obsahuje nejvýš jednu množinu $\mathcal A$
		- počítejme dvěma způsoby dvojice $(A,\mathcal R)$, kde $A\in\mathcal A$, $\mathcal R$ je nasycený řetězec, $A\in\mathcal R$
			- první způsob: dvojic je $\leq n!$
			- druhý způsob: pro $A\in\mathcal A$ mám $|A|!\cdot(n-|A|)!$ nasycených řetězců obsahujících $A$
				- mám množinu $A$
				- mám $|A|$ možností, který prvek z ní odeberu
				- postupně odebírám prvky, až se dostanu k prázdné množině → $|A|!$ možností
				- podobně $(n-|A|)!$ možností, jak dotvořit řetězec přidáváním prvků
			- $n!\geq\sum_{A\in\mathcal A}|A|!(n-|A|)!\implies 1\geq\sum_{A\in\mathcal A}\frac{|A|!(n-|A|)!}{n!}=\sum_{A\in\mathcal A}\frac1{n\over|A|}\geq\sum\frac1{n\choose\lfloor}$
			- pokračování viz záznam
- věta: Nechť $G=(V,E)$ je graf na $n$ vrcholech, který neobsahuje $C_4$ jako podgraf. Potom $|E|\leq O(n^{3/2})$.
- důkaz:
	- nechť $G=(V,E)$ je graf bez $C_4$, $|V|=n$
	- označme $H$ počet dvojic $(x,\set{y,z})$ takových, že $x,y,z\in V$, $y\neq z$, $x$ je soused $y$ i $z$
	- počítejme $H$ dvěma způsoby
		- pro dané $x\in V$ mám přesně ${\deg x\choose 2}$ možností, jak zvolit $y$ a $z$
			- tedy $H=\sum_{x\in V}{\deg x\choose 2}\geq\sum_{x\in V}\frac{(\deg x-1)^2}2$
		- pro dané $\set{y,z}\in{V\choose 2}$ existuje nejvýše jeden společný soused $x\in V$, jinak by $G$ obsahoval $C_4$
			- tedy $H\leq{n\choose 2}\leq\frac{n^2}2$
	- tedy $\frac{n^2}2\geq \sum_{x\in V}\frac{(\deg x-1)^2}2$
	- z toho plyne, že $n^2\geq \sum_{x\in V}{(\deg x-1)^2}$
	- chci $|E|=\frac 12\sum_{x\in V}\deg x\leq O(n^{3/2})$
	- uvažme funkci $f(x)=(x-1)^2$, ta je konvexní, tedy pro každé $x_1,x_2,\dots,x_n\in\mathbb R: f(\frac{x_1+\dots+x_n}n)\leq\frac{f(x_1)+f(x_2)+\dots+f(x_n)}n$
	- tedy $n\geq\frac{\sum_{x\in V}{(\deg x-1)^2}}n\geq\left(\frac{\sum_{x\in V}\deg x}n-1\right)^2$
		- počet hran je polovina ze součtu stupňů
	- $\sqrt n\geq\frac{2|E|}n-1$
	- $n^{3/2}\geq 2|E|-n$
	- $\frac12(n^{3/2}+n)\geq|E|\quad\square$
- poznámka: odhad je těsný
	- mějme incidenční graf konečné projektivní roviny řádu $k$
	- …

## Ramseyovy věty

- df: klika v grafu $G=(V,E)$ je množina vrcholů taková, že každé dva jsou spojené hranou
- df: nezávislá množina v grafu $G=(V,E)$ je množina vrcholů taková, že žádné dvě vrcholy nejsou spojené hranou
- motivační tvrzeníčko: v každém grafu na 6 vrcholech existuje klika velikosti 3 nebo nezávislá množina velikosti 3
	- vezmu vrchol $v$ – zbývá pět vrcholů
	- $v$ je buď spojený se třemi vrcholy, nebo je nespojený se třemi vrcholy
	- pokud je spojený, dívám se na hrany mezi nimi
- ekvivalentně: když v úplném grafu $K_6$ obarvím hrany červeně a modře, tak vždy vznikne jednobarevný trojúhelník (červeně jsou hrany původního grafu na šesti vrcholech, modře jsou nehrany)
- Ramseyova věta, grafová verze: $\forall k\in\mathbb N\;\forall\ell\in\mathbb N\;\exists N\in\mathbb N$ takové, že $\forall$ graf $G$ na $N$ vrcholech obsahuje kliku velikosti $k$ nebo nezávislou množinu velikosti $\ell$
- označme $R(k,\ell)$ nejmeší $N$, pro které platí závěr té věty
- už víme: $R(3,3)\leq 6$
- pozorování: $R(3,3)=6$, protože $C_5$ neobsahuje ani kliku, ani nezávislou množinu velikosti 3
- $R(k,\ell)$ se nazývá Ramseyovo číslo
- důkaz indukcí podle $k+\ell$
	- pozorování: $R(k,1)=1=R(1,\ell)$
	- pozorování: $R(k,2)=k=R(2,k)$
	- mějme $k\geq 3,\,l\geq 3$, definujme $N:=R(k,\ell-1)+R(k-1,\ell)$
	- nechť máme dán graf $G$ na $N$ vrcholech
	- nechť $x$ je libovolný vrchol $G$
	- označme $S$ množinu sousedů vrcholu $x$ a $T=V\setminus (S\cup\set{x})$
	- protože $|S|+|T|=N-1=R(k,\ell-1)+R(k-1,\ell)-1$, tak platí buď $|S|\geq R(k-1,\ell)$, nebo $|T|\geq R(k,\ell-1)$
	- předpokládejme, že $|S|\geq R(k-1,\ell)$, označme $G_S$ podgraf $G$ indukovaý $S$
	- tedy $G_S$ obsahuje kliku velikosti $k-1$ nebo nezávislou množinu velikosti $\ell$
	- pokud $G_S$ obsahuje nezávislou množinu velikosti $\ell$, tak i $G$ ji obsahuje, hotovo
	- pokud $G_S$ obsahuje kliku velikosti $k-1$, tak ta klika spolu s $x$ tvoří kliku velikosti $k$ v $G$, hotovo
	- případ $|T|\geq R(k,\ell-1)$ je analogický
	- $V(G)=S\cup T\cup\set{x}$
- důsledek (symetrická verze Ramseyovy věty): $\forall m\;\exists N\;\forall G$ na $N$ vrcholech má kliku nebo nezávislou množinu velikosti $m$
- ekvivalentní 2-barevná verze Ramseyovy věty: $\forall m\;\exists N\;\forall$obarvení hran $K_N$ červeně a modře existuje jednobarevná klika velikosti $m$
- věta (vícebarevná verze Ramseyovy věty): $\forall b\in\mathbb N\;\forall m\in\mathbb N\;\exists N\in\mathbb N\;\forall$obarvení hran $K_N$ pomocí $b$ barev existuje množina $m$ vrcholů taková, že všechny hrany mezi nimi mají stejnou barvu
	- $R^*_b(m)$ … nejmenší $N$ s touto vlastností
- připomenutí: $R(k,\ell):=$ nejmenší $N$ takové, že každé obarvení hran $K_n$ červeně a modře obsahuje modrou kliku velikosti $k$ nebo červenou kliku velikosti $\ell$
- $R^*_2(m)=R(m,m)$
- důkaz
	- postupujme indukcí podle $b$
	- pro $b=1: R_1^*(m)=m$
	- pro $b=2:R^*_2(m)=R(m,m)$
	- nechť $b\gt 2$
		- nechť $N=R(m,R_{b-1}^*(m))$
		- mějme obarvení $K_N$ pomocí $b$ barev
		- nechť ty barvy jsou 1) modrá a 2) $b-1$ odstínů červené
		- Ramseyova věta pro 2 barvy říká, že v tom obarvení buď existuje modrá klika velikosti $m$ (jsem hotov), nebo existuje klika $X$ velikosti $R^*_{b-1}(m)$ taková, že všechny barvy hran mezi vrcholy $X$ jsou odstíny červené
		- $X$ indukuje úplný graf na $R^*_{b-1}$, jehož hrany jsou obarveny pomocí $b-1$ barev, tedy v něm je jednobarevná klika velikosti $m$ $\square$
- značení
	- ${X\choose p}$ … množina $p$-prvkových podmnožin $X$
	- $K_N^{(p)}$ … $p$-uniformní úplný hypergraf, což je hypergraf $([N],{[N]\choose p})$
		- tedy $K_N=K_N^{(2)}$
- pro $b\in\mathbb N:b$-obarvení $K_N^{(p)}$ je funkce ${[N]\choose p}\to[b]$
- pro dané $b$-obarvení $\beta$ hypergrafu $K_N^{(p)}$ řeknu, že množina $X\subseteq[N]$ je jednobarevná (v obarvení $\beta$), pokud $\beta$ přiřazuje všem množinám v ${X\choose p}$ tu samou barvu
- $K^{(p)}_\infty$ … nekonečný hypergraf $(\mathbb N,{\mathbb N\choose p})$
- věta (Ramsey, konečná verze): $\forall p\in\mathbb N\;\forall b\in\mathbb N\;\forall m\in\mathbb N\;\exists N\in\mathbb N\;\forall\,b$-obarvení $K_N^{(p)}$ $\exists$ jednobarevná $m$-prvková podmnožina $[N]$
- věta (Ramsey, nekonečná verze): $\forall p\in\mathbb N\;\forall b\in\mathbb N\;\forall\,b$-obarvení $K_\infty^{(p)}\;\exists$ nekonečná jednobarevná podmnožina $\mathbb N$
- $p=1$
	- pro dané $b,m$ stačí $N=b(m-1)+1$
	- princip holubníku
- dokážeme, že konečnou verzi lze odvodit z nekonečné
- věta (Kőnigovo lemma): nechť $T$ je strom s nekonečně mnoha vrcholy, který neobsahuje žádný vrchol nekonečného stupně, nechť $x_0$ je libovolný vrchol $T$; potom $T$ obsahuje nekonečnou cestu začínající v $x_0$
- důkaz
	- zakořeňme $T$ ve vrcholu $x_0$
	- indukcí definujme posloupnost vrcholů $x_0,x_1,x_2,\dots$ tak, že $x_0,x_1$ tvoří cestu a pro $\forall i\in\mathbb N_0:$ podstrom zakořeněný v $x_i$ má nekonečně mnoho vrcholů
	- už máme $x_0$
	- nechť už máme $x_0,x_1,\dots,x_n$, nechť $y_1,y_2,\dots,y_k$ jsou děti $x_n$
	- aspoň jeden vrchol $y_i$ je kořenem nekonečného podstromu
	- tedy definujeme $x_{n+1}:=y_i$
	- posloupnost $x_0,x_1,x_2,\dots$ tvoí nekonečnou cestu v $T$
- tvrzení: z nekonečné verz Ramseyovy věty plyne konečná verze
- důkaz
	- nechť neplatí konečná Ramseyova věta, tedy $\exists p\;\exists b\;\exists m\;\forall N\;\exists\,b$-obarvení $K_N^{(p)}$ neobsahující jednobarevnou podmnožinu velikosti $m$
	- řeknu, že $b$-obarvení $\beta$ hypergrafu $K_N^{(p)}$ je záludné, pokud v něm neexistuje jednobarevná podmnožina $[N]$ velikosti $m$
	- $Z_N$ … množina záludných obarvení $K_N^{(p)}$
	- řeknu, že $b$-obarvení $\gamma\in Z_{N+1}$ rozšiřuje $b$-obarvení $\beta\in Z_N$, pokud pro každou $h\in{[N]\choose p}$ platí $\gamma(h)=\beta(h)$
	- pozorování: každé $\gamma\in Z_{n+1}$ rozšiřuje právě jedno $\beta\in Z_N$
	- definujme strom $T$ na vrcholech $Z_1\cup Z_2\cup\dots=\bigcup_{N=1}^\infty Z_N$
	- $\set{\beta,\gamma}\in E(T)\iff\gamma$ rozšiřuje $\beta$ nebo naopak
	- v tom stromě existuje nekonečná cesta $\beta_1,\beta_2,\beta_3,\dots$, kde $\beta_N\in Z_N$ (podle Kőnigova lemmatu)
	- definujme obarvení $\beta:{\mathbb N\choose p}\to[b]$ takto: nechť máme dánu množinu $h\in{\mathbb N\choose p}$, volme $N\in\mathbb N$ takové, že $h\subseteq [N]$ a definujme $\beta(h):=\beta_N(h)$
	- tvrdím, že $\beta$ je záludné obarvení pro $K_\infty^{(p)}$
	- kdyby ne, tak $\beta$ má nějakou jednobarevnou $m$-prvkovou množinu $X\subseteq\mathbb N$
	- volme $N$ tak, že $X\subseteq[N]$
	- potom $\beta$ obarví ${X\choose p}$ stejně jako $\beta_N$, ale $\beta_N$ je záludné pro $K_N^{(p)}$, tedy $X$ v něm není jednobarevná
	- tedy $\beta$ je záludné pro $K_\infty^{(p)}$, a tedy nekonečná Ramseyova věta neplatí $\quad\square$

## Samoopravné kódy

- naše omezení
	- nad abecedou $\mathbb Z_2$
	- informace je rozdělená na slova pevné délky $k$, každé se zakóduje do slova délky $n$
	- chyby při přenosu nemění počet symbolů
- příklady
	- trojnásobné opakování
		- 0 → 000
		- 1 → 111
		- dekódování: 011 → 111 → 1
	- kontrola parity
		- když posílám 3 bity, tak 4. se rovná XORu těch prvních tří (tedy součtu nad $\mathbb Z_2$)
- df: $\mathbb Z_2^n$ … množina slov délky $n$ nad $\mathbb Z_2$, slova píšu jako řádkové vektory: $x=(x_1,x_2,\dots,x_n)$
- $\oplus$ … sčítání nad $\mathbb Z_2$
- $x\oplus y=(x_1\oplus y_1,\dots,x_n\oplus y_n)$
- $\underline 0$ … nulový vektor v $\mathbb Z_n^2$
- Hammingova vzdálenost $d(x,y):=$ počet $i$ takových, že $x_i\neq y_i$
- Hammingova váha $\Vert x\Vert:=$ počet $i$ takových, že $x_i\neq 0$
- pozorování
	- $\Vert x\Vert=d(x,0)$
	- $d(x,y)=\Vert x\oplus y\Vert$
- df: kód je podmnožina $\mathbb Z_2^n$ (pro nějaké $n$)
- pro kód $C\subseteq\mathbb Z_2^n$ je minimální vzdálenost $\Delta(C):=\min_{x, y\in C,\;x\neq y} d(x,y)$
- $(n,k,d)$-kód je množina $C\subseteq\mathbb Z_2^n$ taková, že $|C|=2^k$ a $\Delta(C)=d$
- např.
	- $C_1=\set{000,111}$ je $(3,1,3)$-kód
	- $C_2=\set{x\in\mathbb Z_2^4;\Vert x\Vert\text{ je sudá}}$ je $(4,3,2)$-kód … tohle odpovídá kontrole parity
- kód $C\in\mathbb Z_2^n$ je lineární, pokud je to vektorový podprostor $\mathbb Z_2^n$ (ekvivalentně $\underline 0\in C$ a $\forall x,y\in C:x\oplus y\in C$)
- $C_1,C_2$ jsou lineární
- pro lineární $(n,k,d)$-kód je $k$ jeho dimenze
- $k$ taky odpovídá počtu bitů informace, které jsem schopný zakódovat do jednoho kódového slova
- pozorování: pokud $C$ je lineární, tak $\Delta(C)=\min_{x\in C\setminus{\underline 0}} d(x,\underline 0)=\min_{x\in C\setminus\set{\underline 0}}\Vert x\Vert$, protože pokud $x,y\in C$ jsou takové, že $d(x,y)=\Delta(C)$, tak potom $d(x,y)=d(x\oplus y,\underline 0)$
- nechť $C$ je $(n,k,d)$-kód pro $k\in\mathbb N$, tak kódování pro $C$ je bijekce $\mathbb Z_2^k\to C$
- pro lineární $(n,k,d)$-kód $C$ je generující matice $G\in\mathbb Z_2^{k\times n}$, jejíž řádky tvoří bázi $C$
- tvrzení: pokud $G$ je generující matice $(n,k,d)$-kódu $C$, tak zobrazení, které vektoru $x=(x_1,x_2,\dots,x_k)\in\mathbb Z_2^k$ přiřadí vektor $xG$ je kódování pro $C$
- pro $C_1:$
	- $(0)(111)=(000)$
	- $(1)(111)=(111)$
- pro $C_2:(x_1,x_2,x_3)G_2=(x_1,x_2,x_3,x_1\oplus x_2\oplus x_3)$
- dk
	- uvažujeme zobrazení $f:\mathbb Z_2^k\to \mathbb Z_2^n$ definované $f(x)=xG$
	- stačí ověřit
		1) $\forall x\in\mathbb Z_2^k:f(x)\in C$
		2) $f$ je prosté
	- ověřme 1)
		- nechť $r_1,\dots,r_k$ jsou řádky $G$, tedy $r_1,\dots,r_k\in C$
		- potom pro každé $x=(x_1,\dots,x_k)$ platí $xG=x_1r_1\oplus x_2r_2\oplus\dots\oplus x_kr_k$, což je lineární kombinace prvků $C$, tedy prvek $C$
	- ověřme 2)
		- kdyby $\exists x\neq x'\in\mathbb Z_2^k:f(x)=f(x')$
		- tak $xG=x'G\iff \underbrace{(x-x')}_{\neq 0}G=\underline 0$, což nemůže nastat, protože řádky $G$ jsou lineárně nezávislé
- df: dekódování $(n,k,d)$-kódu $C$ je funkce $g:\mathbb Z_2^n\to C$ taková, že $\forall x\in\mathbb Z_2^n:d(x,g(x))=\min_{y\in C}d(x,y)$
- pro $C_1:g(x)$ vrací 000 nebo 111 podle $\Vert x\Vert$
- pro $C_2:$ přepneme první bit, pokud nesedí parita
- df: pro $x,y$ definuji $\braket{x,y}=x_1y_1\oplus\dots\oplus x_ny_n$
- pozor, může se stát, že pro $x\neq 0:\braket{x,x}=0$
- $C^\perp:=\set{y\in\mathbb Z_2^n:\forall x\in C:\braket{x,y}=0}$ … duální kód k $C$
- fakt
	- pokud $C$ je podprostor dimenze $k$, tak $C^\perp$ je podprostor dimenze $n-k$
	- $(C^\perp)^\perp=C$, pokud $C$ je podprostor $\mathbb Z_2^n$

### Dekódování

- postup
	- máme $x\in\mathbb Z_2^{k}$
	- kódováním pomocí funkce $f$ dostaneme $y\in C\subseteq\mathbb Z_2^n$
	- přenosem dostaneme $\tilde y\in C$
	- dekódováním pomocí funkce $g$ dostaneme $\bar y\in C$
	- z $\bar y$ pomocí funkce $f^{-1}$ dostaneme $\bar x\in\mathbb Z_2^{k}$
- $f$ je bijekce mezi $\mathbb Z_2^{k}$ a $C$
- $(n,k,d)$-kód
- pozorování: pokud se při přenosu změní nejvýše $d-1$ bitů, tak poznám, zda došlo k chybě
- pozorování: pokud se při přenosu změní nejvýše $\left\lfloor\frac{d-1}2\right\rfloor$ bitů, tak jsem schopen chybu jednoznačně opravit
- df: nechť je $C$ lineární $(n,k,d)$-kód, pak kontrolní matice kódu $C$ je matice, jejíž řádky tvoří bázi $C^\perp$
- pozorování: kontrolní matice lienárního $(n,k,d)$-kódu má $n-k$ řádků a $n$ sloupců
- příklad
	- $C_1=\set{000,111}$, lineární $(3,1,3)$-kód
	- $C_1^\perp=\set{000,110,101,011}$
	- $C_1$ má kontrolní matici např. ${110\choose 011}$
- tvrzení: nechť $C$ je lineární $(n,k,d)$-kód s kontrolní maticí $K$, potom $\forall x\in\mathbb Z_2^n:x\in C\iff Kx^T=\underline 0$
- důkaz
	- nechť $r_1,r_2,\dots,r_{n-k}\in\mathbb Z_2^n$ jsou řádky $K$
	- potom $x\in C\iff x\in(C^\perp)^\perp\iff\forall y\in C^\perp:\braket{x,y}=0$ $\iff \forall i\in\set{1,\dots,n-k}:\braket{x,r_i}=0\iff Kx^T=\underline 0$
- nechť $C$ je lineární $(n,k,d)$-kód s kontrolní maticí $K$
- víme: $d=\Delta(C)=\min_{x\in C\setminus\set{0}}||x||$
- pozorování: navíc $\Delta(C)$ je nejmenší $t\geq 1$ takové, že v $K$ lze najít $t$ sloupců, jejichž součet je $\underline 0\in\mathbb Z_2^{n-k}$
- důsledky
	- $\Delta(C)\geq 2\iff K$ má všechny sloupce nenulové
	- $\Delta(C)\geq 3\iff K$ má všechny sloupce nenulové a navíc každé dva sloupce různé
- df: nechť $r\in\mathbb N,\,r\geq 2$, nechť $K_r$ je matice s $r$ řádky a $2^r-1$ sloupci, jejíž sloupce jsou nenulové a různé; nechť $H_r$ je kód s kontrolní maticí $K_r$; kódům $H_r$ se říká Hammingovy kódy
- konvence (?): $i$-tý sloupec $K$ odpovídá binárnímu zápisu čísla $i$
- pozorování: $H_r$ je lineární $(n,k,d)$-kód, kde $n=2^r-1,\;k=2^r-1-r,\;d=3$
- tvrzení: $\forall r\geq 2$, pro $n=2^r-1$, $\forall x\in\mathbb Z_2^n$; existuje právě jedno $y\in H_r$ takové, že $d(x,y)\leq 1$
- navíc to $y\in H_r$ lze najít následujícím algoritmem
	- spočítej $K_rx^T=:s$
	- pokud $s=\underline 0$, tak $x\in H_r$, tedy $y:=x$
	- pokud $s\neq\underline 0$, tak nechť $i\in\set{1,\dots,n}$ je takové, ž $i$-tý sloupec $K_r$ je roven $s$; potom nechť $y$ je vektor, který vznikne z $x$ změnou $i$-tého bitu
- důkaz přeskočíme
- Hammingovy kódy umí opravit jednu chybu, jsou mnohem úspornější než trojnásobné opakování
- tvrzení (Singletonův odhad): pokud existuje $(n,k,d)$-kód $C$, tak $k+d\leq n+1$
- důkaz
	- nechť $C$ je $(n,k,d)$-kód
	- definujme funkci $\psi:\mathbb Z_2^n\to\mathbb Z_2^{n-d+1}$
	- $\psi(x_1,\dots,x_n)=(x_1,\dots,x_{n-d+1})$
	- pro $x,y\in C$, $x\neq y$, tak $\psi(x)\neq\psi(y)$
	- tedy $|C|\leq 2^{n-d+1}$
	- tedy $k\leq n-d+1$, tj. $k+d\leq n+1$
	- stručně: $d$ označuje počet bitů, ve kterých se dvě různá slova liší, takže když jich smažeme $d-1$, tak se pořád budou lišit
- značení: $B(x,t):=\set{y\in\mathbb Z_2^n:d(x,y)\leq t}$, $V(t):=|B(x,t)|={n\choose 0}+{n\choose1}+{n\choose2}+\dots+{n\choose t}$
- tvrzení (Hammingův odhad): pokud existuje $(n,k,d)$-kód $C$, tak $|C|\leq\frac{2^n}{V(\lfloor\frac{d-1}2\rfloor)}$
- důkaz: plyne z toho, že pro $x,y\in C$, $x\neq y$: $B(x,\lfloor\frac{d-1}2\rfloor)\cap B(y,\lfloor\frac{d-1}2\rfloor)=\emptyset$
- tvrzení (Gilbert-Varshamovův odhad): $\forall n,d,d\lt n$ existuje kód $C$ taková, že $|C|\geq 2^n/V(d-1)$
- důkaz: hledejme $C$ hladově