Zkouška

Úvod

• Příklad: Technika důkazu indukcí a sporem
  • věta: Prvočísel je nekonečně mnoho.
  • důkaz sporem
    • kdyby $p_1,\dots,p_n$ byla všechna prvočísla
    • $\zeta := p_1\cdot p_2 \cdot \ldots\cdot p_n$
    • $(\zeta +1)\bmod p_i=1 \implies \zeta + 1$ není dělitelné žádným prvočíslem a je větší než všechna $p_i\implies\zeta+1$ by také muselo být prvočíslo ↯
  • věta: $\forall n \in \mathbb N: 2^0+2^1+2^2+\dots+2^n=2^{n+1}-1$
  • důkaz indukcí podle n
    • $2^0=2^1-1$
    • indukční krok
      • IP: $2^0+2^1+2^2+\dots+2^n=2^{n+1}-1$
      • chceme: $2^0+2^1+2^2+\dots+2^n+2^{n+1}=2^{n+2}-1$
      • z IP: $2^{n+1}-1+2^{n+1}=2^{n+2}-1\quad \square$
• Definice: Operace s čísly: sumy, produkty, horní a dolní celá část
  • prázdná suma se rovná nule, prázdný produkt jedné
  • horní celá část se značí $\lceil x \rceil$, zaokrouhluje nahoru
  • dolní celá část se značí $\lfloor x \rfloor$, zaokrouhluje dolů
• Definice: Množinové operace: rovnost, inkluze, sjednocení, průnik, rozdíl, symetrická diference, potence (množina podmnožin), mohutnost (počet prvků)
  • symetrická diference $A\bigtriangleup B=(A\setminus B)\cup(B\setminus A)$
  • potence $2^A:=\lbrace B \mid B\subseteq A\rbrace$
• Definice: Uspořádané k-tice a kartézský součin
  • uspořádaná dvojice $(x,y)$
    • lze zavést pomocí klasických množin jako $\lbrace \lbrace x \rbrace, \lbrace x,y\rbrace\rbrace$
    • uspořádaná k-tice $(x_1,\dots,x_k)$
  • kartézský součin $A\times B:=\lbrace(a,b)\mid a\in A, b\in B \rbrace$
    • $A^k:=\underbrace{A\times A \times \dots \times A}_k$

Relace

• Definice: Relace mezi množinami, relace na množině
  • (binární) relace mezi množinami $X,Y$ je podmnožina $X\times Y$
  • relace na množině $X$ je podmnožina $X^2$
  • značení – pro relaci $R$ mezi $X,Y:xRy \equiv (x,y)\in R$
• Příklad: Příklady relací: prázdná, univerzální, diagonální
  • prázdná $\emptyset$
  • univerzální $X\times Y$
  • diagonální $\Delta_X := \lbrace (x,x)\mid x\in X\rbrace$, např. rovnost $x=y$
• Definice: Operace s relacemi: inverze, skládání
  • inverze
    • k relaci $R$ mezi $X,Y$ lze definovat inverzní relaci $R^{-1}$ mezi $Y,X$, přičemž $R^{-1} := \lbrace(y,x)\mid (x,y)\in R\rbrace$
  • skládání
    • pro relaci $R$ mezi $X,Y$ a relaci $S$ mezi $Y,Z$ lze definovat složenou relaci $T=R\circ S$ mezi $X,Z$
    • $xTz \equiv \exists y \in Y: xRy \land ySz$
    • $R\circ \Delta_Y =R,\quad \Delta_X\circ R = R$
    • značení skládání funkcí: $(f\circ g)(x)=g(f(x))$
