Příklad: Technika důkazu indukcí a sporem; - věta: Prvočísel je nekonečně mnoho.<br>- důkaz sporem<br>	- kdyby $p_1,\dots,p_n$ byla všechna prvočísla<br>	- $\zeta := p_1\cdot p_2 \cdot \ldots\cdot p_n$<br>	- $(\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 ↯<br>- věta: $\forall n \in \mathbb N: 2^0+2^1+2^2+\dots+2^n=2^{n+1}-1$<br>- důkaz indukcí podle n<br>	- $2^0=2^1-1$<br>	- indukční krok<br>		- IP: $2^0+2^1+2^2+\dots+2^n=2^{n+1}-1$<br>		- chceme: $2^0+2^1+2^2+\dots+2^n+2^{n+1}=2^{n+2}-1$<br>		- 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é<br>- horní celá část se značí $\lceil x \rceil$, zaokrouhluje nahoru<br>- 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)$<br>- 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)$<br>	- lze zavést pomocí klasických množin jako $\lbrace \lbrace x \rbrace, \lbrace x,y\rbrace\rbrace$<br>	- uspořádaná k-tice $(x_1,\dots,x_k)$<br>- kartézský součin $A\times B:=\lbrace(a,b)\mid a\in A, b\in B \rbrace$<br>	- $A^k:=\underbrace{A\times A \times \dots \times A}_k$
Definice: Relace mezi množinami, relace na množině; - (binární) relace mezi množinami $X,Y$ je podmnožina $X\times Y$<br>- relace na množině $X$ je podmnožina $X^2$<br>- 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$<br>- univerzální $X\times Y$<br>- 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<br>	- 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$<br>- skládání<br>	- pro relaci $R$ mezi $X,Y$ a relaci $S$ mezi $Y,Z$ lze definovat složenou relaci $T=R\circ S$ mezi $X,Z$<br>	- $xTz \equiv \exists y \in Y: xRy \land ySz$<br>	- $R\circ \Delta_Y =R,\quad \Delta_X\circ R = R$<br>	- 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$<br>- funkce $f:X\to Y$ je…<br>- prostá (injektivní) $\equiv \nexists x,x' \in X: x \neq x' \land f(x)=f(x')$<br>- na Y (surjektivní) $\equiv (\forall y \in Y)(\exists x \in X): f(x)=y$<br>- vzájemně jednoznačná (bijektivní) $\equiv (\forall y \in Y)(\exists! x \in X):f(x)=y$<br>	- taková funkce je tedy prostá i „na“<br>	- k takové funkci existuje inverzní funkce $f^{-1}$ z Y do X
Definice: Vlastnosti relací: reflexivita, symetrie, antisymetrie, transitivita; - relace R na X je…<br>- reflexivní $\equiv \forall x \in X: xRx$<br>	- $\Delta_X \subseteq R$<br>- symetrická $\equiv \forall x,y \in X: xRy \implies yRx$<br>	- $R=R^{-1}$<br>- antisymetrická $\equiv \forall x,y \in X: xRy \land yRx \implies x=y$<br>	- $R\cap R^{-1}\subseteq \Delta_X$<br>- tranzitivní $\equiv \forall x,y,z \in X: xRy \land yRz \implies xRz$<br>	- $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í<br>	- např. rovnost čísel, rovnost mod K, geometrická podobnost<br>- ekvivalenční třída prvku $x \in X:R[x]=\lbrace y \in X \mid xRy\rbrace$<br>- množinový systém $\mathcal S\subseteq 2^X$ je rozklad množiny $X \equiv$<br>	- $\forall A \in \mathcal S: A \neq \emptyset$<br>	- $\forall A,B\in \mathcal S: A\neq B \implies A \cap B = \emptyset$<br>	- $\bigcup_{A\in \mathcal S}A=X$
Věta: Vztah mezi ekvivalencemi a rozklady; - věta<br>	- (1) $\forall x \in X: R[x]\neq \emptyset$<br>	- (2) $\forall x,y \in X:$ buď $R[x]=R[y]$, nebo $R[x] \cap R[y]=\emptyset$<br>	- (3) $\lbrace R[x] \mid x \in X\rbrace$ (množina všech ekvivalenčních tříd) určuje ekvivalenci R jednoznačně<br>- důkaz<br>	- (1) ekvivalence je reflexivní, tedy nutně platí $x \in R[x]$, tudíž je ta ekvivalenční třída neprázdná<br>	- (2) dokážeme, že pokud nejsou disjunktní, tak se rovnají<br>		- platí $R[x]\cap R[y]\neq \emptyset$<br>		- dokazujeme $R[x]=R[y]$, stačí nám $R[x]\subseteq R[y]$ (opačnou inkluzi lze dokázat podobným způsobem)<br>		- víme $\exists t \in R[x]\cap R[y]$<br>			- tedy platí xRt, tRx, yRt, tRy<br>		- chceme $\forall a \in R[x]: a \in R[y]$<br>		- dále aplikujeme tranzitivitu<br>		- $aRx \land xRt \implies aRt$<br>		- $aRt \land tRy \implies aRy$<br>	- (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
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í<br>- (částečně) uspořádaná množina $(X,R)$<br>	- zkráceně ČUM<br>	- R je (částečné) uspořádání na X<br>- prvky $x,y \in X$ jsou porovnatelné $\equiv xRy \lor yRx$<br>- uspořádání je lineární $\equiv \forall x,y\in X$ porovnatelné<br>	- (všechny prvky množiny jsou navzájem porovnatelné)<br>- částečné uspořádání (nebo pouze uspořádání) je obecný pojem, některá taková uspořádání jsou navíc lineární<br>- 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$ <br>	- pozor – ostré uspořádání není speciálním případem uspořádání (protože není reflexivní)<br>	- 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)$<br>	- $2\backslash 4$<br>	- $4,6$ neporovnatelné<br>	- dělitelnost na reálných čísel (bez nuly) není uspořádání, protože $(-1)\backslash1\land 1\backslash (-1)$ (není antisymetrické)<br>- inkluze $(2^X,\subseteq)$<br>	- $\lbrace 1 \rbrace \subseteq \lbrace 1,3 \rbrace$<br>	- $\lbrace 1,2 \rbrace, \lbrace 2,3 \rbrace$ neporovnatelné<br>- lexikografické uspořádání<br>	- abeceda: $(X, \leq)$<br>	- Df: $(X^2,\leq_{lex})$<br>	- $(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)$<br>	- $(X^k, \leq_{lex})$<br>	- $(X^*, \leq_{lex})$<br>		- X* – konečné posloupnosti prvků z X<br>	- 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)<br>- $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)$<br>	- 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$<br>- prvek $x\in X$ je minimální $\equiv \nexists y \in X: y\lt x$<br>- x je nejmenší $\implies$ x je minimální<br>- v Hassově diagramu<br>	- z minimálního prvku dolů nevede žádná spojnice<br>	- 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<br>	- zvolíme $x_1 \in X$ libovolně<br>	- buď je $x_1$ minimální, nebo $\exists x_2 \lt x_1$<br>	- buď je $x_2$ minimální, nebo $\exists x_3\lt x_2$<br>	- atd.<br>	- 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:<br>- $A\subseteq X$ je řetězec $\equiv \forall a,b \in A: a,b$ jsou porovnatelné<br>- $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í)<br>- $\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|$<br>	- řetězec: $A\subseteq X:\forall a,b\in A: a\leq b\lor b\leq a$<br>	- antiřetězec: $A\subseteq X:\forall a,b\in A,\;a\neq b: \neg(a\leq b\lor b\leq a)$<br>	- maximální velikost řetězce … $\omega$ („výška“)<br>	- maximální velikost antiřetězce … $\alpha$ („šířka“)<br>	- důsledek věty: $\text{max}(\alpha,\omega)\geq\sqrt{|X|}$<br>- důkaz<br>	- najdeme všechny minimální prvky → vrstva $X_1$<br>	- smažu $X_1$, proces opakuju → najdu $X_2$<br>	- tak postupuju dál, dokud nerozkrájím celou ČUM<br>	- každá vrstva tvoří antiřetězec<br>	- vrstvy jsou rozklad<br>	- existuje množina taková, že každý prvek je z jiné vrstvy a dohromady tvoří řetězec<br>		- formálně $\exists\lbrace q_1,\dots,q_k\rbrace$ řetězec t. ž. $\forall i: q_i\in X_i$<br>		- jak je to možné?<br>			- $q_{i+1}$ je ve vrstvě $X_{i+1}$, protože nějaký prvek $q_i$ je menší – ten je ve vrstvě $X_i$
Věta: Počet funkcí mezi množinami; - věta: počet $f:N\to M=m^n$<br>	- pro $|N|=n, |M|=m;\quad m,n\gt 0$<br>- důkaz indukcí podle $n$<br>	- $n=1\quad$ \# $f=m=m^1$<br>	- $n\to n+1$<br>		- (n+1)-prvková N, m-prvková M<br>		- zvolíme $x\in N$<br>		- $f':N\setminus\lbrace x \rbrace\to M$<br>		- podle IP existuje $m^n$ funkcí $f'$<br>		- zadat zobrazení $f$ je totéž jako zadat hodnotu $f(x)\in M$ plus zobrazení $f'$<br>		- hodnotu $f(x)$ lze zvolit $m$ způsoby<br>		- celkem tedy $m^n\cdot m=m^{n+1}$<br>- 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)<br>- důkaz indukcí podle $n$<br>	- podobně jako předchozí důkaz<br>	- $n\to n+1$<br>		- $f':N\setminus\lbrace x \rbrace\to M\setminus\lbrace f(x) \rbrace$<br>		- podle IP existuje $(m-1)^\underline n$ funkcí $f'$<br>		- hodnotu $f(x)$ lze zvolit $m$ způsoby<br>		- celkem tedy $(m-1)^\underline n \cdot m=m^\underline{n+1}$<br>- 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$<br>- $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|}$<br>- 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}$.<br>- důkaz<br>	- víme, že $\mathcal S\cup\mathcal L=2^X$<br>	- stačí $|\mathcal S|=|\mathcal L|$<br>	- sestrojíme $f:\mathcal S\to \mathcal L$ bijekci<br>	- zvolíme si $a\in X$<br>	- $f(S):=S\bigtriangleup \lbrace a\rbrace$ (prvek a přidáme nebo odebereme, podle toho, zda je prvkem S, nebo není)<br>	- $f(S)\in \mathcal L$<br>	- $f$ má inverzi $f^{-1}=f$
Věta: Počet permutací na množině; - definice: $[n]=\lbrace1,2,\dots,n\rbrace$<br>- věta: na množině $[n]$ existuje $n!$ permutací (podobně na každé n-prvkové množině)<br>- 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$<br>- u uspořádaných k-tic bez opakování hledáme prosté funkce, tedy $|X|^\underline k$<br>- pomocí „počítání dvěma způsoby“ odvodíme vzorec pro neuspořádané k-tice (k-prvkové podmnožiny)<br>- 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)<br>- 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)!}$<br>- 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<br>- ${n-1\choose k-1}+{n-1\choose k}={n\choose k}$<br>	- 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$<br>- důkaz<br>	- jeden člen výsledného součtu – součin n věcí, z nichž každá bude x nebo y<br>	- z každé závorky vyberu x nebo y<br>	- výsledkem je člen $x^{n-k}y^k$<br>	- 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|$$<br>- důkaz<br>	- pro prvek $x$ ve sjednocení spočítáme příspěvky k levé (vždy 1) a pravé straně<br>	- nechť $x$ patří do právě $t$ množin<br>	- průniky k-tic<br>		- $k \gt t$ … přispěje 0<br>		- $k\leq t$ … přispěje $(-1)^{k+1}{t\choose k}$<br>			- vybíráme k-tice množin z t-množin, do kterých prvek patří<br>			- minus jednička vychází ze vzorce<br>		- chceme $\sum_{k=1}^t(-1)^{k+1}{t\choose k}=1$<br>		- lze upravit na $\sum_{k=1}^t(-1)^{k}{t\choose k}=-1$<br>		- z binomické věty $0=(1-1)^t=\sum_{k=0}^t{t\choose k}(-1)^{k}$<br>		- tedy bez prvního členu se součet rovná $-1\quad \square$<br>- 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?<br>- jaká je pravděpodobnost, že náhodně zvolená permutace nebude mít žádný pevný bod<br>- každá z $n!$ permutací je stejně pravděpodobná<br>- $š(n)$ … počet permutací bez pevného bodu<br>- pravděpodobnost je rovna $š(n)/n!$<br>- $S_n$ … množina všech permutací<br>- $A_i=\lbrace \pi \in S_n \mid \pi(i)=i\rbrace$<br>- $A=\bigcup_{i=1}^n A_i$ … (množina všech „špatných“ permutací)<br>- musíme vyjádřit velikosti průniků<br>	- permutací s $k$ pevnými body je $(n-k)!$<br>	- (protože permutuji všechny prvky kromě těch pevných)<br>- dosazením do principu inkluze a exkluze vyjde $|A|=\sum_{k=1}^n(-1)^{k+1}{n\choose k}(n-k)!$<br>	- $n\choose k$ vyplývá z počtu prvků druhé sumy<br>	- ${n\choose k}(n-k)!={n!\over k!}$<br>- $|A|=\sum_{k=1}^n(-1)^{k+1}\frac{n!}{k!}=n!\cdot\sum_{k=1}^n{(-1)^{k+1}\over k!}$<br>- $|A|=n!({1\over 1!}-{1\over 2!}+{1\over 3!}-\dots+{(-1)^{n+1}\over n!})$<br>- $š(n)=n!-|A|=n!\cdot(1-{1\over 1!}+{1\over 2!}-{1\over 3!}+\dots+{(-1)^n\over n!})$<br>	- závorka konverguje k $e^{-1}$<br>	- závorka odpovídá pravděpodobnosti v problému šatnářky<br>- $š(n)=n!\cdot\sum_{k=0}^n\frac{(-1)^k}{k!}$<br>- 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$.<br>- lemma: AG nerovnost $\frac{a+b}{2}\geq \sqrt{ab}$<br>	- $(\sqrt a - \sqrt b)^2\geq 0$<br>	- $a-2\sqrt{ab}+b\geq 0$<br>	- $a+b\geq 2\sqrt{ab}$<br>	- $\frac{a+b}{2}\geq \sqrt{ab}$<br>- důkaz<br>	- $(n!)^2$ lze přerovnat jako $(1\cdot n)(2\cdot (n-1))\dots((n-1)\cdot 2)(n\cdot 1)$<br>	- to se rovná $\prod_{i=1}^n i(n+1-i)$<br>	- zvolíme-li v AG nerovnosti $a=i,b=n+1-i$, dostáváme<br>	- $\sqrt{i(n+1-i)}\leq {i+n+1-i\over 2}={n+1\over 2}$<br>	- 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$$<br>	- pro důkaz druhé nerovnosti uvažme součin $i(n+1-i)$<br>	- pro $i=1$ a $i=n$ je roven $n$<br>	- 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$<br>	- platí tedy $i(n+1-i)\geq n$<br>	- tudíž $$(n!)^2=\prod_{i=1}^n {i(n+1-i)}\geq \prod_{i=1}^n n=n^n$$<br>	- 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!}$<br>- dolní odhad dokážeme pomocí ${n\choose k}=\prod_{i=0}^{k-1}{n-i\over k-i}$<br>- $\frac{n-i}{k-i}\geq \frac nk$, což dokážeme:<br>- $kn-ki \geq kn-in$<br>- $in\geq ki$<br>- $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$<br>- kombinačních čísel v jednom řádku Pascalova trojúhelníku je $2n+1$<br>- odhadujeme prostřední – tedy největší z nich<br>- ${4^n\over 2n+1}$ je průměr všech kombinačních čísel v řádku<br>- $4^n$ je jejich součet
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.<br>- 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$<br>	- $V(K_n):=[n]$<br>	- $E(K_n):={V(K_n)\choose 2}$<br>- prázdný graf $E_n$<br>	- $V(E_n):=[n]$<br>	- $E(E_n) =\emptyset$<br>- cesta $P_n$<br>	- $V(P_n):=\{0,\dots, n\}$<br>	- $E(P_n):=\{\{i,i+1\}\mid 0\leq i \lt n\}$<br>	- délka cesty se měří v počtu hran<br>- kružnice/cyklus $C_n$<br>	- $n\geq 3$<br>	- $V(C_n):=\{0,\dots, n–1\}$<br>	- $E(C_n):=\{\{i,(i+1)\bmod n\}\mid 0\leq i \lt n\}$
Definice: Bipartitní graf, úplný bipartitní graf; - bipartitní graf<br>	- partity grafu – jednotlivé „strany“<br>	- Df: Graf (V, E) je bipartitní $\equiv \exists L,P\subseteq V$ t. ž.:<br>		- $L \cup P = V$<br>		- $L \cap P = \emptyset$<br>		- $\forall e \in E: |e \cap L| = 1\quad (\land\ |e \cap P| = 1)$<br>			- nebo $E(G)\subseteq\lbrace\lbrace x,y\rbrace\mid x\in L,y\in P\rbrace$<br>- úplný bipartitní $K_{m,n}$<br>	- každý prvek nalevo je spojený s každým napravo<br>	- 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<br>- v podstatě stačí přejmenovat vrcholy a dostaneme dva stejné grafy<br>- značení $\cong$<br>- $\cong$ je ekvivalence na libovolné množině grafů<br>	- 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<br>- graf je k-regulární, pokud je stupeň všech vrcholů grafu roven k<br>- 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|$.<br>- důkaz: každá hrana spojuje dva vrcholy (do součtu stupňů přispívá 2×)<br>- důsledek: princip sudosti<br>	- 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$.<br>	- 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}$<br>	- poznámka: pro $n=1$ je posloupnost $D$ skóre $\iff$ $d_1=0$<br>- důkaz $\impliedby$<br>	- předpokládám existenci $G'$<br>	- vytvořím $G$ doplněním vrcholu $v_n$ a hran k $d_n$ posledním vrcholům v grafu $G'$<br>	- tak vznikne graf $G$ se skórem $D$<br>- důkaz $\implies$<br>	- předpokládejme, že $D$ je skóre grafu<br>	- uvažme množinu $\mathcal G$ všech grafů se skórem $D$<br>	- 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<br>	- stačí dokázat pomocné tvrzení<br>	- 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<br>	- jinak definujeme $j(G)$, což je index toho z vrcholů nespojených s $v_n$, který má největší index<br>	- buď $G_0$ graf, pro něž je $j(G)$ nejmenší možné<br>	- dokážeme, že $j(G_0)=n-d_n-1$<br>	- pro spor předpokládejme, že $j\gt n-d_n-1$<br>	- 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$<br>	- 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$<br>	- lze vytvořit $G'$, kde přepneme hrany<br>		- v $G_0$ jsou spojeny vrcholy s indexy $j,k; i,n$<br>		- v $G'$ tyto hrany nahradíme hranami $j,n;i,k$<br>		- 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$<br>- graf $G'=(V',E')$ je indukovaným podgrafem grafu $G=(V,E)$ $\equiv V'\subseteq V \land E'= E\cap {V'\choose 2}$<br>	- „podgraf indukovaný množinou vrcholů“<br>	- $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<br>	- v grafu existuje podgraf izomorfní s $P_n$ pro nějaké $n$<br>		- $G'\subseteq G:G'\cong P_n$<br>	- v grafu existuje určitá posloupnost navzájem různých vrcholů a hran<br>		- $(v_0,e_1,v_1,e_2,v_2,\dots,e_n,v_n)$<br>		- $v_0,\dots,v_n$ jsou navzájem různé vrcholy<br>		- $e_1,\dots,e_n$ jsou hrany<br>		- $\forall i: e_i=\lbrace v_{i-1},v_i\rbrace$<br>- kružnice v grafu<br>	- v grafu existuje podgraf izomorfní s $C_n$ pro nějaké $n$<br>		- $G'\subseteq G:G'\cong C_n$<br>	- v grafu existuje posloupnost navzájem různých vrcholů a hran<br>		- $(v_0,e_0,v_1,e_1,\dots,v_{n-1},e_{n-1},v_0)$<br>		- $v_0,\dots,v_{n-1}$ jsou navzájem různé vrcholy<br>		- $e_0,\dots,e_{n-1}$ jsou hrany<br>		- $\forall i: e_i=\lbrace v_{i},v_{(i+1)\bmod n}\rbrace$<br>- sled v grafu (walk) – můžou se opakovat vrcholy i hrany<br>	- $(v_0,e_1,v_1,e_2,\dots,e_n,v_n)$<br>	- $\forall i: e_i=\lbrace v_{i-1},v_i\rbrace$<br>- 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$<br>- 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$<br>	- relace $\sim$ je ekvivalence<br>	- 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)<br>- komponenty souvislosti jsou podgrafy indukované třídami ekvivalence $\sim$<br>	- komponenty jsou souvislé<br>	- 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$<br>- důkaz $\implies$ triviální<br>- důkaz $\impliedby$<br>	- uvažme sled S<br>	- kdyby se ve sledu neopakovaly vrcholy, je to cesta<br>	- 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í<br>	- opakujeme, dokud S není cesta
Definice: Matice sousednosti; - matice sousednosti $A(G)$ grafu $G$<br>- matice $n\times n$ nul a jedniček<br>- při očíslování vrcholů $v_1,\dots,v_n\in V(G)$<br>- $A_{ij}:=[\lbrace v_i,v_j\rbrace\in E]$<br>	- definice: indikátor $[\psi]$ je 0/1 podle platnosti výroku $\psi$<br>	- tzn. $A_{ij}=1$, pokud spolu $v_i, v_j$ tvoří hranu (jinak 0)<br>- $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$<br>- důkaz: indukcí podle t<br>	- $t=1$ … hrana = sled délky 1<br>	- $t\to t+1$<br>		- $A^{t+1}_{ij}=(A^tA)_{ij}=\sum_kA^t_{ik}A_{kj}$<br>			- $A^t_{ik}$ … (z IP) počet sledů délky $t$ z $v_i$ do $v_k$<br>			- $A_{kj}$ … tvoří $v_k,v_j$ hranu?<br>		- 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<br>		- 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$<br>- $d_G:V^2\to\mathbb R$<br>- $d_G(u,v):=$ min. z délek (počtu hran) všech cest mezi $u,v$<br>- vlastnosti metriky (funkce je metrika = chová se jako vzdálenost)<br>	- $d_G(u,v)\geq 0$<br>	- $d_G(u,v) = 0 \iff u=v$<br>	- platí trojúhelníková nerovnost $d_G(u,w) \leq d_G(u,w) + d_G(w,v)$<br>	- $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<br>- odebrání vrcholu – musím odebrat odpovídající hrany<br>	- výsledný graf je podgraf indukovaný množinou všech vrcholů bez toho odebíraného<br>		- $G-v=G[V\setminus\{v\}]$<br>- dělení hrany (pomocí nového vrcholu): G % e<br>	- $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)$<br>- kontrakce hrany: G.e<br>	- z vrcholů odebereme $u,v$, přidáme $x$<br>	- 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<br>- tah může být uzavřený (končí, kde začal), nebo otevřený<br>- 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ň<br>- důkaz $\implies$<br>	- 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)<br>	- 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ý)<br>- důkaz $\impliedby$<br>	- uvážíme nejdelší tah $T$ (respektive jeden z nejdelších tahů)<br>	- sporem dokážeme, že $T$ je uzavřený<br>		- kdyby nebyl uzavřený, obsahuje lichý počet hran incidentních s počátečním vrcholem $v$<br>		- $v$ má sudý stupeň $\implies$ existuje nepoužitá hrana incidentní s $v$<br>		- $T$ lze prodloužit o nepoužitou hranu $\implies$ existuje delší tah  ↯<br>	- sporem dokážeme, že $T$ obsahuje všechny hrany<br>		- kdyby pro nějaké $u$ tah $T$ neobsahoval hranu $\lbrace u,v\rbrace$<br>			- (vrchol $v$ nemusí být na tahu $T$)<br>		- 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 ↯<br>	- sporem dokážeme, že $T$ obsahuje všechny vrcholy<br>		- mějme vrchol $v\notin T$<br>		- zvolíme $u\in T$ libovolně<br>		- graf je souvislý $\implies$ existuje cesta $P$ mezi $u,v$<br>		- tedy musí existovat „nenakreslená“ hrana spojující „nakreslený“ a „nenakreslený“ vrchol<br>		- formálně $\exists r,s\in P:r\in T,s\notin T, \lbrace r,s\rbrace\in E(G)$<br>		- 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\}$<br>	- nepovolíme smyčky (v podstatě zakážeme diagonálu na relaci)<br>- podkladový graf je neorientovaný graf založený na tom původním orientovaném<br>	- 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$<br>- vstupní a výstupní stupeň $\text{deg}^\text{in},\text{deg}^\text{out}$ (hrany vedoucí do vrcholu / z vrcholu)<br>- vrchol je vyvážený $\equiv \text{deg}^\text{in}(v)=\text{deg}^\text{out}(v)$<br>- graf je vyvážený $\equiv$ všechny vrcholy jsou vyvážené<br>- 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ý<br>- o. graf je silně souvislý $\equiv$ existuje orientovaná cesta mezi každými dvěma vrcholy<br>- 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ý<br>- důkaz<br>	- $3\implies 1\quad\checkmark$<br>	- $2\implies 3$<br>		- vyváženost – hran dovnitř je v každém vrcholu stejně jako hran ven<br>		- silná souvislost – pro každou dvojici vrcholů existuje orientovaný tah $u\to v\implies$ existuje orientovaná cesta $u\to v$<br>	- $1\implies 2$<br>		- stejný princip jako u věty o existenci uzavřeného eulerovského tahu v neorientovaném grafu<br>		- sudý stupeň vrcholu v podstatě odpovídá vyváženosti vrcholu
Definice: Strom, les, list; - strom je souvislý graf bez kružnic (= acyklický)<br>- les je acyklický graf<br>- list je vrchol stupně 1<br>	- 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).<br>- důkaz<br>	- nechť $P$ je nejdelší cesta ve stromu<br>	- dokážeme, že koncové vrcholy cesty $P$ jsou listy<br>	- 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<br>	- 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<br>	- 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.<br>- důkaz $\implies$<br>	- $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<br>	- $G-v$ je acyklický, protože odstraněním vrcholu a hrany nemůže vzniknout kružnice<br>		- 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)<br>- důkaz $\impliedby$<br>	- $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<br>	- $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í:<br>	1. G je souvislý a acyklický (strom)<br>	2. mezi vrcholy $u, v$ existuje právě jedna cesta (jednoznačně souvislý)<br>	3. G je souvislý a po smazání libovolné jedné hrany už nebude souvislý (minimální souvislý)<br>	4. G je acyklický a po přidání libovolné jedné hrany vznikne cyklus (maximální acyklický)<br>	5. G je souvislý a platí pro něj Eulerova formule $|E(G)|=|V(G)|-1$<br>- důkaz<br>	- $1\implies 2$<br>		- indukcí otrháváním listů<br>		- IP: $G-l$ je strom $\implies$ $G-l$ je jednoznačně souvislý<br>		- dokážeme, že $G$ je jednoznačně souvislý<br>		- 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<br>		- každá cesta do $l$ vede přes souseda $s$<br>		- 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$<br>			- existuje bijekce mezi $l,v$-cestami v $G$ a $s,v$-cestami v $G-l$<br>	- $1\implies 3$<br>		- podobná indukce<br>		- $G-l$ je mimimální souvislý<br>		- minimální souvislost je zachována<br>			- když zruším hranu $s,l$, tak se to rozpadne<br>			- 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<br>	- $1\implies 4$<br>		- opět indukce<br>		- když přidám hranu mezi vrcholy v $G-l$, tak to řeší IP<br>		- když přidám hranu mezi $l$ a vrcholem v $G-l$, tak vzniká cyklus<br>			- protože $G$ je souvislý, tudíž mezi $l$ a libovolným jiným vrcholem už nějaká cesta existuje<br>	- $1\implies 5$<br>		- indukcí podle $n:=|V(T)|$<br>		- $n=1\quad 0=|E(T)|=|V(T)|-1=1-1$<br>		- $n\to n+1$<br>			- $T$ je strom na $n+1$ vrcholech<br>			- $T$ má list<br>			- $T':=T-l$ je strom na $n$ vrcholech<br>			- z IP: $|E(T')|=n-1$<br>			- vrácení $l$ zvýší počet hran i vrcholů o 1<br>			- takže $|E(T)|=|E(T')|+1=n=(n+1)-1 \quad\square$<br>	- $2\implies 1$<br>		- obměnou, tedy $\neg 1\implies\neg 2$<br>		- když graf není souvislý, tak není jednoznačně souvislý<br>		- když graf není acyklický, tak má kružnici, přičemž mezi vrcholy na kružnici neexistuje jednoznačná cesta<br>	- $3\implies 1$<br>		- obměnou, tedy $\neg 1\implies \neg 3$<br>		- když graf není souvislý, tak není minimální souvislý<br>		- když má kružnici, tak není minimální souvislý, protože můžu odstranit hranu na kružnici a souvislost se zachová<br>	- $4\implies 1$<br>		- obměnou, tedy $\neg 1\implies \neg 4$<br>		- když není acyklický, není maximální acyklický<br>		- když není souvislý, můžu přidat hranu (most) a nevytvořím kružnici, takže graf nemohl být maximální acyklický<br>	- $5\implies 1$<br>		- dokážeme, že souvislý graf splňující Eulerovu formuli má list<br>			- součet stupňů je roven dvojnásobku počtu hran<br>			- $\sum\text{deg}(v_i)=2|E|=2n-2$ (z Eulerovy formule)<br>			- průměrný stupeň $=\frac{2n-2}{n}<2$<br>			- graf je souvislý a netriviální, takže alespoň jeden vrchol musí mít stupeň 1 $\implies$ graf má list<br>		- důkaz indukcí podle $n:=|V(G)|$<br>			- $n=1$ platí triviálně (graf je strom, takže implikace platí)<br>			- $n\to n+1$<br>				- mějme graf $G$, který splňuje (5) a má list $v$ – viz výše<br>				- $G-v$ pořád splňuje (5)<br>				- podle IP je $G-v$ strom<br>				- $\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ý<br>- $\implies$<br>	- kostra je strom, strom je souvislý, každé dva vrcholy jsou spojené cestou<br>	- kostra je podgrafem $G$, takže tyto cesty existují i v $G$, tudíž i $G$ je souvislý<br>- $\impliedby$<br>	- $G$ je souvislý<br>	- když je acyklický, tak mám kostru<br>	- když není acyklický, tak odebírám hrany na cyklech tak dlouho, dokud není acyklický, čímž dostanu kostru
Definice: Rovinné nakreslení grafu a jeho stěny (neformálně); - (nakreslení grafu, aby se hrany nekřížily)<br>- vrcholy = body v rovině (navzájem různé)<br>- hrany = křivky, které se neprotínají a jejich společnými body jsou jejich společné vrcholy<br>	- definice křivky<br>		- $f:[0,1]→\mathbb R$<br>		- spojitá, prostá<br>		- = oblouk<br>- stěny nakreslení<br>	- části, na které nakreslení grafu rozděluje rovinu<br>	- stěnou je i vnější stěna (zbytek roviny)<br>	- hranice stěny – skládá se z hran<br>	- hranice stěny je nakreslení uzavřeného sledu
Definice: Rovinný graf, topologický graf; - graf je rovinný, pokud má alespoň jedno rovinné nakreslení<br>- topologický graf je uspořádaná dvojice (graf, nakreslení)
Příklad: $K_5$ a $K_{3,3}$ nejsou rovinné.; - $K_5$ – nakreslíme $K_4$ (jeden vrchol doprostřed, ostatní kolem něj) a hledáme, kam umístit pátý vrchol (zjistíme, že to nejde)<br>- podobně $K_{3,3}$<br>- lze dokázat pomocí vět o maximálních počtech hran
Věta: Hranice stěny je nakreslením uzavřeného sledu (bez důkazu).
Definice: Stereografická projekce; - máme rovinu, na ní je položená sféra (koule) tak, že se jí dotýká právě v jednom bodě (ten označím jako jižní pól)<br>- vedu polopřímku ze severního pólu skrz promítaný bod, průsečík s rovinou dává obraz daného bodu<br>- tak dostávám spojitou bijekci mezi sférou (bez severního pólu) a $\mathbb R^2$
Věta: Graf jde nakreslit do roviny, právě když jde nakreslit na sféru.; - důkaz: stereografická projekce je bijekce mezi sférou bez severního pólu a rovinou
Příklad: Vnější stěnu lze zvolit.; - vnější stěna se pozná podle toho, že obsahuje severní pól<br>- když sféru pootočím, tak vnější stěnu můžu zvolit
Kuratowského věta (bez důkazu): Graf je nerovinný, právě když obsahuje podgraf izomorfní s dělením $K_5$ nebo $K_{3,3}$.
Věta: Eulerova formule pro souvislé rovinné grafy (v+f=e+2); - věta: Nechť $G$ je souvislý graf nakreslený do roviny, $v:=|V(G)|, e:=|E(G)|, f:=$ počet stěn nakreslení, potom $v+f=e+2$.<br>- důkaz: indukcí podle $e$<br>	- $e=v-1$ (G je strom)<br>		- $f=1$<br>		- $v+1=v-1+2\quad\checkmark$<br>	- $e-1\to e$<br>		- mějme graf $G$ s $e$ hranami<br>		- zvolím si libovolnou hranu $x$ na kružnici<br>		- $G':=G-x$<br>		- $v'=v,\quad e'=e-1,\quad f'=f-1$<br>		- z IP: $v'+f'=e'+2$<br>		- po dosazení: $v+f-1=e-1+2$<br>		- k oběma stranám přičteme jedničku<br>		- $v+f=e+2\quad\square$
Věta: Maximální rovinný graf je triangulace.; - (pokud má aspoň 3 vrcholy)<br>- definice: maximální rovinný graf je rovinný graf, který přidáním libovolné hrany přestane být rovinný<br>- G musí být souvislý – kdyby nebyl, tak můžu spojit komponenty (pomocí vrcholů na hranici stěny, v níž leží komponenta) a graf nepřestane být rovinný, což je spor s maximální rovinností<br>- hranicí stěny je kružnice $\implies$ je to $\triangle$<br>	- kdyby nebyl, tak na kružnici jsou nesousední vrcholy, které můžu spojit a graf nepřestane být rovinný<br>- hranicí stěny není kružnice<br>	- nějaký vrchol na hranici se opakuje<br>	- tento vrchol můžu odstranit → hranice se rozpadne na komponenty → vrcholy v různých komponentách můžu spojit bez ztráty rovinnosti
Věta: Maximální počet hran rovinného grafu; - počet hran maximálního rovinného grafu<br>	- každá stěna přispěje třemi hranami<br>	- každá hrana patří ke dvěma stěnám<br>	- počítáme „strany hran“: $3f=2e$<br>	- $f={2\over 3}e$<br>	- $v+{2\over 3}e=e+2$<br>	- $e=3v-6$<br>- věta: V každém rovinném grafu s aspoň 3 vrcholy je $|E|\leq 3|V|-6$.<br>- důkaz<br>	- doplníme do $G$ hrany, až získáme maximální rovinný $G'$<br>	- $e'=3v-6$ (vrcholy nepřidáváme)<br>	- $e\leq e'=3v-6$<br>- důsledek<br>	- průměrný stupeň vrcholu v rovinném grafu je menší než 6<br>		- $\sum \text{deg}(\xi)=2e\leq 6v-12$<br>		- průměrný stupeň $\leq {6v-12\over v}\lt 6$
Věta: V rovinném grafu existuje vrchol stupně nejvýše 5.; - viz věta a důsledek výše<br>- kdyby měly všechny vrcholy stupeň alespoň šest, tak by průměrný stupeň nemohl být ostře menší než 6
Věta: Počet hran a vrchol nízkého stupně v rovinných grafech bez trojúhelníků; - maximální rovinné grafy bez trojúhelníků mají stěny čtvercové, pětiúhelníkové, nebo to může být strom ve tvaru hvězdy<br>- pro čtvercově stěny platí $4f=2e$, pro pětiúhelníkové $5f=2e$<br>- obecně $4f\leq 2e\to f\leq \frac 12 e$<br>- $v+\frac 12e\geq e+2$<br>- $e\leq 2v-4$<br>- průměrný stupeň $\leq {4v-8\over v} \lt$ 4<br>- existuje vrchol stupně max. 3
Definice: Obarvení grafu k barvami, barevnost; - obarvení grafu $G$ $k$ barvami (k-obarvení) je $c:V(G)\to[k]$ t. ž. kdykoli $\lbrace x,y\rbrace\in E(G)$, pak $c(x)\neq c(y)$<br>- barevnost $\chi(G)$ grafu $G:=\text{min }k:\exists$ k-obarvení grafu $G$<br>- pozorování: kdykoli $H\subseteq G$, pak $\chi(H)\leq \chi(G)$
Příklad: Barevnost úplných grafů, cest a kružnic; - úplné grafy … $\chi(K_n)=n$<br>- cesty … $\chi(P_n)=2$ pro $n\geq 1$<br>- sudé kružnice … $\chi(C_{2k})=2$<br>- liché kružnice … $\chi(C_{2k+1})=3$
Věta: Ekvivalentní tvrzení: graf má barevnost nejvýše 2, graf je bipartitní, graf neobsahuje lichou kružnici.; - věta: $\chi(G)\leq 2\iff G$ je bipartitní $\iff G$ neobsahuje lichou kružnici<br>- důkaz barevnosti bipartitních grafů<br>	- jednu partitu obarvím jednou barvou, druhou druhou barvou<br>	- barvy určují partity<br>- důkaz barevnost $\iff$ lichá kružnice<br>	- $\implies$ máme dokázáno obměnou (když má lichou kružnici, nejde obarvit dvěma barvami)<br>	- $\impliedby$ <br>		- kdyby G byl nesouvislý: obarvíme po komponentách<br>		- jinak: nechť T je kostra grafu G, pak existuje obarvení kostry (dvěma barvami)<br>			- sporem: kdyby existovala hrana, které tohle obarvení přiřklo stejné barvy koncových vrcholů, pak v grafu existuje lichá kružnice (spor)<br>			- mezi stejnobarevnými vrcholy bude cesta sudé délky, protože mají stejnou barvu a jsou ve stromě<br>			- tedy spojením stejnobarevných vrcholů vznikne lichá kružnice
Věta: Barevnost ≥ klikovost; - definice: klikovost grafu $\kappa(G)$ je maximální $k$ takové, že v grafu jako podgraf existuje úplný graf $K_k$<br>- $\chi(G)\geq\kappa(G)$<br>- zjevně platí
Příklad: Princip barvení indukcí: stromy jsou 2-obarvitelné, rovinné grafy 6-obarvitelné; - barvení stromu<br>	- strom rozdělíme do vrstev podle vzdálenosti od kořenu $v$<br>	- $c(x)=(d(v,x) \bmod 2)+1$<br>	- tvrzení: každý strom je 2-obarvitelný<br>	- důkaz: indukcí podle počtu vrcholů (základní případ pro 1 vrchol), postupně přidáváme (odebrané) listy, listu dáváme opačnou barvu než má vrchol, kam ho připojujeme, tedy $c(l)=3-c'(s)$<br>- barvení rovinného grafu – viz následující věta
Věta: Barevnost ≤ maximální stupeň + 1; - definice: graf G je k-degenerovaný $\equiv \exists \leq$ lineární uspořádání na $V(G)$ t. ž. $\forall v \in V(G): |\lbrace u<v \mid \lbrace u,v \rbrace \in E(G) \rbrace| \leq k$<br>	- vrcholy lze uspořádat tak, že z každého vrcholu doleva vede nejvýše $k$ hran<br>	- vrcholy skládám zprava doleva tak, jak je odtrhávám<br>	- stromy 1-deg., rovinné 5-deg., rovinné bez trojúhelníků 3-deg.<br>	- $\Delta := \text{max deg}(v)$ … graf je $\Delta$-degenerovaný<br>- graf je k-degenerovaný $\implies \chi\leq k+1$<br>	- barvím zleva, nejvýše $k$ barev může být zakázáno
Věta o 5 barvách; - věta: Pro každý rovinný graf $G$ platí $\chi(G)\leq 5$.<br>- první důkaz: indukcí podle $|V|$<br>	- pro $|V|\leq 5$ triviální<br>	- $n-1\to n$<br>		- nechť $v$ je vrchol s minimálním stupněm (nejvýše pět)<br>		- $G' := G-v$, podle IP existuje 5-obarvení $c'$ grafu $G'$<br>		- pokud na sousedech $v$ v obarvení $c'$ jsou použity max. 4 barvy, tak tu pátou můžeme použít na vrchol $v$<br>		- co když má každý soused jinou barvu<br>			- A je maximální souvislý podgraf indukovaný vrcholy áčkové a céčkové barvy, do kterých existuje cesta ze souseda $a$ přes vrcholy áčkové a céčkové barvy<br>			- pokud soused $c \notin A$<br>				- prohodíme barvy v A<br>				- tím pádem áčková barva se uvolní pro $v$<br>			- pokud soused $c \in A$<br>				- použiju stejný trik pro $b$ a $d$<br>				- soused $b$ je obalený kružnicí mezi $a$ a $c$, takže nehrozí, že by byl spojený s $d$<br>		- tzv. Kempeho řetězce<br>- druhý důkaz: indukcí podle $|V|$<br>	- máme vrchol stupně 5<br>	- musí existovat dva sousedi toho grafu, kteří nejsou spojeni hranou (jinak bychom dostali $K_5$)<br>	- můžu vytvořit rovinný $G'=G-v+\lbrace x,y\rbrace$ (nahradím vrchol hranou – bez ztráty rovinnosti)<br>	- můžu vytvořit rovinný $G''=G'.\lbrace x,y\rbrace$ (kontrakce hrany – zachovává rovinnost)<br>	- $G''$ obarvíme indukcí → dostaneme obarvení $c''$ → $c$ obarvení $G-v$ (v němž se barvy $x$ a $y$ rovnají) → existuje volná barva pro $v$
Věta o 4 barvách (bez důkazu): Pro každý rovinný graf $G$ platí $\chi(G)\leq 4$.
Definice: Pravděpodobnostní prostor diskrétní, konečný, klasický; - pravděpodobnostní prostor<br>	- $\Omega$ = množina elementárních jevů<br>	- $\mathcal F \subseteq 2^\Omega$ = množina jevů<br>	- $P:\mathcal F \to [0,1]$ = pravděpodobnost<br>	- náš pravděpodobnostní prostor je diskrétní, konečný a klasický<br>- diskrétní pravděpodobnostní prostor<br>	- $\Omega$ je konečná nebo spočetná (tedy spočetně nekonečná, existuje bijekce do $\mathbb N$)<br>	- $\mathcal F = 2^\Omega$<br>	- $P(J)=\sum_{x\in J}P(\lbrace x\rbrace)$<br>		- stačí určit pravděpodobnosti elementárních jevů<br>		- tedy jev nastává, když nastane kterýkoli z jeho elementárních jevů<br>	- $P(\emptyset)=0,\quad P(\Omega)=1$<br>	- klasický pravděpodobnostní prostor … $P(J)=\frac{|J|}{|\Omega|}$<br>		- všechny elementární jevy mají stejnou pravděpodobnost<br>	- konečný pravděpodobnostní prostor … $\Omega$ je konečná
Definice: Jev elementární, jev složený, pravděpodobnost jevu; - elementární jev = výsledek náhodného pokusu<br>- složený jev = množina elementárních jevů<br>- pravděpodobnost jevu … $P(J)=\sum_{x\in J}P(\lbrace x\rbrace)$
Příklad: Jev se také dá popsat logickou formulí.; - např. $P[\text{padlo sudé číslo}]$
Příklad: Bertrandův paradox s kartičkami; - tři kartičky, jedna je z obou stran červená, druhá modrá, třetí má jednu stranu červenou a druhou modrou<br>- vybereme náhodnou kartičku<br>- otočíme ji náhodnou stranou nahoru<br>- horní strana je červená<br>- jaká je pravděpodobnost toho, že dolní strana je také červená<br>- pravděpodobnostní prostor: ČČ, ČČ, MM, MM, ČM, MČ<br>- tři možnosti, z nich dvě chceme, takže $2 \over 3$
Definice: Podmíněná pravděpodobnost; - podmíněná pravděpodobnost jevu $A\subseteq\Omega$ za podmínky $B\subseteq\Omega$, přičemž $P(B)\neq 0$<br>- $P[A|B]:=\frac{P(A\cap B)}{P(B)}$<br>- počítání s pravděpodobností<br>	- $P(A\cup B)=P(A)+P(B)-P(A\cap B)$<br>	- $P(A\cup B)\leq P(A)+P(B)$<br>	- doplněk do množiny elementárních jevů … $\bar B$<br>	- $P[A|B] \cdot P(B)=P(A\cap B)$<br>	- $P[A|\bar B] \cdot P(\bar B)=P(A \cap \bar B)$<br>	- $P(A\cap B)+P(A\cap\bar B)=P(A)$<br>	- pozorování: $P[A|B]\cdot P(B)=P(A\cap B)=P(B\cap A)=P[B|A]\cdot P(A)$
Věta o úplné pravděpodobnosti (věta o rozboru případů); - věta: Pro $A\in \Omega,~B_1,\dots,B_k$ rozklad $\Omega$ t. ž. $\forall i:P(B_i)\neq 0$ platí $P(A)=\sum_iP[A|B_i]\cdot P(B_i)$.<br>- důsledek: řetězové pravidlo $P(A\cap B\cap C)=P[A|B\cap C]\cdot P(B\cap C)=P[A|B\cap C]\cdot P[B|C]\cdot P(C)$
Bayesova věta; - věta: Nechť $A$ je jev s $P(A)\neq 0$, $B_1,\dots,B_k$ rozklad $\Omega$ na jevy s $P(B_i)\neq 0$ pro všechna $i$. Potom $P[B_i|A]=\frac{P[A|B_i]\cdot P(B_i)}{\sum_jP[A|B_j]\cdot P(B_j)}$.
Definice: Jevy nezávislé a po dvou nezávislé; - nezávislost dvou jevů<br>	- jevy $A,B$ jsou nezávislé $\equiv$<br>		- $P(A\cap B)=P(A)\cdot P(B)$<br>		- $P[A|B]\cdot P(B)=P(A)\cdot P(B)$<br>	- $\iff P(B)=0 \lor P[A|B]=P(A)$<br>- jevy jsou po 2 nezávislé, pokud pro libovolnou dvojici z množiny jevů platí, že se pravděpodobnost průniku rovná součinu pravděpodobností<br>	- lze zobecnit na jevy po $k$ nezávislé<br>	- jevy jsou nezávislé $\equiv$ pro každé $k\geq 2$ jsou po $k$ nezávislé
Definice: Součin pravděpodobnostních prostorů, projekce; - součin pravděpodobnostních prostorů $(\Omega_1,2^{\Omega_1},P_1)$ a $(\Omega_2,2^{\Omega_2},P_2)$ je $(\Omega_1\times\Omega_2,2^{\Omega_1\times\Omega_2},P)$, kde $P(A):=\sum_{(a_1,a_2)\in A}P_1(a_1)\cdot P_2(a_2)$, přičemž $A\subseteq\Omega_1\times\Omega_2$<br>- jev lze promítnout na jednu z os – dostaneme hodnotu jednoho prvku z n-tice jevů<br>- jevy v různých prostorech jsou navzájem nezávislé
Definice: Náhodná veličina; - náhodná veličina je funkce z $\Omega$ do $\mathbb R$<br>- každému elementárnímu jevu přiřadí číselnou hodnotu
Příklad: Logické formule s náhodnými veličinami dávají jevy.; - např. $P[X\lt 3]$, kde $X$ je počet jedniček v $n$ hodech mincí
Definice: Střední hodnota; - střední hodnota náhodné veličiny $X$ je $\mathbb E[X]:=\sum_{\omega\in\Omega}X(\omega)\cdot P(\omega)$<br>- v klasickém pravděpodobnostním prostoru je to aritmetický průměr $\mathbb E[X]={\sum X(\omega)\over |\Omega|}$
Věta o linearitě střední hodnoty; - věta: Nechť $X,Y$ jsou náhodné věličiny a $\alpha\in\mathbb R$. Potom $\mathbb E[X+Y]=\mathbb E[X]+\mathbb E[Y]$ a $\mathbb E[\alpha X]=\alpha\mathbb E[X]$.<br>- důkaz<br>	- $\mathbb E[X+Y]=\sum_{\omega\in\Omega}(X+Y)(\omega)\cdot P(\omega)$ $=\sum (X(\omega)\cdot P(\omega)+Y(\omega)\cdot P(\omega))$ $=\sum X(\omega)\cdot P(\omega)+\sum Y(\omega)\cdot P(\omega)$<br>	- násobení konstantou se dokáže podobně (dosazením do sumy)
Definice: Indikátor náhodného jevu; - indikátor jevu $\equiv$ náhodná veličina, která nabývá hodnoty 0, nebo 1, podle toho, zda daný jev nastal
Příklad: Použití indikátorů k výpočtu střední hodnoty; - $n$ hodů mincí<br>- $X=$ celkový počet jedniček, chceme $\mathbb E[X]$<br>- $X_i=$ kolikrát je na i-té pozici jednička (1×/0×)<br>- $X=\sum_iX_i\to\mathbb E[X]=\sum_i\mathbb E[X_i]$<br>- $\mathbb E[X_i]={1\over 2}\to\mathbb E[X]={n\over 2}$
Věta: Erdősovo-Szekeresovo lemma o monotónních podposloupnostech; - lemma: Nechť $x_1,\dots,x_{n^2+1}$ je posloupnost nazvájem různých čísel. Potom existuje vybraná podposloupnost délky $n+1$, která je ostře monotónní (rostoucí nebo klesající).<br>- důkaz<br>	- definujme relaci $\leq$ na množině indexů $\lbrace 1,\dots,n^2+1\rbrace$<br>	- $i\leq j\equiv i\leq j\land x_i\leq x_j$<br>	- pozorování: $\leq$ je ČU<br>		- řetězec je rostoucí pp. (podposloupnost)<br>		- antiřetězec je klesající pp.<br>	- z věty O Dlouhém a Širokém plyne $\alpha\cdot\omega\geq n^2+1$<br>		- nemůže nastat $\alpha \leq n\land \omega\leq n$<br>		- $\implies \alpha\geq n+1\lor\omega\geq n+1$
Příklad: Existence de Bruijnovy posloupnosti (konstrukce pomocí orientovaných eulerovských tahů); - neprobráno, nebude zkoušeno
Příklad: Převod barvení mapy na barvení grafu pomocí duality; - každý stát (stěnu zobrazení) zvolíme jako vrchol grafu a hranami spojíme ty, které spolu sousedí<br>- duální graf rovinného grafu $G\equiv$ graf $G*$ jehož vrcholy odpovídají stěnám grafu G a hrany vedou mezi každou dvojicí stěn, které sdílejí společnou hranu
Definice: Markovova nerovnost; - věta<br>	- nechť X je nezáporná náhodná veličina a $k\gt 0$<br>	- přičemž $\mathbb E[X]\gt 0$<br>	- pak $P\left[X\geq k\cdot\mathbb E\left[X\right]\right]\leq\frac 1k$<br>- důkaz<br>	- $\mathbb E[X]=\sum_{a\geq0}a\cdot P[X=a]=\sum_{a\lt t}a\cdot P[X=a]+\sum_{a\geq t}a\cdot P[X=a]$<br>	- tvrdím, že první suma (pro $a\lt t$) je nezáporná<br>	- u druhé sumy využiju toho, že $a\geq t$<br>	- $\mathbb E[X]\geq t\cdot P[X\geq t]$<br>	- pro $t=k\cdot\mathbb E[X]$ dosadím<br>	- $P[X\geq k\cdot\mathbb E[X]]\leq\frac{\mathbb E[X]}{k\cdot\mathbb E[X]}$
Příklad: Velikost řezu v grafu: střední hodnota, existuje velký řez, pravděpodobnostní algoritmus; - střední hodnota – vážený průměr X (jako „váhy“ použijeme pravděpodobnosti)<br>	- $\mathbb E[X]:=\sum_{\omega\in\Omega}X(\omega)\cdot P(\omega)=\sum_{a\in\mathbb R}a\cdot P[X=a]$<br>	- linearita<br>- jevy $J_1,\dots,J_n$<br>	- $X:=$ počet jevů, které nastaly<br>	- $X_i$ … indikátor jevu $J_i$<br>	- $\mathbb E[X_i]=0\cdot P[X_i=0]+1\cdot P[X_i=1]$<br>	- střední hodnota indikátoru jevu je rovna pravděpodobnosti jevu<br>	- $\mathbb E[X]=\sum_i\mathbb E[X_i]$<br>- řez a algoritmus viz video
Příklad: Klasifikace platónských těles pomocí rovinných grafů; - platónské těleso = konvexní pravidelný mnohostěn, jehož všechny stěny jsou shodné pravidelné mnohoúhelníky a zároveň z každého vrcholu vychází stejný počet hran<br>- příklad<br>	- vezmu osmistěn, opíšu mu sféru<br>	- z těžiště budu promítat vrcholy na sféru<br>	- vznikne rovinný graf<br>- hledám rovinný graf<br>	- každá stěna má právě $k$ hran, $3\leq k$<br>	- graf je d-regulární, $d\leq 5$<br>- lze sestrojit duální graf – prohodí se nám $k$ a $d$<br>	- $3\leq k\leq 5$<br>	- $3\leq d\leq 5$<br>- Eulerova formule: $v+f=e+2$<br>	- $kf=2e, \quad dv=2e$<br>	- vyjádříme $f,v$ dosadíme do E. f.<br>	- ${2e\over d}+{2e \over k}=e+2$<br>	- vydělím 2e<br>	- $\frac 1d+\frac 1k=\frac 12+\frac 1e$<br>	- tedy pravá strana rovnice bude $\in(\frac 12,1]$<br>		- z toho plyne, že $\text{min}(d,k)=3$<br>- tabulka možných parametrů – $d,k$ vymýšlím podle podmínek, zbytek dopočítávám ze vzorců; jiná platónská tělesa nemohou existovat