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)