• Definice: Funkce (zobrazení) a jejich druhy: prosté (injektivní), na (surjektivní), vzájemně jednoznačné (bijektivní)
  • funkce z množiny X do množiny Y je relace A mezi X a Y t. ž. $(\forall x\in X)(\exists! y\in Y):xAy$
  • funkce $f:X\to Y$ je…
  • prostá (injektivní) $\equiv \nexists x,x' \in X: x \neq x' \land f(x)=f(x')$
  • na Y (surjektivní) $\equiv (\forall y \in Y)(\exists x \in X): f(x)=y$
  • vzájemně jednoznačná (bijektivní) $\equiv (\forall y \in Y)(\exists! x \in X):f(x)=y$
    • taková funkce je tedy prostá i „na“
    • k takové funkci existuje inverzní funkce $f^{-1}$ z Y do X
• Definice: Vlastnosti relací: reflexivita, symetrie, antisymetrie, transitivita
  • relace R na X je…
  • reflexivní $\equiv \forall x \in X: xRx$
    • $\Delta_X \subseteq R$
  • symetrická $\equiv \forall x,y \in X: xRy \implies yRx$
    • $R=R^{-1}$
  • antisymetrická $\equiv \forall x,y \in X: xRy \land yRx \implies x=y$
    • $R\cap R^{-1}\subseteq \Delta_X$
  • tranzitivní $\equiv \forall x,y,z \in X: xRy \land yRz \implies xRz$
    • $R\circ R \subseteq R$
• Definice: Ekvivalence, ekvivalenční třída, rozklad množiny
  • relace R na X je ekvivalence $\equiv$ R je reflexivní & symetrická & tranzitivní
    • např. rovnost čísel, rovnost mod K, geometrická podobnost
  • ekvivalenční třída prvku $x \in X:R[x]=\lbrace y \in X \mid xRy\rbrace$
  • množinový systém $\mathcal S\subseteq 2^X$ je rozklad množiny $X \equiv$
    • $\forall A \in \mathcal S: A \neq \emptyset$
    • $\forall A,B\in \mathcal S: A\neq B \implies A \cap B = \emptyset$
    • $\bigcup_{A\in \mathcal S}A=X$
• Věta: Vztah mezi ekvivalencemi a rozklady
  • věta
    • (1) $\forall x \in X: R[x]\neq \emptyset$
    • (2) $\forall x,y \in X:$ buď $R[x]=R[y]$, nebo $R[x] \cap R[y]=\emptyset$
    • (3) $\lbrace R[x] \mid x \in X\rbrace$ (množina všech ekvivalenčních tříd) určuje ekvivalenci R jednoznačně
  • důkaz
    • (1) ekvivalence je reflexivní, tedy nutně platí $x \in R[x]$, tudíž je ta ekvivalenční třída neprázdná
    • (2) dokážeme, že pokud nejsou disjunktní, tak se rovnají
      • platí $R[x]\cap R[y]\neq \emptyset$
      • dokazujeme $R[x]=R[y]$, stačí nám $R[x]\subseteq R[y]$ (opačnou inkluzi lze dokázat podobným způsobem)
      • víme $\exists t \in R[x]\cap R[y]$
        • tedy platí xRt, tRx, yRt, tRy
      • chceme $\forall a \in R[x]: a \in R[y]$
      • dále aplikujeme tranzitivitu
      • $aRx \land xRt \implies aRt$
      • $aRt \land tRy \implies aRy$
    • (3) na základě ekvivalenčních tříd lze jednoznačně určit, zda jsou prvky x a y ekvivalentní, neboť stačí najít ekvivalenční třídu obsahující y a zjistit, zda je v této třídě také x

Uspořádání

• Definice: Uspořádání částečné a lineární, uspořádaná množina, ostré uspořádání
  • relace R na množině X je (částečné) uspořádání $\equiv$ R je reflexivní & antisymetrická & tranzitivní
  • (částečně) uspořádaná množina $(X,R)$
    • zkráceně ČUM
    • R je (částečné) uspořádání na X
  • prvky $x,y \in X$ jsou porovnatelné $\equiv xRy \lor yRx$
  • uspořádání je lineární $\equiv \forall x,y\in X$ porovnatelné
    • (všechny prvky množiny jsou navzájem porovnatelné)
  • částečné uspořádání (nebo pouze uspořádání) je obecný pojem, některá taková uspořádání jsou navíc lineární
  • ostré uspořádání – každému uspořádání $\leq$ na X přiřadíme relaci $<$ na X: $a < b \equiv a \leq b \land a \neq b$
    • pozor – ostré uspořádání není speciálním případem uspořádání (protože není reflexivní)
    • vlastnosti ostrého uspořádání – ireflexivní, antisymetrické, tranzitivní
• Příklady uspořádání: dělitelnost, inkluze podmnožin, lexikografické
  • dělitelnost $(\mathbb N^+,\backslash)$
    • $2\backslash 4$
    • $4,6$ neporovnatelné
    • dělitelnost na reálných čísel (bez nuly) není uspořádání, protože $(-1)\backslash1\land 1\backslash (-1)$ (není antisymetrické)
  • inkluze $(2^X,\subseteq)$
    • $\lbrace 1 \rbrace \subseteq \lbrace 1,3 \rbrace$
    • $\lbrace 1,2 \rbrace, \lbrace 2,3 \rbrace$ neporovnatelné
  • lexikografické uspořádání
    • abeceda: $(X, \leq)$
    • Df: $(X^2,\leq_{lex})$
    • $(a_1, a_2) \leq_{lex} (b_1, b_2) \equiv a_1 \lt b_1 \lor (a_1=b_1 \land a2\leq b_2)$
    • $(X^k, \leq_{lex})$
    • $(X^*, \leq_{lex})$
      • X* – konečné posloupnosti prvků z X
    • pokud je slovo krátké, doplníme ho mezerami ze začátku abecedy
• Definice: Hasseův diagram, relace bezprostředního předchůdce
  • Hasseův diagram graficky zachycuje vztahy mezi prvky ČUM (porovnatelné prvky jsou spojeny, větší prvky jsou výše)
  • $x$ je bezprostředním předchůdcem $y$ v uspořádání $\leq$ $\equiv x\lt y \land (\nexists z: x\lt z \land z \lt y)$
    • značí se $x\triangleleft y$
• Definice: Minimální/maximální a nejmenší/největší prvek
  • prvek $x\in X$ je nejmenší $\equiv \forall y \in X: x\leq y$
  • prvek $x\in X$ je minimální $\equiv \nexists y \in X: y\lt x$
  • x je nejmenší $\implies$ x je minimální
  • v Hassově diagramu
    • z minimálního prvku dolů nevede žádná spojnice
    • nejmenší prvek je nejníž v diagramu, existuje do něj cesta z libovolného jiného prvku
• Věta: Konečná neprázdná uspořádaná množina má minimální a maximální prvek
  • důkaz
    • zvolíme $x_1 \in X$ libovolně
    • buď je $x_1$ minimální, nebo $\exists x_2 \lt x_1$
    • buď je $x_2$ minimální, nebo $\exists x_3\lt x_2$
    • atd.
    • po konečně mnoha krocích nalezneme minimální prvek, protože jinak by X měla nekonečně mnoho různých prvků, což je spor s konečností
• Definice: Řetězec a antiřetězec
  • pro $(X,\leq)$ ČUM:
  • $A\subseteq X$ je řetězec $\equiv \forall a,b \in A: a,b$ jsou porovnatelné
  • $A \subseteq X$ je antiřetězec (nezávislá množina) $\equiv \nexists a,b$ různé & porovnatelné
• Definice: parametry α a ω
  • $\omega(X,\leq)$ je délka nejdelšího řetězce = maximum z délek řetězců (výška uspořádání)
  • $\alpha(X,\leq)$ je délka nejdelšího antiřetězce (šířka uspořádání)
• Věta: O Dlouhém a Širokém
  • věta: pro každou konečnou ČUM $(X,\leq)$ platí $\alpha(X,\leq)\cdot \omega(X,\leq)\geq |X|$
    • řetězec: $A\subseteq X:\forall a,b\in A: a\leq b\lor b\leq a$
    • antiřetězec: $A\subseteq X:\forall a,b\in A,\;a\neq b: \neg(a\leq b\lor b\leq a)$
    • maximální velikost řetězce … $\omega$ („výška“)
    • maximální velikost antiřetězce … $\alpha$ („šířka“)
    • důsledek věty: $\text{max}(\alpha,\omega)\geq\sqrt{|X|}$
  • důkaz
    • najdeme všechny minimální prvky → vrstva $X_1$
    • smažu $X_1$, proces opakuju → najdu $X_2$
    • tak postupuju dál, dokud nerozkrájím celou ČUM
    • každá vrstva tvoří antiřetězec
    • vrstvy jsou rozklad
    • existuje množina taková, že každý prvek je z jiné vrstvy a dohromady tvoří řetězec
      • formálně $\exists\lbrace q_1,\dots,q_k\rbrace$ řetězec t. ž. $\forall i: q_i\in X_i$
      • jak je to možné?
        • $q_{i+1}$ je ve vrstvě $X_{i+1}$, protože nějaký prvek $q_i$ je menší – ten je ve vrstvě $X_i$

Kombinatorické počítání

• Věta: Počet funkcí mezi množinami
  • věta: počet $f:N\to M=m^n$
    • pro $|N|=n, |M|=m;\quad m,n\gt 0$
  • důkaz indukcí podle $n$
    • $n=1\quad$ # $f=m=m^1$
    • $n\to n+1$
      • (n+1)-prvková N, m-prvková M
      • zvolíme $x\in N$
      • $f':N\setminus\lbrace x \rbrace\to M$
      • podle IP existuje $m^n$ funkcí $f'$
      • zadat zobrazení $f$ je totéž jako zadat hodnotu $f(x)\in M$ plus zobrazení $f'$
      • hodnotu $f(x)$ lze zvolit $m$ způsoby
      • celkem tedy $m^n\cdot m=m^{n+1}$
  • jiný způsob důkazu – pro každé $x$ existuje $m$ možností, počet $x$ je $n$
• Věta: Počet prostých funkcí mezi množinami
  • věta: počet prostých $f:N\to M=m^{\underline{n}}$ (viz klesající mocnina níže)
  • důkaz indukcí podle $n$
    • podobně jako předchozí důkaz
    • $n\to n+1$
      • $f':N\setminus\lbrace x \rbrace\to M\setminus\lbrace f(x) \rbrace$
      • podle IP existuje $(m-1)^{\underline n}$ funkcí $f'$
      • hodnotu $f(x)$ lze zvolit $m$ způsoby
      • celkem tedy $(m-1)^{\underline n} \cdot m=m^{\underline{n+1}}$
  • jiný způsob důkazu – pro první $x$ existuje $m$ možností, pro každé další o jednu méně, počet $x$ je $n$
• Definice: Klesající mocnina
  • $m^{\underline n}=\underbrace{m\cdot (m-1)\cdot (m-2)\cdot\ldots\cdot(m-n+1)}_n$
• Definice: Charakteristická funkce podmnožiny
  • pro podmnožinu $A$ množiny $X$ definujeme zobrazení $c_A:X\to\lbrace 0,1\rbrace$
  • $c_A(x)= \begin{cases} 1 &\text{pokud } x\in A \\ 0 &\text{pokud }x\notin A\end{cases}$
• Věta: Počet všech podmnožin
  • věta: $|2^N|=2^{|N|}$
  • důkaz: počet podmnožin = počet charakteristických funkcí = $2^{|N|}$
• Věta: Počet podmnožin sudé a liché velikosti
  • věta: Nechť $X\neq \emptyset$ je konečná množina, pak počet podmnožin $\mathcal S$ sudé velikosti se rovná počtu podmnožin $\mathcal L$ liché velikosti, což se rovná $2^{n-1}$.
  • důkaz
    • víme, že $\mathcal S\cup\mathcal L=2^X$
    • stačí $|\mathcal S|=|\mathcal L|$
    • sestrojíme $f:\mathcal S\to \mathcal L$ bijekci
    • zvolíme si $a\in X$
    • $f(S):=S\bigtriangleup \lbrace a\rbrace$ (prvek a přidáme nebo odebereme, podle toho, zda je prvkem S, nebo není)
    • $f(S)\in \mathcal L$
    • $f$ má inverzi $f^{-1}=f$
• Věta: Počet permutací na množině
  • definice: $[n]=\lbrace1,2,\dots,n\rbrace$
  • věta: na množině $[n]$ existuje $n!$ permutací (podobně na každé n-prvkové množině)
  • důkaz: počet prostých funkcí $[n]\to[n]=n^{\underline n}=n!$
• Věta: Počet uspořádaných k-tic bez opakování a k-prvkových podmnožin
  • počet uspořádaných k-tic $|X^k|=|X|^k$, lze jej totiž vyjádřit jako počet funkcí $f:[k]\to X$
  • u uspořádaných k-tic bez opakování hledáme prosté funkce, tedy $|X|^{\underline k}$
  • pomocí „počítání dvěma způsoby“ odvodíme vzorec pro neuspořádané k-tice (k-prvkové podmnožiny)
  • uspořádaných k-tic bude k!-krát víc než těch neuspořádaných (každou neuspořádanou k-tici lze k! způsoby lineárně uspořádat)
  • z toho vyplývá, že k-prvkových podmnožin (neuspořádaných k-tic) bude $|X|^{\underline k}\over k!$
• Definice: Notace pro množinu všech k-prvkových podmnožin
  • $X\choose k$ … množina všech k-prvkových podmnožin množiny X
• Definice: Kombinační číslo (binomický koeficient), Pascalův trojúhelník
  • kombinační číslo (binomický koeficient) ${n\choose k}:={n^{\underline k} \over k!}={n!\over k!(n-k)!}$
  • Pascalův trojúhelník – n roste shora dolů, k zleva doprava
• Věta: Základní vlastnosti kombinačních čísel
  • ${n\choose k} = {n\choose n-k}$ … každé k-prvkové podmnožině přiřadíme její doplněk
  • ${n-1\choose k-1}+{n-1\choose k}={n\choose k}$
    • zvolíme jeden prvek $a$ a rozdělíme všechny k-prvkové podmnožiny podle toho, zda obsahují $a$, nebo ne
• Binomická věta
  • věta: $(x+y)^n=\sum_{i=0}^n{n\choose i}x^{n-i}y^i$
  • důkaz
    • jeden člen výsledného součtu – součin n věcí, z nichž každá bude x nebo y
    • z každé závorky vyberu x nebo y
    • výsledkem je člen $x^{n-k}y^k$
    • takových členů tam bude $n \choose k$
• Věta: Princip inkluze a exkluze
  • věta: (pro konečné množiny) $$|\bigcup_{i=1}^nA_i|=\sum_{k=1}^n(-1)^{k+1}\sum_{I\in{[n]\choose k}}|\bigcap_{i\in I}A_i|$$
  • důkaz
    • pro prvek $x$ ve sjednocení spočítáme příspěvky k levé (vždy 1) a pravé straně
    • nechť $x$ patří do právě $t$ množin
    • průniky k-tic
      • $k \gt t$ … přispěje 0
      • $k\leq t$ … přispěje $(-1)^{k+1}{t\choose k}$
        • vybíráme k-tice množin z t-množin, do kterých prvek patří
        • minus jednička vychází ze vzorce
      • chceme $\sum_{k=1}^t(-1)^{k+1}{t\choose k}=1$
      • lze upravit na $\sum_{k=1}^t(-1)^{k}{t\choose k}=-1$
      • z binomické věty $0=(1-1)^t=\sum_{k=0}^t{t\choose k}(-1)^{k}$
      • tedy bez prvního členu se součet rovná $-1\quad \square$
  • druhý důkaz – pomocí charakteristických funkcí
• Příklad: Problém šatnářky: počet permutací bez pevného bodu
  • Šatnářka $n$ pánům vydá náhodně $n$ klobouků (které si předtím odložili v šatně). Jaká je pravděpodobnost, že žádný pán nedostane od šatnářky zpět svůj klobouk?
  • jaká je pravděpodobnost, že náhodně zvolená permutace nebude mít žádný pevný bod
  • každá z $n!$ permutací je stejně pravděpodobná
  • $š(n)$ … počet permutací bez pevného bodu
  • pravděpodobnost je rovna $š(n)/n!$
  • $S_n$ … množina všech permutací
  • $A_i=\lbrace \pi \in S_n \mid \pi(i)=i\rbrace$
  • $A=\bigcup_{i=1}^n A_i$ … (množina všech „špatných“ permutací)
  • musíme vyjádřit velikosti průniků
    • permutací s $k$ pevnými body je $(n-k)!$
    • (protože permutuji všechny prvky kromě těch pevných)
  • dosazením do principu inkluze a exkluze vyjde $|A|=\sum_{k=1}^n(-1)^{k+1}{n\choose k}(n-k)!$
    • $n\choose k$ vyplývá z počtu prvků druhé sumy
    • ${n\choose k}(n-k)!={n!\over k!}$
  • $|A|=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}=n!\cdot\sum_{k=1}^n{(-1)^{k+1}\over k!}$
  • $|A|=n!({1\over 1!}-{1\over 2!}+{1\over 3!}-\dots+{(-1)^{n+1}\over n!})$
  • $š(n)=n!-|A|=n!\cdot(1-{1\over 1!}+{1\over 2!}-{1\over 3!}+\dots+{(-1)^n\over n!})$
    • závorka konverguje k $e^{-1}$
    • závorka odpovídá pravděpodobnosti v problému šatnářky
  • $š(n)=n!\cdot\sum_{k=0}^n\frac{(-1)^k}{k!}$
  • pravděpodobnost … $\sum_{k=0}^n\frac{(-1)^k}{k!}\approx e^{-1}$
