Zkouška

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_nx^n$

• 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ích stromů s $n$ vnitřními vrcholy
• $(C_n)_{n=0}^\infty$ jsou Catalanova čísla
• rekurentní tvar
  • $C_0=1$
  • $C_{n+1}=\sum_{i=0}^n C_iC_{n-i}$ pro $n\gt 0$
• explicitní vzorec: $C_n=\frac1{n+1}{2n\choose n}$

• 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

• KPR má řád $n\in\mathbb N$, pokud každá její přímka má $n+1$ bodů
• tedy řád KPR := velikost přímky – 1

hypergraf je dvojice $(V,H)$, kde $H$ je množina podmnožin $V$, tj. $H\subseteq\mathcal P(V)$

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$

• 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^*\coloneqq\set{p\in\mathcal P:x\in p}$
    • $x^*$ … přímky, které procházejí $x$
  • $\mathcal P^*=\set{x^*\mid x\in X}$
• v podstatě obrátíme incidenční graf

• 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

• velikost toku $f$ v síti $(V,E,z,s,c)$ je $w(f)\coloneqq f[\text{Out}(z)]-f[\text{In}(z)]$
• kde Out(z) a In(z) jsou množiny hran do, respektive ze zdroje a $f[A]\coloneqq\sum_{e\in A}f(e)$ pro $A\subseteq E$

maximální tok je tok, který má největší velikost

ř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)$

• $E(A,B)\coloneqq E\cap (A\times B)$
• tedy $E(A,B)=\set{uv\in E: u\in A\land v\in B}$
• elementární řez je $E(A,B)$ pro $A\subseteq V,\;B=V\setminus A$
  • přičemž $z\in A,\;s\in B$

minimální řez je řez, který má nejmenší kapacitu

• 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$

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$

vrcholové pokrytí v $G=(V,E)$ je množina vrcholů $C\subseteq V$ taková, že každá hrana obsahuje aspoň 1 vrchol z $C$

• 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,f\in E:e\neq f\implies r(e)\neq r(f)$ … tj. $r$ je prostá
• $r(e)$ … „reprezentant hyperhrany $e$“
• analogie s předsedy spolků

• $F\subseteq E$ je hranový řez v $G$, pokud $G-F$ je nesouvislý
  • kde $G-F\coloneqq(V,E\setminus F)$
• $A\subseteq V$ je vrcholový řez, pokud $G-A$ je nesouvislý
  • kde $G-A=(V\setminus A,E\cap {V\setminus A\choose 2})$

• 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$
• 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

• graf je hranově $k$-souvislý, pokud neobsahuje žádný hranový řez velikosti menší než $k$
• graf je vrcholově $k$-souvislý, pokud má aspoň $k+1$ vrcholů a neobsahuje žádný vrcholový řez velikosti menší než $k$

• klika v grafu je množina vrcholů taková, že každé dva jsou spojené hranou
• nezávislá množina v grafu je množina vrcholů taková, že žádné dva vrcholy nejsou spojené hranou

• slovo $x\in\mathbb Z^n_2$ lze chápat jako řádkový vektor $x=(x_1,x_2,\dots,x_n)$
• Hammingova vzdálenost $d(x,y)\coloneqq$ počet $i$ takových, že $x_i\neq y_i$
• Hammingova váha $\Vert x\Vert\coloneqq$ počet $i$ takových, že $x_i\neq 0$

pro kód $C\subseteq\mathbb Z_2^n$ je minimální vzdálenost $\Delta(C)\coloneqq\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$

• 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$)
• pro lineární $(n,k,d)$-kód je $k$ jeho dimenze

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$

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$

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)$

$C^\perp\coloneqq\set{y\in\mathbb Z_2^n:(\forall x\in C)\braket{x,y}=0}$ … duální kód k $C$

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$

• 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

• věta: $e(\frac ne)^n\leq n!\leq en(\frac ne)^n$
• důkaz: odhad pomocí integrálu
  • $\ln(n!)=\sum_{i=1}^n\ln(i)=\sum_{i=2}^n\ln(i)$
    • protože $\ln(1)=0$
  • 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ě horní 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!$
  • obrázek zachycuje situaci pro $n=7$
  • 
• věta: $(\frac nk)^k\leq{n\choose k}\leq(e\cdot\frac nk)^k$
  • kde ${n\choose k}=\frac{n!}{k!\cdot(n-k)!}$ pro $0\leq k\leq n$
