# 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 ## Rovinné kreslení grafů - Definice: Rovinné nakreslení grafu a jeho stěny (neformálně) - (nakreslení grafu, aby se hrany nekřížily) - vrcholy = body v rovině (navzájem různé) - hrany = křivky, které se neprotínají a jejich společnými body jsou jejich společné vrcholy - definice křivky - $f:[0,1]→\mathbb R$ - spojitá, prostá - = oblouk - stěny nakreslení - části, na které nakreslení grafu rozděluje rovinu - stěnou je i vnější stěna (zbytek roviny) - hranice stěny – skládá se z hran - hranice stěny je nakreslení uzavřeného sledu - Definice: Rovinný graf, topologický graf - graf je rovinný, pokud má alespoň jedno rovinné nakreslení - 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) - podobně $K_{3,3}$ - 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) - vedu polopřímku ze severního pólu skrz promítaný bod, průsečík s rovinou dává obraz daného bodu - 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 - 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$. - důkaz: indukcí podle $e$ - $e=v-1$ (G je strom) - $f=1$ - $v+1=v-1+2\quad\checkmark$ - $e-1\to e$ - mějme graf $G$ s $e$ hranami - zvolím si libovolnou hranu $x$ na kružnici - $G':=G-x$ - $v'=v,\quad e'=e-1,\quad f'=f-1$ - z IP: $v'+f'=e'+2$ - po dosazení: $v+f-1=e-1+2$ - k oběma stranám přičteme jedničku - $v+f=e+2\quad\square$ - Věta: Maximální rovinný graf je triangulace. - (pokud má aspoň 3 vrcholy) - definice: maximální rovinný graf je rovinný graf, který přidáním libovolné hrany přestane být rovinný - 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í - hranicí stěny je kružnice $\implies$ je to $\triangle$ - kdyby nebyl, tak na kružnici jsou nesousední vrcholy, které můžu spojit a graf nepřestane být rovinný - hranicí stěny není kružnice - nějaký vrchol na hranici se opakuje - 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 - každá stěna přispěje třemi hranami - každá hrana patří ke dvěma stěnám - počítáme „strany hran“: $3f=2e$ - $f={2\over 3}e$ - $v+{2\over 3}e=e+2$ - $e=3v-6$ - věta: V každém rovinném grafu s aspoň 3 vrcholy je $|E|\leq 3|V|-6$. - důkaz - doplníme do $G$ hrany, až získáme maximální rovinný $G'$ - $e'=3v-6$ (vrcholy nepřidáváme) - $e\leq e'=3v-6$ - důsledek - průměrný stupeň vrcholu v rovinném grafu je menší než 6 - $\sum \text{deg}(\xi)=2e\leq 6v-12$ - 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 - 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 - pro čtvercově stěny platí $4f=2e$, pro pětiúhelníkové $5f=2e$ - obecně $4f\leq 2e\to f\leq \frac 12 e$ - $v+\frac 12e\geq e+2$ - $e\leq 2v-4$ - průměrný stupeň $\leq {4v-8\over v} \lt$ 4 - existuje vrchol stupně max. 3 ## Barvení grafů - 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)$ - barevnost $\chi(G)$ grafu $G:=\text{min }k:\exists$ k-obarvení grafu $G$ - 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$ - cesty … $\chi(P_n)=2$ pro $n\geq 1$ - sudé kružnice … $\chi(C_{2k})=2$ - 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 - důkaz barevnosti bipartitních grafů - jednu partitu obarvím jednou barvou, druhou druhou barvou - barvy určují partity - důkaz barevnost $\iff$ lichá kružnice - $\implies$ máme dokázáno obměnou (když má lichou kružnici, nejde obarvit dvěma barvami) - $\impliedby$ - kdyby G byl nesouvislý: obarvíme po komponentách - jinak: nechť T je kostra grafu G, pak existuje obarvení kostry (dvěma barvami) - sporem: kdyby existovala hrana, které tohle obarvení přiřklo stejné barvy koncových vrcholů, pak v grafu existuje lichá kružnice (spor) - mezi stejnobarevnými vrcholy bude cesta sudé délky, protože mají stejnou barvu a jsou ve stromě - 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$ - $\chi(G)\geq\kappa(G)$ - zjevně platí - Příklad: Princip barvení indukcí: stromy jsou 2-obarvitelné, rovinné grafy 6-obarvitelné - barvení stromu - strom rozdělíme do vrstev podle vzdálenosti od kořenu $v$ - $c(x)=(d(v,x) \bmod 2)+1$ - tvrzení: každý strom je 2-obarvitelný - 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)$ - 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