• Věta: Odhad faktoriálu: $n^{n/2} \leq n! \leq ((n+1)/2)^n$
  • věta: Pro každé $n\geq 1$ platí $n^{n\over 2}\leq n!\leq ({n+1\over 2})^n$.
  • lemma: AG nerovnost $\frac{a+b}{2}\geq \sqrt{ab}$
    • $(\sqrt a - \sqrt b)^2\geq 0$
    • $a-2\sqrt{ab}+b\geq 0$
    • $a+b\geq 2\sqrt{ab}$
    • $\frac{a+b}{2}\geq \sqrt{ab}$
  • důkaz
    • $(n!)^2$ lze přerovnat jako $(1\cdot n)(2\cdot (n-1))\dots((n-1)\cdot 2)(n\cdot 1)$
    • to se rovná $\prod_{i=1}^n i(n+1-i)$
    • zvolíme-li v AG nerovnosti $a=i,b=n+1-i$, dostáváme
    • $\sqrt{i(n+1-i)}\leq {i+n+1-i\over 2}={n+1\over 2}$
    • z toho vyplývá $$n!=\prod_{i=1}^n \sqrt{i(n+1-i)}\leq \prod_{i=1}^n\frac{n+1}{2}=\left(\frac{n+1}{2}\right)^n$$
    • pro důkaz druhé nerovnosti uvažme součin $i(n+1-i)$
    • pro $i=1$ a $i=n$ je roven $n$
    • pro ostatní $i$ máme součin dvou čísel, z nichž větší je alespoň $n\over 2$ a menší je alespoň $2$, tedy součin je také nejméně $n$
    • platí tedy $i(n+1-i)\geq n$
    • tudíž $$(n!)^2=\prod_{i=1}^n {i(n+1-i)}\geq \prod_{i=1}^n n=n^n$$
    • tedy platí $n!\geq n^{n\over 2}$