• důkaz
  • dolní odhad
    • ${n\choose k}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{k\cdot(k-1)\cdot\ldots\cdot 1}=\frac nk\cdot\frac{n-1}{k-1}\cdot\ldots\cdot\frac{n-k+1}{1}\geq(\frac nk)^k$
    • neboť $\frac nk\leq\frac{n-1}{k-1}\leq\dots\leq\frac{n-k+1}1$
  • horní odhad
    • ${n\choose k}=\frac{\overbrace{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}^{k}}{k!}\leq\frac{n^k}{(\frac ke)^k}=(\frac{en}k)^k$
    • používáme $(\frac ne)^n\leq n!$
• věta: $\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}}$
  • $P=\frac{2m\choose m}{2^{2m}}=\frac{\frac{(2m)!}{m!\cdot m!}}{\underbrace{2\cdot2\cdot\ldots\cdot2}_{2m}}=\frac{1\cdot2\cdot3\cdot\ldots\cdot 2m}{(2\cdot4\cdot 6\cdot\ldots\cdot 2m)(2\cdot 4\cdot6\cdot\ldots\cdot 2m)}=\frac{1\cdot 3\cdot 5\cdot\ldots\cdot(2m-1)}{2\cdot4\cdot6\cdot\ldots\cdot 2m}$
  • $P^2=\frac{1\cdot1\cdot3\cdot3\cdot\ldots\cdot(2m-1)\cdot(2m-1)}{2\cdot2\cdot4\cdot4\cdot\ldots\cdot 2m\cdot2m}=1\cdot\frac{1\cdot 3}{2\cdot 2}\cdot\frac{3\cdot 5}{4\cdot 4}\cdot\ldots\cdot\frac{(2m-3)(2m-1)}{(2m-2)(2m-2)}\cdot\frac{2m-1}{2m\cdot 2m}$
  • používáme postřeh $\forall k\in\mathbb N:\frac{(k-1)(k+1)}{k\cdot k}=\frac{k^2-1}{k^2}\lt 1$
  • tedy $P^2\lt\frac{2m-1}{2m\cdot 2m}\lt\frac1{2m}$
  • podobně $P^2=\frac{1\cdot1}{2}\cdot\frac{3\cdot 3}{2\cdot 4}\cdot\ldots\cdot\frac{(2m-1)(2m-1)}{(2m-2)(2m)}\cdot\frac1{2m}$
  • zjevně $\frac{k\cdot k}{(k-1)(k+1)}\gt 1$
  • proto $P^2\gt\frac1{4m}$
  • máme $\frac 1{4m}\leq P^2\leq\frac 1{2m}$, z toho $\frac1{2\sqrt{m}}\leq P\leq \frac{1}{\sqrt{2m}}$

• obecný postup
  • 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 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$
  • $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}$

• fakt: pokud se dá posloupnost shora odhadnout nějakou exponenciální funkcí, tak $a_n=\frac{1}{n!} f^{(n)}(0)$
  • kde $f(x)$ je její vytvořující funkce
  • „odvození“
    • $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$
• 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$
• 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 (protože pro $n\gt\delta$ bude v součinu v čitateli jeden člen nulový)
  • celkově ignorujeme otázky konvergence, ale aby věta platila, tak bychom chtěli $|x|\lt1$
• důkaz
  • označme $f(x)=(1+x)^\delta$
  • zjevně
    • $f'(x)=\delta(1+x)^{\delta-1}$
    • $f''(x)=\delta(\delta-1)(1+x)^{\delta-2}$
    • $f^{(n)}(x)=\delta(\delta-1)\cdot\ldots\cdot(\delta-n+1)(1+x)^{\delta-n}$
  • 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}$

• modelový příklad: našli jsme $f(x)=\frac{1-2x}{(1-3x)(1-x)}$
• chceme znát explicitní vzorec pro $a_n$ (známe rekurentní)
• $\frac{1-2x}{(1-3x)(1-x)}=\frac\alpha{1-3x}+\frac\beta{1-x}$
• ${\alpha\over1-3x}$ odpovídá posloupnosti $\alpha,3\alpha,9\alpha,\dots,3^n\alpha,\dots$
• $\beta\over 1-x$ odpovídá posloupnosti $\beta,\beta,\beta,\dots,\beta,\dots$
• tedy $a_n=3^n\alpha+\beta$
• $\alpha,\beta$ lze spočítat…
  • pomocí prvních několika členů posloupnosti
    • $a_0=1=3^0\alpha+\beta=\alpha+\beta$
    • $a_1=2=3^1\alpha+\beta=3\alpha+\beta$
  • rozkladem na parciální zlomky (viz např. Math Tutor)

