Zkouška

Kromě uvedených pojmů a tvrzení se u zkoušky můžete setkat i s počítacími nebo teoretickými příklady.

Pojmy

U následujících pojmů byste měli umět zformulovat definici a na jednoduchém příkladu ukázat, že té definici rozumíte.

• vytvořující funkce
  • 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$
• Catalanova čísla
  • 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
  • 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
• řád konečné projektivní roviny
  • 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
  • hypergraf je dvojice $(V,H)$, kde $H$ je množina podmnožin $V$, tj. $H\subseteq\mathcal P(V)$
• incidenční graf hypergrafu
  • 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$
• dualita projektivních rovin
  • 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
• toková síť
  • 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
  • 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
  • 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
  • maximální tok je tok, který má největší velikost
• řez v síti
  • ř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
  • kapacita řezu $R$ … $c(R)=\sum_{e\in R}c(e)$
• elementární řez
  • $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
  • minimální řez je řez, který má nejmenší kapacitu
• nenasycená a zlepšující cesta
  • 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
  • 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 grafu
  • 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ů v hypergrafu
  • 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ů
• hranový a vrcholový řez v grafu
  • $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})$
• hranová a vrcholová souvislost grafu
  • 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
• hranově a vrcholově $k$-souvislý graf
  • 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 a nezávislá množina v grafu
  • 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
• Hammingova vzdálenost a Hammingova váha
  • 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$
• minimální vzdálenost kódu
  • 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
  • $(n,k,d)$-kód je množina $C\subseteq\mathbb Z_2^n$ taková, že $|C|=2^k$ a $\Delta(C)=d$
• lineární kó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
• generující matice
  • 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$
• kódování
  • 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í
  • 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)$
• duální kód
  • $C^\perp\coloneqq\set{y\in\mathbb Z_2^n:(\forall x\in C)\braket{x,y}=0}$ … duální kód k $C$
• kontrolní matice lineárního kódu
  • 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$
• Hammingovy kódy
  • 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

Tvrzení

U následujících tvrzení se očekává, že je budete umět zformulovat a (není-li uvedeno jinak) i dokázat.

• Odhady kombinatorických funkcí: $e(n/e)^n\leq n!\leq en(n/e)^n$, $(n/k)^k\leq{n\choose k}\leq(en/k)^k$, $\frac{2^{2m}}{2\sqrt m}\leq{2m\choose m}\leq\frac{2^{2m}}{\sqrt{2m}}$
  • 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}}$
• Odvození vytvořující funkce pro rekurentně zadanou posloupnost
  • 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}$
• Zobecněná binomická věta
  • 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}$
• Rozklad racionální funkce na parciální zlomky (bez důkazu) a jeho využití při práci s vytvořujícími funkcemi
  • 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)
• Odvození vzorečku pro Catalanova čísla, definovaná jako počet binárních zakořeněných stromů
  • $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}$
• Odvození vlastností konečných projektivních rovin: počet bodů, počet přímek, počet bodů v jedné přímce, počet přímek procházejících jedním bodem
  • 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)$
• Duální projektivní rovina je opravdu projektivní rovina
  • 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
• Konstrukce projektivních rovin z konečných těles
  • 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)$
• Existence maximálního toku v obecné síti (bez důkazu)
  • 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
• Charakterizace maximálního toku pomocí neexistence zlepšující cesty a pomocí řezu odpovídající kapacity; minimaxová věta o toku a řezu
  • 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)
• Fordův–Fulkersonův algoritmus, jeho důsledek pro celočíselnost maximálního toku a pro existenci maximálního toku v síti s racionálními kapacitami
  • algoritmus
    • iterujeme, dokud existuje zlepšující cesta
    • spočítáme rezervu celé cesty (minimum přes rezervy hran cesty)
    • pro každou hranu upravíme tok – v protisměru odečteme co nejvíc, zbytek přičteme po směru
  • pro celočíselné kapacity vrátí celočíselný tok (protože i rezervy budou celočíselné)
  • racionální kapacity převedeme na celočíselné
  • algoritmus se zastaví, protože v takové síti musí existovat řez s konečnou kapacitou a protože se tok v každé iteraci zvětší aspoň o jedna