• Věta: Odhad kombinačního čísla: $\left({n\over k}\right)^k \leq {n\choose k} \leq n^k$
  • horní odhad zřejmý z toho, že kombinační číslo lze zapsat jako ${n^{\underline k} \over k!}$
  • dolní odhad dokážeme pomocí ${n\choose k}=\prod_{i=0}^{k-1}{n-i\over k-i}$
  • $\frac{n-i}{k-i}\geq \frac nk$, což dokážeme:
  • $kn-ki \geq kn-in$
  • $in\geq ki$
  • $n\geq k$, což platí
• Věta: Odhad prostředního kombinačního čísla: $4^n/(2n+1) \leq {2n\choose n} \leq 4^n$
  • věta: ${4^n\over 2n+1}\leq {2n\choose n}\leq 4^n$
  • kombinačních čísel v jednom řádku Pascalova trojúhelníku je $2n+1$
  • odhadujeme prostřední – tedy největší z nich
  • ${4^n\over 2n+1}$ je průměr všech kombinačních čísel v řádku
  • $4^n$ je jejich součet

Grafy

• Definice: Graf, vrchol, hrana, V(G), E(G)
  • Graf je $(V, E)$, kde $V$ je konečná neprázdná množina vrcholů a $E \subseteq {V \choose 2}$ je množina hran.
  • Lze značit jako $G=(V,E)$. Potom $V(G)$ je množina vrcholů a $E(G)$ je množina hran.