• $C_n$ … počet binární stromů s $n$ vnitřními vrcholy
  • $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$
  • $C(x)=\sum_{n=0}^\infty C_nx^n$
• $\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 ovlivňuje pouze koeficient u $C_0$, můžeme se jí zbavit
• $=-\frac12[x^{n+1}]\sqrt{1-4x}=(-\frac12)(-4)^{n+1}[x^{n+1}]\sqrt{1+x}=$
• $=(-\frac12)(-4)^{n+1}{\frac12\choose n+1}=(-1)^n\cdot 2^{2n+1}\cdot\frac{\frac12\cdot(\frac12-1)\cdot\ldots\cdot(\frac12-n)}{(n+1)!}$
  • ze zobecněné binomické věty
• $=(-1)^n\cdot 2^{2n+1}\cdot\frac{\frac12\cdot(-\frac12)\cdot(-\frac32)\cdot\ldots\cdot(-\frac{2n-1}2)}{(n+1)!}=2^n\cdot\frac{1\cdot3\cdot5\cdot\ldots\cdot(2n-1)}{(n+1)!}=$
• $=\frac{1\cdot3\cdot5\cdot\ldots\cdot(2n-1)\cdot (2^n\cdot n!)}{(n+1)!\cdot n!}=\frac{(2n)!}{(n+1)!\cdot n!}=\frac1{n+1}{2n\choose n}$

• tvrzení: v každé KPR mají všechny přímky stejný počet bodů
• důkaz: 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_\ell$, kde $k\lt \ell$
  • 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{wz_1},\overline{wz_2},\dots,\overline{wz_\ell},\overline{wx}$, 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
  • spor: $w$ a $v$ mají aspoň 2 společné přímky
• 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
• definice: KPR má řád $n\in\mathbb N$, pokud každá její přímka má $n+1$ bodů
• 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 1 (každý bod patří do právě $n+1$ přímek)
  • 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
• důkaz 2 ($|X|=n^2+n+1$)
  • 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$
• důkaz 3 ($|\mathcal P|=n^2+n+1$) – dvě varianty
  • 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ů
    • mezi partitami tedy vede $(n^2+n+1)(n+1)$ hran
    • proto i v horní partitě musí být $n^2+n+1$ vrcholů
  • 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)$

• věta: $(X^*,\mathcal P^*)$ je projektivní rovina
  • připomenutí: $x^*\coloneqq\set{p\in\mathcal P:x\in p}$
• důkaz
  • $(X^*,\mathcal P^*)$ splní A1 $\iff(\forall p,q\in X^*,\;p\neq q)(\exists! x^*\in\mathcal P^*):\set{p,q}\subseteq x^*$ $\iff (\forall p,q\in\mathcal P,\;p\neq q)(!\exists x\in X):x\in p\land x\in q\iff (X,\mathcal P)$ splní A2
  • obdobně $(X^*,\mathcal P^*)$ splní A2 $\iff\dots\iff(X,\mathcal P)$ splní A1
  • A3: 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$
    • tvrdíme, že $\overline{ab},\overline{bc},\overline{cd},\overline{ad}$ jsou hledané 4 přímky
    • zvolíme tři z nich: $\overline{ab},\overline{bc},\overline{cd}$
      • průnik prvních dvou je $b$
      • průnik druhých dvou je $c$
      • společný bod nemají
    • obdobně pro libovolnou jinou trojici

• 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)\mid x,y,z\in T}$, $|V|=n^3$
• nechť $X$ je množ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\mid 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
• intuice: kdyby to bylo v $\mathbb R^3$, tak body jsou přímky procházející počátkem a přímky jsou roviny procházející počátkem (svazky přímek)
• $(X,\mathcal P)$ je projektivní rovina
  • A1: dva různé podprostory dimenze 1 jsou generovány dvěma lineárně nezávislými vektory, ty dohromady generují podprostor dimenze 2
  • A2: $\dim P+\dim Q-\dim(P\cap Q)=\dim(\text{span}(P\cup Q))$
    • $\dim P=\dim Q=2$
    • $\dim(span(P\cup Q))=3$
    • tedy $\dim(P\cap Q)=1$
  • A3: lze nalézt 4 nenulové vektory takové, že každé tři z nich jsou lineárně nezávislé
    • např. $(1,0,0),(0,1,0),(0,0,1),(1,1,1)$

• 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

• pozorování: pokud má tok $f$ zlepšující cestu, tak není maximální
• důkaz: 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)$
• důkaz
  • $1\implies 2:$ obměnou (viz pozorování)
  • $3\implies 1:$ obměnou
    • 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)$
• 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)$
• důkaz
  • $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)