• Souvislost mezi velikostí největšího párování a nejmenšího vrcholového pokrytí v obecném grafu
  • lemma: pokud $M$ je párování a $C$ vrcholové pokrytí v $G=(V,E)$, tak $|M|\leq |C|$
  • důkaz
    • 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$
• Kőnigova–Egerváryho věta
  • věta: v každém bipartitním grafu má největší párování stejnou velikost jako nejmenší vrcholové pokrytí
  • důkaz
    • nechť $G=(V,E)$ je bipartitní graf s partitami $A,B$
    • vytvořme tokovou síť $(V\cup\set{z,s},E^+,z,s,c)$
      • $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}$
      • pro $x\in A$, $y\in B$
        • $c(zx)=c(ys)=1$
        • $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|$
• Hallova věta v grafové a hypergrafové verzi
  • pozorování: v bipartitním grafu s partitami $A,B$ má každé párování velikost nejvýše $|A|$ (i nejvýše $|B|$)
  • definice: pro graf $G=(V,E)$ a množinu $X\subseteq V$ označím $N(X):=\set{y\in V\setminus X: (\exists x\in X)\set{x,y}\in E}$
  • 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“}}$
  • důkaz
    • $\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őnigovy–Egerváryho 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$
        • protože nepokryté hrany musí pokrývat vrcholy v $N(X)$
      • navíc $|X|=|A|-|C_A|\gt |C_B|\geq |N(X)|$
        • jelikož $|C|\lt|A|\implies |A|\gt|C_A|+|C_B|$
      • to je spor s Hallovou podmínkou
  • pozorování: 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
    • $H$ má SRR $\iff$ $I_H$ má párování velikosti $|E|$
    • 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$
• Mengerovy věty pro hranovou a vrcholovou souvislost (Mengerova věta pro hranovou souvislost je též někdy označována jako „Fordova–Fulkersonova věta“)
  • Mengerova věta, 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)$
  • Mengerova věta, 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
  • důkaz
    • $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é: existuje $k$ hranově disjunktních cest z $x$ do $y$
  • definice: 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$
  • Mengerova věta, vrcholová $xy$-verze
    • 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$
  • důkaz
    • $\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$
  • 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$
  • důkaz
    • nechť $A$ je nejmenší vrcholový řez v $G^-$
      • potom $k_v(G^-)=|A|$
    • chceme $k_v(G)\leq k_v(G^-)+1=|A|+1$
    • $G^-$ se po odebrání $A$ rozpadne na několik komponent, rozlišme případy:
      • pokud existuje komponenta (v $G^--A$), která neobsahuje $x$ ani $y$, tak $A$ je vrcholový řez v $G$
        • tedy $k_v(G)\leq |A|$
      • jinak má $G^--A$ právě 2 komponenty, jedna obsahuje $x$, druhá $y$, označíme je jako $G^-_x,G^-_y$
        • pokud BÚNO $G^-_x$ obsahuje ještě nějaký další vrchol $z$, tak $A\cup\set x$ je vrcholový řez v $G$, tedy $k_v(G)\leq|A|+1$
        • pokud $G_x^-$ ani $G_y^-$ už neobsahují kromě $x$ nebo $y$ už žádný další vrchol, tak $|V|=|A|+2$, tedy $k_v(G)\leq |V|-1=|A|+1$
  • Mengerova věta, globální vrcholová verze
    • $G$ je vrcholově $k$-souvislý $\iff$ mezi každými dvěma různými vrcholy $x,y$ existuje $k$ navzájem VVD cest
  • důkaz
    • 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 vrcholy 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{\set{x,y}})$
          • 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$
• Lemma o uších pro 2-souvislé grafy
  • konvence: „$k$-souvislý graf“ znamená „vrcholově $k$-souvislý“
  • definice: 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 hrany cesty $xz_1z_2\dots z_dy$
  • věta: 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
          • opět spor s maximalitou $G_\max$