• Definice: Standardní grafy: úplný, prázdný, cesta, kružnice
  • úplný graf $K_n$
    • $V(K_n):=[n]$
    • $E(K_n):={V(K_n)\choose 2}$
  • prázdný graf $E_n$
    • $V(E_n):=[n]$
    • $E(E_n) =\emptyset$
  • cesta $P_n$
    • $V(P_n):=\{0,\dots, n\}$
    • $E(P_n):=\{\{i,i+1\}\mid 0\leq i \lt n\}$
    • délka cesty se měří v počtu hran
  • kružnice/cyklus $C_n$
    • $n\geq 3$
    • $V(C_n):=\{0,\dots, n–1\}$
    • $E(C_n):=\{\{i,(i+1)\bmod n\}\mid 0\leq i \lt n\}$
• Definice: Bipartitní graf, úplný bipartitní graf
  • bipartitní graf
    • partity grafu – jednotlivé „strany“
    • Df: Graf (V, E) je bipartitní $\equiv \exists L,P\subseteq V$ t. ž.:
      • $L \cup P = V$
      • $L \cap P = \emptyset$
      • $\forall e \in E: |e \cap L| = 1\quad (\land\ |e \cap P| = 1)$
        • nebo $E(G)\subseteq\lbrace\lbrace x,y\rbrace\mid x\in L,y\in P\rbrace$
  • úplný bipartitní $K_{m,n}$
    • každý prvek nalevo je spojený s každým napravo
    • prvky na jedné straně mezi sebou nejsou spojeny
• Definice: Isomorfismus grafů
  • grafy jsou izomorfní $\equiv$ existuje bijekce, která zachovává vlastnost být spojen hranou
  • v podstatě stačí přejmenovat vrcholy a dostaneme dva stejné grafy
  • značení $\cong$
  • $\cong$ je ekvivalence na libovolné množině grafů
    • neexistuje množina všech grafů (protože neexistuje množina všech množin)
• Definice: Stupeň vrcholu, k-regulární graf, skóre grafu
  • stupeň vrcholu – počet hran, kterých se účastní daný vrchol
  • graf je k-regulární, pokud je stupeň všech vrcholů grafu roven k
  • skóre grafu = posloupnost stupňů vrcholů (až na pořadí) → jakmile dvěma grafům vyjde jiné skóre, nemohou být izomorfní
• Věta: Vztah mezi součtem stupňů a počtem hran, princip sudosti
  • věta: Pro každý graf $(V,E)$ platí $\sum_{v\in V} \text{deg}(v)=2\cdot |E|$.
  • důkaz: každá hrana spojuje dva vrcholy (do součtu stupňů přispívá 2×)
  • důsledek: princip sudosti
    • součet stupňů je sudý $\implies$ počet vrcholů lichého stupně je sudý
• Věta o skóre
  • věta: Posloupnost $D=d_1\leq d_2\leq\dots\leq d_n$ pro $n\geq 2$ je skóre grafu $\iff D'=d'_1,\dots,d'_{n-1}$ je skóre grafu $\land \ 0\leq d_n\leq n-1$.
    • přičemž $d'_i=\begin{cases}d_i &\text{pro } i\lt n-d_n\\ d_i-1 &\text{pro } i\geq n-d_n\end{cases}$
    • poznámka: pro $n=1$ je posloupnost $D$ skóre $\iff$ $d_1=0$
  • důkaz $\impliedby$
    • předpokládám existenci $G'$
    • vytvořím $G$ doplněním vrcholu $v_n$ a hran k $d_n$ posledním vrcholům v grafu $G'$
    • tak vznikne graf $G$ se skórem $D$
  • důkaz $\implies$
    • předpokládejme, že $D$ je skóre grafu
    • uvažme množinu $\mathcal G$ všech grafů se skórem $D$
    • pomocné tvrzení: v množině $\mathcal G$ existuje graf $G_0$, v němž je vrchol $v_n$ spojen s posledními $d_n$ vrcholy
    • stačí dokázat pomocné tvrzení
    • pokud $d_n=n-1$ (tedy $v_n$ je spojen se všemi ostatními vrcholy), vyhovuje pomocnému tvrzeni kterýkoliv graf z $\mathcal G$ a jsme hotovi
    • jinak definujeme $j(G)$, což je index toho z vrcholů nespojených s $v_n$, který má největší index
    • buď $G_0$ graf, pro něž je $j(G)$ nejmenší možné
    • dokážeme, že $j(G_0)=n-d_n-1$
    • pro spor předpokládejme, že $j\gt n-d_n-1$
    • vrchol $v_n$ je spojen s $d_n$ vrcholy, takže musí existovat $i\lt j$ takové, že $v_i$ je spojen s $v_n$
    • vzhledem k tomu, že $\text{deg}(v_i)\leq \text{deg}(v_j)$, existuje vrchol $v_k$, který je spojený hranou s $v_j$, ale nikoli s $v_i$
    • lze vytvořit $G'$, kde přepneme hrany
      • v $G_0$ jsou spojeny vrcholy s indexy $j,k; i,n$
      • v $G'$ tyto hrany nahradíme hranami $j,n;i,k$
      • skóre zůstane zachováno, ale $j(G')$ je nižší než $j(G_0)$, což je spor
• Definice: Podgraf, indukovaný podgraf
  • graf $G'=(V',E')$ je podgrafem grafu $G=(V,E)$ (značíme $G'\subseteq G$) $\equiv V'\subseteq V \land E'\subseteq E$
  • graf $G'=(V',E')$ je indukovaným podgrafem grafu $G=(V,E)$ $\equiv V'\subseteq V \land E'= E\cap {V'\choose 2}$
    • „podgraf indukovaný množinou vrcholů“
    • $G[A] := (A, E(G) \cap {A \choose 2})$, kde $A\subseteq V(G)$
