Zkouška

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

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

• symetrická diference $A\bigtriangleup B=(A\setminus B)\cup(B\setminus A)$
• potence $2^A:=\lbrace B \mid B\subseteq A\rbrace$

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

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

• prázdná $\emptyset$
• univerzální $X\times Y$
• diagonální $\Delta_X := \lbrace (x,x)\mid x\in X\rbrace$, např. rovnost $x=y$

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

• 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

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

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

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

• 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

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

• 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

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

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

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

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

$m^{\underline n}=\underbrace{m\cdot (m-1)\cdot (m-2)\cdot\ldots\cdot(m-n+1)}_n$

• 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: $|2^N|=2^{|N|}$
• důkaz: počet podmnožin = počet charakteristických funkcí = $2^{|N|}$

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

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

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

$X\choose k$ … množina všech k-prvkových podmnožin množiny X

• 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

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

• 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: (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í

• Š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: 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}$

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

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

• ú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\}$

• 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

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

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

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

• 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

• 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

• 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

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

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

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

$\forall u,v,w\in V(G): d(u,v)\leq d(u,w)+d(w,v)$

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

• 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: 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 ↯

• 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