• Cayleyho vzorec pro počet stromů na $n$ vrcholech
  • věta: $s_n=n^{n-2}$
    • $s_n$ … počet stromů na množině vrcholů $[n]\coloneqq\set{1,2,\dots,n}$
  • důkaz
    • nebudu počítat stromy, ale kořenové stromy
      • definice: 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
    • definice: 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}$
• Spernerova věta
  • 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]$
  • definice: 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: 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 antiř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}$
      • definice: 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$
      • v $\mathcal P([n])$ existuje $n!$ nasycených řetězců
        • idea: 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 z $\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|!\cdot(n-|A|)!$
        • $\implies1\geq\sum_{A\in\mathcal A}\frac{|A|!\cdot(n-|A|)!}{n!}=\sum_{A\in\mathcal A}\frac1{n\choose|A|}\geq\sum_{A\in\mathcal A}\frac1{n\choose\lfloor n/2\rfloor}=|\mathcal A|\cdot\frac1{n\choose\lfloor n/2\rfloor}$
          • ze všech kombinačních čísel $n\choose k$ je největší $n\choose n/2$, takže ho můžu všude nahradit a hodnota výrazu se tím zmenší
        • $\implies{n\choose\lfloor n/2\rfloor}\geq |\mathcal A|$
• Počet hran v grafu bez $C_4$
  • 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$
    • poznámka: ${n\choose 2}=\frac{n(n-1)}2$
    • 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$
    • $\sqrt n\geq\frac{2|E|}n-1$
      • počet hran je polovina ze součtu stupňů
    • $n^{3/2}\geq 2|E|-n$
    • $\frac12(n^{3/2}+n)\geq|E|$
• Počítání dvěma způsoby (znalost obecného postupu)
  • typicky známe vlastnosti množin $A$ a $B$
  • snažíme se vyjádřit hledanou veličinu pomocí dvojic, kde jeden prvek je z $A$ a druhý z $B$
  • alternativní pohled pomocí bipartitního grafu a partitami $A$ a $B$
    • zjistíme, že $A$ vysílá určitý počet hran a že $B$ může přijmout určitý počet hran
• Ramseyova věta v grafové verzi a ve verzi pro barvení hran úplného grafu (i s více než dvěma barvami)
  • Ramseyova věta, grafová verze: $(\forall k\in\mathbb N)(\forall\ell\in\mathbb N)(\exists N\in\mathbb N)$ takové, že každý graf na $N$ vrcholech obsahuje kliku velikosti $k$ nebo nezávislou množinu velikosti $\ell$
    • $R(k,\ell)$ … Ramseyovo číslo (nejmenší $N$, pro které platí, že libovolný graf na $N$ vrcholech obsahuje kliku velikosti $k$ nebo nezávislou množinu velikosti $\ell$)
  • důkaz indukcí podle $k+\ell$
    • základ indukce
      • pozorování: $R(k,1)=1=R(1,\ell)$
      • pozorování: $R(k,2)=k=R(2,k)$
    • mějme $k\geq 3,\,\ell\geq 3$, definujme $N:=R(k,\ell-1)+R(k-1,\ell)$
      • tyhle hodnoty jsou dobře definované (z indukčního předpokladu), protože součet argumentů je menší než $k+\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)$
      • právě jedna z nerovností musí platit
    • předpokládejme, že $|S|\geq R(k-1,\ell)$, označme $G_S$ podgraf $G$ indukovaný $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, kde $|T|\geq R(k,\ell-1)$, je analogický
  • důsledek (symetrická verze Ramseyovy věty): pro každé $m$ existuje $N$ takové, že graf na $N$ vrcholech má kliku nebo nezávislou množinu velikosti $m$
  • ekvivalentní 2-barevná verze Ramseyovy věty: pro každé $m$ existuje $N$ takové, že pro každé 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)$ takové, že pro každé 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í
    • $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}(m)$ vrcholech, jehož hrany jsou obarveny pomocí $b-1$ barev, tedy v něm je jednobarevná klika velikosti $m$