• Definice: Cesta, kružnice, sled a tah v grafu
  • cesta v grafu
    • v grafu existuje podgraf izomorfní s $P_n$ pro nějaké $n$
      • $G'\subseteq G:G'\cong P_n$
    • v grafu existuje určitá posloupnost navzájem různých vrcholů a hran
      • $(v_0,e_1,v_1,e_2,v_2,\dots,e_n,v_n)$
      • $v_0,\dots,v_n$ jsou navzájem různé vrcholy
      • $e_1,\dots,e_n$ jsou hrany
      • $\forall i: e_i=\lbrace v_{i-1},v_i\rbrace$
  • kružnice v grafu
    • v grafu existuje podgraf izomorfní s $C_n$ pro nějaké $n$
      • $G'\subseteq G:G'\cong C_n$
    • v grafu existuje posloupnost navzájem různých vrcholů a hran
      • $(v_0,e_0,v_1,e_1,\dots,v_{n-1},e_{n-1},v_0)$
      • $v_0,\dots,v_{n-1}$ jsou navzájem různé vrcholy
      • $e_0,\dots,e_{n-1}$ jsou hrany
      • $\forall i: e_i=\lbrace v_{i},v_{(i+1)\bmod n}\rbrace$
  • sled v grafu (walk) – můžou se opakovat vrcholy i hrany
    • $(v_0,e_1,v_1,e_2,\dots,e_n,v_n)$
    • $\forall i: e_i=\lbrace v_{i-1},v_i\rbrace$
  • tah v grafu – můžou se opakovat vrcholy, hrany ne
• Definice: Souvislý graf, relace dosažitelnosti (ekvivalence), komponenty souvislosti
  • graf $G$ je souvislý $\equiv\forall u,v\in V(G):$ existuje cesta v $G$ s krajními vrcholy $u,v$
  • dosažitelnost v $G$ je relace $\sim$ na $V(G)$ t. ž. $u\sim v\equiv$ existuje cesta v $G$ s krajními vrcholy $u,v$
    • relace $\sim$ je ekvivalence
    • tranzitivita se dokazuje pomocí dvou posloupností vrcholů $x \sim y$ a $y\sim z$ a následně zvolení nejzazšího vrcholu z posloupnosti $y\sim z$, který je obsažen v posloupnosti $x\sim y$ a v tomto vrcholu se posloupnosti slepí (přičemž části za ním v první posloupnosti a před ním v druhé posloupnosti se ustřihnou)
  • komponenty souvislosti jsou podgrafy indukované třídami ekvivalence $\sim$
    • komponenty jsou souvislé
    • graf je souvislý $\iff$ má 1 komponentu
• Věta: Dosažitelnost sledem je totéž jako dosažitelnost cestou
  • lemma: $\exists$ cesta mezi $u,v\iff\exists$ sled mezi $u,v$
  • důkaz $\implies$ triviální
  • důkaz $\impliedby$
    • uvažme sled S
    • kdyby se ve sledu neopakovaly vrcholy, je to cesta
    • pokud $v_k=v_l$, kde $k\lt l$, vyřízneme část sledu mezi nimi → stále máme sled, který je kratší než ten původní
    • opakujeme, dokud S není cesta
• Definice: Matice sousednosti
  • matice sousednosti $A(G)$ grafu $G$
  • matice $n\times n$ nul a jedniček
  • při očíslování vrcholů $v_1,\dots,v_n\in V(G)$
  • $A_{ij}:=[\lbrace v_i,v_j\rbrace\in E]$
    • definice: indikátor $[\psi]$ je 0/1 podle platnosti výroku $\psi$
    • tzn. $A_{ij}=1$, pokud spolu $v_i, v_j$ tvoří hranu (jinak 0)
  • $A$ je symetrická, součty řádků/sloupců jsou stupně vrcholů
• Věta: Počet sledů délky k lze získat z k-té mocniny matice sousednosti
  • lemma: $A^t_{ij}=$ # sledů délky $t$ z $v_i$ do $v_j$
  • důkaz: indukcí podle t
    • $t=1$ … hrana = sled délky 1
    • $t\to t+1$
      • $A^{t+1}_{ij}=(A^tA)_{ij}=\sum_kA^t_{ik}A_{kj}$
        • $A^t_{ik}$ … (z IP) počet sledů délky $t$ z $v_i$ do $v_k$
        • $A_{kj}$ … tvoří $v_k,v_j$ hranu?
      • suma se tedy rovná součtu počtu sledů délky $t$ z $v_i$ do $v_k$ pro ta $k$, kde $v_k,v_j$ tvoří hranu
      • to se rovná počtu sledů délky $t+1$ z $v_i$ do $v_j$
• Definice: Vzdálenost v grafu (grafová metrika)
  • vzdálenost (grafová metrika) v souvislém grafu $G$
  • $d_G:V^2\to\mathbb R$
  • $d_G(u,v):=$ min. z délek (počtu hran) všech cest mezi $u,v$
  • vlastnosti metriky (funkce je metrika = chová se jako vzdálenost)
    • $d_G(u,v)\geq 0$
    • $d_G(u,v) = 0 \iff u=v$
    • platí trojúhelníková nerovnost $d_G(u,w) \leq d_G(u,w) + d_G(w,v)$
    • $d_G(v,u)=d_G(u,v)$
• Věta: Trojúhelníková nerovnost pro vzdálenost
  • $\forall u,v,w\in V(G): d(u,v)\leq d(u,w)+d(w,v)$
• Definice: Grafové operace: přidání/odebrání vrcholu/hrany, dělení hrany, kontrakce hrany
  • přidání vrcholu, přidání hrany, smazání hrany – vždy pouze úprava odpovídající množiny
  • odebrání vrcholu – musím odebrat odpovídající hrany
    • výsledný graf je podgraf indukovaný množinou všech vrcholů bez toho odebíraného
      • $G-v=G[V\setminus\{v\}]$
  • dělení hrany (pomocí nového vrcholu): G % e
    • $G\%e=(V\cup \lbrace x \rbrace, E\setminus\lbrace\lbrace u,v\rbrace\rbrace\cup\lbrace\lbrace u,x\rbrace,\lbrace v,x\rbrace\rbrace)$
  • kontrakce hrany: G.e
    • z vrcholů odebereme $u,v$, přidáme $x$
    • z hran odebereme hranu $u,v$, v hranách s $u$ nebo $v$ nahradíme daný vrchol vrcholem $x$
• Definice: Otevřený a uzavřený eulerovský tah
  • eulerovský tah obsahuje všechny vrcholy a hrany grafu
  • tah může být uzavřený (končí, kde začal), nebo otevřený
  • graf je eulerovský $\equiv$ existuje v něm uzavřený eulerovský tah
• Věta o existenci uzavřeného eulerovského tahu
  • věta: graf $G$ je eulerovský $\iff G$ je souvislý a každý jeho vrchol má sudý stupeň
  • důkaz $\implies$
    • souvislost plyne z dosažitelnosti libovolných dvou vrcholů po eulerovském tahu (tah je speciální případ sledu – když někde vede sled, tak tam vede i cesta)
    • kdykoliv jsme vrchol navštívili, vstupujeme a vystupujeme do něj po jiných hranách (hrany incidentní s $v$ rozdělíme do disjunktních dvojic $\implies \text{deg}(v)$ je sudý)
  • důkaz $\impliedby$
    • uvážíme nejdelší tah $T$ (respektive jeden z nejdelších tahů)
    • sporem dokážeme, že $T$ je uzavřený
      • kdyby nebyl uzavřený, obsahuje lichý počet hran incidentních s počátečním vrcholem $v$
      • $v$ má sudý stupeň $\implies$ existuje nepoužitá hrana incidentní s $v$
      • $T$ lze prodloužit o nepoužitou hranu $\implies$ existuje delší tah ↯
    • sporem dokážeme, že $T$ obsahuje všechny hrany
      • kdyby pro nějaké $u$ tah $T$ neobsahoval hranu $\lbrace u,v\rbrace$
        • (vrchol $v$ nemusí být na tahu $T$)
      • při nějakém průchodu vrcholem $u$ lze uzavřený tah rozpojit a na jeho konec přidat hranu $\lbrace u,v\rbrace$, čímž vznikne delší tah ↯
    • sporem dokážeme, že $T$ obsahuje všechny vrcholy
      • mějme vrchol $v\notin T$
      • zvolíme $u\in T$ libovolně
      • graf je souvislý $\implies$ existuje cesta $P$ mezi $u,v$
      • tedy musí existovat „nenakreslená“ hrana spojující „nakreslený“ a „nenakreslený“ vrchol
      • formálně $\exists r,s\in P:r\in T,s\notin T, \lbrace r,s\rbrace\in E(G)$
      • to je stejná situace jako v předchozím sporu ↯
• Definice: Orientovaný graf, podkladový graf, vstupní a výstupní stupeň, vyváženost vrcholu
  • orientovaný graf … $(V,E): E \subseteq V^2 \setminus \{(x,x)\mid x\in V\}$
    • nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)
  • podkladový graf je neorientovaný graf založený na tom původním orientovaném
    • pro orientovaný $G=(V,E)$ existuje podkladový $G^0=(V,E^0)$, kde $\lbrace u,v\rbrace \in E^0\equiv (u,v)\in E\lor (v,u)\in E$
  • vstupní a výstupní stupeň $\text{deg}^\text{in},\text{deg}^\text{out}$ (hrany vedoucí do vrcholu / z vrcholu)
  • vrchol je vyvážený $\equiv \text{deg}^\text{in}(v)=\text{deg}^\text{out}(v)$
  • graf je vyvážený $\equiv$ všechny vrcholy jsou vyvážené
  • součet vstupních stupňů = součet výstupních stupňů = počet hran
• Definice: Silná a slabá souvislost orientovaných grafů
  • orientovaný graf je slabě souvislý $\equiv$ jeho podkladový graf je souvislý
  • o. graf je silně souvislý $\equiv$ existuje orientovaná cesta mezi každými dvěma vrcholy
  • silná souvislost $\implies$ slabá souvislost
• Věta: Uzavřené eulerovské tahy v orientovaných grafech
  • věta: pro orientovaný graf $G$ platí: (1) $G$ je vyvážený a slabě souvislý $\iff$ (2) $G$ je eulerovský $\iff$ (3) $G$ je vyvážený a silně souvislý
  • důkaz
    • $3\implies 1\quad\checkmark$
    • $2\implies 3$
      • vyváženost – hran dovnitř je v každém vrcholu stejně jako hran ven
      • silná souvislost – pro každou dvojici vrcholů existuje orientovaný tah $u\to v\implies$ existuje orientovaná cesta $u\to v$
    • $1\implies 2$
      • stejný princip jako u věty o existenci uzavřeného eulerovského tahu v neorientovaném grafu
      • sudý stupeň vrcholu v podstatě odpovídá vyváženosti vrcholu

Stromy

• Definice: Strom, les, list
  • strom je souvislý graf bez kružnic (= acyklický)
  • les je acyklický graf
  • list je vrchol stupně 1
    • strom o jednom vrcholu nemá žádný list
• Lemma o koncovém vrcholu
  • lemma: Každý strom s aspoň 2 vrcholy má aspoň 1 list (respektive aspoň dva listy).
  • důkaz
    • nechť $P$ je nejdelší cesta ve stromu
    • dokážeme, že koncové vrcholy cesty $P$ jsou listy
    • kdyby z koncového vrcholu $v$ vedla hrana do vrcholu, který neleží na cestě $P$, dala by se cesta $P$ o tuto hranu prodloužit, což by byl spor s tím, že jde o nejdelší cestu
    • kdyby z koncového vrcholu $v$ vedle hrana do vrcholu, který leží na cestě $P$, byla by v grafu kružnice, což by byl spor s acykličností stromu
    • tudíž musí být oba koncové vrcholy listy