• Ramseyova věta pro hypergrafy v konečné a nekonečné verzi (bez důkazu)
  • 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)}$
  • $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})$
  • Ramseyova věta, konečná verze: $(\forall p\in\mathbb N)(\forall b\in\mathbb N)(\forall m\in\mathbb N)(\exists N\in\mathbb N)$ takové, že pro každé $b$-obarvení $K_N^{(p)}$ existuje jednobarevná $m$-prvková podmnožina $[N]$
  • Ramseyova věta, nekonečná verze: $(\forall p\in\mathbb N)(\forall b\in\mathbb N)$ pro libovolné $b$-obarvení $K_\infty^{(p)}$ existuje nekonečná jednobarevná podmnožina $\mathbb N$
  • $p=1$
    • v podstatě barvíme vrcholy
    • pro dané $b,m$ stačí $N=b(m-1)+1$
      • při $b(m-1)$ vrcholech lze najít obarvení, kde každá barva barví přesně $m-1$ vrcholů, po přidání dalšího vrcholu už alespoň jedna barva musí barvit $m$ vrcholů
    • princip holubníku
• Kőnigovo lemma o nekonečné cestě ve stromě, jeho použití při odvození konečné Ramseyovy věty z nekonečné
  • 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
      • kdyby byly všechny podstromy konečné, byl by celý strom konečný
    • 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é verze 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í
• Použití generující matice ke kódování
  • 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$
  • důkaz
    • 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. zobrazení $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é
• Použití kontrolní matice k ověření, zda je slovo kódové
  • 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[n-k]:\braket{x,r_i}=0\iff Kx^T=\underline 0$
• Souvislost minimální vzdálenosti kódu se sloupci kontrolní matice
  • nechť $C$ je lineární $(n,k,d)$-kód s kontrolní maticí $K$
  • pozorování: pokud $C$ je lineární, tak $d=\Delta(C)=\min_{x\in C\setminus{\set{\underline 0}}} d(x,\underline 0)=\min_{x\in C\setminus\set{\underline 0}}\Vert x\Vert$
    • pokud $x,y\in C$ jsou takové, že $d(x,y)=\Delta(C)$, tak potom $d(x,y)=d(x\oplus y,\underline 0)$
  • 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}$
    • $x$ řeší rovnici $Kx^T=\underline 0\iff$ $x$ má jedničky na místech sloupců, které se sečtou na nulu
  • 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é
• Konstrukce Hammingových kódů a jednoznačnost jejich dekódování
  • definice
    • 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
  • přirozená konvence: $i$-tý sloupec $K_r$ odpovídá binárnímu zápisu čísla $i$ (ale obecně pořadí sloupců pro naše účely není důležité)
  • 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é, že $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í
• Singletonův, Hammingův a Gilbertův–Varshamovův odhad na parametry kódů
  • Singletonův odhad: pokud existuje $(n,k,d)$-kód $C$, tak $k+d\leq n+1$
  • důkaz
    • 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
    • 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$
  • 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}$
    • ${n\choose k}$ … počet vektorů, které se od $x$ liší v $k$ bitech
  • 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
    • 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$
    • jedna koule pokryje $V(\lfloor\frac{d-1}2\rfloor)$
    • všechny koule dohromady pokryjí $|C|\cdot V(\lfloor\frac{d-1}2\rfloor)$
    • nemůžou toho pokrýt víc, než tam toho je, proto $|C|\cdot V(\lfloor\frac{d-1}2\rfloor)\leq 2^n$
  • Gilbert-Varshamovův odhad: $\forall n,d$, přičemž $d\lt n$, existuje kód $C$ taková, že $|C|\geq\frac{2^n}{V(d-1)}$
  • důkaz
    • hledám $C$ hladově
      • dám do $C$ nějaký vektor
      • všechny vektory, které jsou od něj do vzdálenosti $d-1$ nesmím použít
      • tak pokračuju dál
    • v každém kroku nejvýš $V(d-1)$ vektorů eliminuju
    • vždycky zvládnu vybrat dohromady aspoň $\frac{2^n}{V(d-1)}$ vektorů