• Lemma o trhání listů
  • lemma: Je-li $v$ list grafu $G$, pak $G$ je strom, právě když $G-v$ je strom.
  • důkaz $\implies$
    • $G-v$ je souvislý, protože pokud mezi dvěma vrcholy existovala cesta v $G$, tak existuje i v $G-v$, neboť list nikdy není vnitřním vrcholem cesty
    • $G-v$ je acyklický, protože odstraněním vrcholu a hrany nemůže vzniknout kružnice
      • jiná formulace: kdyby $C\subseteq G-v \subseteq G$, pak $C\subseteq G$ (kružnice by existovala v původním grafu, což by byl spor)
  • důkaz $\impliedby$
    • $G$ je souvislý, protože přidáním listu nerozbiju cestu a díky tranzitivitě dosažitelnosti je nový list $v$ dosažitelný ze všech vrcholů grafu stejně jako jeho soused $s$, ke kterému jsme $v$ připojili
    • $G$ je acyklický, protože list se nemůže účastnit kružnice, takže pokud $G-v$ neměl kružnici, tak ani $G$ nemá kružnici
• Věta: Pět ekvivalentních charakteristik stromu
  • pro graf G jsou následující tvrzení ekvivalentní:
    1. G je souvislý a acyklický (strom)
    2. mezi vrcholy $u, v$ existuje právě jedna cesta (jednoznačně souvislý)
    3. G je souvislý a po smazání libovolné jedné hrany už nebude souvislý (minimální souvislý)
    4. G je acyklický a po přidání libovolné jedné hrany vznikne cyklus (maximální acyklický)
    5. G je souvislý a platí pro něj Eulerova formule $|E(G)|=|V(G)|-1$
  • důkaz
    • $1\implies 2$
      • indukcí otrháváním listů
      • IP: $G-l$ je strom $\implies$ $G-l$ je jednoznačně souvislý
      • dokážeme, že $G$ je jednoznačně souvislý
      • přidání listu nevytvoří nové cesty mezi vrcholy, které byly už v $G-l$, protože list nemůže být vnitřním vrcholem cesty
      • každá cesta do $l$ vede přes souseda $s$
      • jelikož v původním grafu do souseda existovala právě jedna cesta mezi libovolným $v$ a sousedem $s$, musí existovat právě jedna cesta mezi libovolným $v$ a listem $l$
        • existuje bijekce mezi $l,v$-cestami v $G$ a $s,v$-cestami v $G-l$
    • $1\implies 3$
      • podobná indukce
      • $G-l$ je mimimální souvislý
      • minimální souvislost je zachována
        • když zruším hranu $s,l$, tak se to rozpadne
        • když zruším jinou hranu, tak se to rozpadne taky, protože $G-l$ by se rozpadlo a (nově přidaný) list není vrcholem žádné cesty
    • $1\implies 4$
      • opět indukce
      • když přidám hranu mezi vrcholy v $G-l$, tak to řeší IP
      • když přidám hranu mezi $l$ a vrcholem v $G-l$, tak vzniká cyklus
        • protože $G$ je souvislý, tudíž mezi $l$ a libovolným jiným vrcholem už nějaká cesta existuje
    • $1\implies 5$
      • indukcí podle $n:=|V(T)|$
      • $n=1\quad 0=|E(T)|=|V(T)|-1=1-1$
      • $n\to n+1$
        • $T$ je strom na $n+1$ vrcholech
        • $T$ má list
        • $T':=T-l$ je strom na $n$ vrcholech
        • z IP: $|E(T')|=n-1$
        • vrácení $l$ zvýší počet hran i vrcholů o 1
        • takže $|E(T)|=|E(T')|+1=n=(n+1)-1 \quad\square$
    • $2\implies 1$
      • obměnou, tedy $\neg 1\implies\neg 2$
      • když graf není souvislý, tak není jednoznačně souvislý
      • když graf není acyklický, tak má kružnici, přičemž mezi vrcholy na kružnici neexistuje jednoznačná cesta
    • $3\implies 1$
      • obměnou, tedy $\neg 1\implies \neg 3$
      • když graf není souvislý, tak není minimální souvislý
      • když má kružnici, tak není minimální souvislý, protože můžu odstranit hranu na kružnici a souvislost se zachová
    • $4\implies 1$
      • obměnou, tedy $\neg 1\implies \neg 4$
      • když není acyklický, není maximální acyklický
      • když není souvislý, můžu přidat hranu (most) a nevytvořím kružnici, takže graf nemohl být maximální acyklický
    • $5\implies 1$
      • dokážeme, že souvislý graf splňující Eulerovu formuli má list
        • součet stupňů je roven dvojnásobku počtu hran
        • $\sum\text{deg}(v_i)=2|E|=2n-2$ (z Eulerovy formule)
        • průměrný stupeň $=\frac{2n-2}{n}<2$
        • graf je souvislý a netriviální, takže alespoň jeden vrchol musí mít stupeň 1 $\implies$ graf má list
      • důkaz indukcí podle $n:=|V(G)|$
        • $n=1$ platí triviálně (graf je strom, takže implikace platí)
        • $n\to n+1$
          • mějme graf $G$, který splňuje (5) a má list $v$ – viz výše
          • $G-v$ pořád splňuje (5)
          • podle IP je $G-v$ strom
          • $\implies G$ je strom
• Definice: Kostra grafu
  • kostra grafu je podgraf, který obsahuje všechny vrcholy původního grafu a je to strom
• Věta: Graf má kostru, právě když je souvislý.
  • lemma: $G$ má kostru $\iff G$ je souvislý
  • $\implies$
    • kostra je strom, strom je souvislý, každé dva vrcholy jsou spojené cestou
    • kostra je podgrafem $G$, takže tyto cesty existují i v $G$, tudíž i $G$ je souvislý
  • $\impliedby$
    • $G$ je souvislý
    • když je acyklický, tak mám kostru
    • když není acyklický, tak odebírám hrany na cyklech tak dlouho, dokud není acyklický, čímž dostanu kostru