slama.dev

Diskrétní Matematika

12. 1. 2020; lecture notes

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Mareše z roku 2019/2020 . Pokud by byla někde chyba/nejasnost, nebo byste rádi někam přidali obrázek/text, tak stránku můžete upravit pull requestem (případně mi dejte vědět, např. na mail).

Relace

Definice: relace mezi množinami X,YRX×YX, Y \equiv R \subseteq X \times Y (podmnožina kartézského součinu)

  • prázdná: \emptyset (nic s ničím)
  • univerzální: X×YX \times Y (vše se vším)
  • diagonální ΔX\Delta_X: {(x,x)xX}\left\{\left(x, x\right) \mid x \in X\right\}
    • matice relace má 1 na diagonále
  • inverzní R1R^{-1}: {(y,x)(x,y)R}\left\{\left(y, x\right) \mid \left(x, y\right) \in R\right\}
    • pozor: nemusí to být funkce!
  • složená: x(RS)z yY:xRyySzx \left(R \circ S\right) z \equiv\ \exists y \in Y: xRy \land ySz
    • tzn. tj. musí existovat cesta (když si to představíme jako grafy)

Funkce

Definice: relace ff mezi X,YX, Y je funkce (zobrazení)  xX ! yY:xfy\ \equiv \forall x \in X \ \exists!\ y \in Y: x f y

  • speciální druh relace, ve kterém se z XX zobrazuje „jen jednou“
  • značíme f:XYf: X \mapsto Y nebo f(x)=yf\left(x\right) = y

  • prostá: x,xX,xx:f(x)f(x)\forall x, x' \in X, x \neq x': f\left(x\right) \neq f\left(x'\right)
  • na: yY xX:f(x)=y \forall y \in Y\ \exists x \in X: f\left(x\right) = y
    • na každé yy se něco zobrazí (klidně vícekrát!)
  • bijekce: yY ! xX:f(x)=y\forall y \in Y\ \exists!\ x \in X: f\left(x\right) = y
  • pozn.: podle definice jdou všechny prvky z XX někam do YY!

Vlastnosti relace

  • reflexivní: xX:xRx\equiv \forall x \in X: xRx
    • diagonála
  • symetrická: x,yX:xRy    yRx\equiv \forall x, y \in X: xRy \iff yRx
    • pozn.: R1=RR^{-1} = R
  • antisymetrická: x,yX,xy:xRy    ¬yRx\forall x, y \in X, x \neq y: xRy \implies \neg yRx
    • alternativně: x,yX:xRyyRx    x=y\forall x, y \in X: xRy \land yRx \implies x = y (je z toho lépe vidět diagonála)
    • např. menší než… musí to být pouze jedním směrem
  • tranzitivní: x,y,zX:xRyyRz    xRz\forall x,y,z \in X: xRy \land yRz \implies xRz
    • hezky vidět na grafech, špatně na maticích

Ekvivalence

Relace RR na XX je ekvivalence  R\ \equiv R je tranzitivní, reflexivní a symetrická.

  • ekvivalenční třída R[x]R\left[x\right] prvku x:={yXxRy}x := \left\{y \in X \mid xRy \right\} (jsou spolu mezi sebou všechny v relaci)

Věta: Nechť RR je ekvivalence na XX. Potom:

  1. xX:R[x]\forall x \in X: R[x] \neq \emptyset
    • vyplývá z reflexivity… xR[x]x \in R\left[x\right]
  2. x,yX:\forall x, y \in X: buď R[x]=R[y]R\left[x\right] = R\left[y\right] nebo R[x]R[y]=R\left[x\right] \cap R\left[y\right] = \emptyset
    • pro R[x]R[y]R\left[x\right] \subseteq R\left[y\right]: uvažme zR[x]z \in R\left[x\right], tím pádem zRxzRx (symetrie) a zRyzRy (tranzitivita), proto i xRyxRy a tedy zR[y]z \in R\left[y\right] (pak stačí obrátit…)
    • xRyxRy neplatí – sporem dokážeme, že R[x]R[y]=R\left[x\right] \cap R\left[y\right] = \emptyset… nechť existuje zR[x]R[y]z \in R\left[x\right] \cap R\left[y\right]; potom xRzxRz a zRyzRy (tranzitivita), a tedy xRyxRy, což je ↯
  3. ekvivalenční třídy určují RR jednoznačně
    • zřejmé… xRyxRy právě když {x,y}R[x]\left\{x, y\right\}\subseteq R\left[x\right]

Uspořádání

Relace RR na XX je uspořádání   R\ \equiv\ R je reflexivní, antisymetrická a tranzitivní.

  • lineární \le: x,yX:xyyx\forall x, y \in X: x \le y \lor y \le x (všechny x,yx, y jsou porovnatelné)
  • částečné = ne lineární
  • ostré: pokud \le je uspořádání, pak x<yxyxyx < y \equiv x \le y \land x \neq y je ostré uspořádání
  •  := 1\ge\ :=\ \le^{-1} je také uspořádání (to samé platí pro ostré)
Hasseův diagram

Uvažme uspořadání ({1,2,3},)\left(\left\{1, 2, 3\right\}, \subseteq\right). Jeho Hasseův diagram bude vypadat následně:

  • spojujeme bezprostřední předky, tj.: neexistuje tXt \in X mezi x,yx, y takové, že x<t<yx < t < y
  • xx je minimální (maximální) prvek   y:y<x\ \equiv \nexists\ y: y < x
    • tzn. neexistuje menší
  • xx je nejmenší (největší) prvek  y:xy\ \equiv \forall y: x \le y
    • tzn. je menší než všechny ostatní
    • silnější kritérium než minimální, jelikož musí se všemi být porovnatelný
    • nejmenší je rovněž minimální
Lexikografické uspořádání

Nechť XX je abeceda a \le uspořadání na XX. Pak:

(X2,LEX)\left(X^2, \le_{LEX}\right), (a,b)LEX(a,b)(a<a)(a=abb)\left(a, b\right) \le_{LEX} \left(a', b'\right) \equiv \left(a < a'\right) \lor \left(a = a' \land b \le b'\right)

  • nejprve se rozhoduje podle prvního, pak podle druhého
  • lze generalizovat pro více (kartézský součin) množin

Dlouhý a široký

Definice: pro (X,)\left(X, \le\right) ČUM:

  • AXA \subseteq X je řetězec a,bA\forall a, b \in A jsou porovnatelné
    • ω(X,):=\omega\left(X, \le\right) := délka nejdelšího řetězce
  • AXA \subseteq X je antiřetězec \equiv žádné 2 prvky nejsou porovnatelné (nezávislá množina)
    • α(X,):=\alpha\left(X, \le\right) := délka nejdelšího antiřetězce

Věta (o dlouhém a širokém): pro (X,)\left(X, \le\right) konečnou ČUM: αωX\alpha \omega \ge \left|X\right|

Důkaz:

  • M1:={aXa je minimaˊlnıˊ v }M_1 := \left\{a \in X \mid a\ \text{je minimální v}\ \le\right\}
  • X1:=XM1X_1 := X \setminus M_1
  • pokračujeme a vyjde nám, že i:Miα\forall i: \left|M_i\right| \le \alpha (všechny totiž musí být nezávislé); rovněž akMk,ak1Mk1\exists a_k \in M_k, a_{k - 1} \in M_{k - 1} \ldots řetězec     kω\implies k \le \omega
    • kombinací dojdeme k nerovnosti X=i=1kMiαω\left|X\right| = \sum_{i = 1}^{k} \left|M_i\right| \le \alpha \omega

Věta (Erdős-Szekeres): nechť x1,,xn2+1x_1, \ldots, x_{n^2 + 1} jsou navzájem různé. Pak existuje buď rostoucí nebo neklesající posloupnost délky alespoň n+1n + 1.

Důkaz: Na {1,,n+1}\left\{1, \ldots, n + 1\right\} definujme uspořádání i<j    i<jxi<xji < j \iff i < j \land x_i < x_j. Rostoucí odpovídají řetězcům, klesající antiřetězcům.

Segway do kombinatorického počítání

Věta: je-li AA aa-prvkové a BB bb-prvkové, pak počet f:AB=baf: A \mapsto B = b^a

Důkaz: každý prvek z AA můžeme (podle definice dokonce musíme) poslat do libovolného prvku z BB.


Věta: 2X=2X\left|2^X\right| = 2^{\left|X\right|}

Důkaz: pro YXY \subseteq X zavedeme charakteristickou funkci CY:X{0,1}C_Y: X \mapsto \left\{0, 1\right\}, kde

CY(x){1xY0jindyC_Y\left(x\right) \begin{cases} 1 & x \in Y \\ 0 & \text{jindy}\end{cases}

Každá CYC_Y jasně určuje unikátní podmnožinu, tím pádem vlastně počítáme funkce z nn-prvkové do 22-prvkové množiny, kterých je 2n2^n (viz předešlá věta).


Věta: je-li AA aa-prvkové a BB bb-prvkové, pak počet f:ABf: A \mapsto B prostých je i=0a1(bi)=ba\prod_{i = 0}^{a - 1}\left(b - i\right) = b ^ {\underline{a}} Důkaz: 1. prvek z aabb možností, druhý b1b - 1, …


Počítání dvojic: f:{1,2}XX2f: \left\{1, 2\right\} \mapsto X \equiv X^2

  • prvky jsou dvojice (f(1),f(2))\left(f\left(1\right), f\left(2\right)\right)
  • {1,,k}\left\{1, \ldots, k\right\} – uspořádání kk-tice
  • NX\mathbb{N} \mapsto X – nekonečné posloupnosti prvků z XX

Počet k-tic různých prvků z XXf:{1,,k}Xf: \left\{1, \ldots, k\right\} \mapsto X je n(n1)(n2)(nk1)n \cdot \left(n - 1\right) \cdot \left(n - 2\right) \cdot \ldots \cdot \left(n - k - 1\right)

  • n=Xn = \left|X\right| (stejné jako počítání prostých funkcí)

Počet bijekcí mezi XX a XX (permutací) =n(n1)1:=n!= n \cdot \left(n - 1\right) \cdot \ldots \cdot 1 := n! (faktoriál)

Kombinatorika

  • pár definic na rozjezd:

(Xk):={AXA=k}\binom{X}{k} := \left\{A \subseteq X \mid \left|A\right| = k\right\}

(nk):=n(n1)(n2)(nk+1)k(k1)(k2)21=n!k!(nk)!\binom{n}{k} := \frac{n \cdot \left(n - 1\right) \cdot \left(n - 2\right) \cdot \ldots \cdot \left(n - k + 1\right)}{k \cdot \left(k - 1\right) \cdot \left(k - 2\right) \cdot \ldots \cdot 2 \cdot 1} = \frac{n!}{k! \cdot \left(n - k\right)!}

Věta: (Xk)=(Xk)\left|\binom{X}{k}\right| = \binom{\left|X\right|}{k}

Důkaz (počítání dvěma způsoby):

  • # uspořádaných kk-tic různých prvků z XX je stejný jako:
    • # prostých funkcí z {1,,k}X\left\{1, \ldots, k\right\} \mapsto X, kterých je n(n1)(nk+1)n \cdot \left(n - 1\right) \cdot \ldots \cdot \left(n - k + 1\right)
    • # kk-prvkových množin k! \cdot k! (zpermutováním)… (Xk)k!\left|\binom{X}{k}\right| \cdot k!

Vlastnosti kombinačních čísel:

  • počet prázdných podmnožin =1== 1 = počet „plných“ podmnožin: (n0)=1=(nn)\binom{n}{0} = 1 = \binom{n}{n}
  • počet 1-prvkových podmnožin=n= = n = počet podmnožin, kde 1 prvek chybí: (n1)=n=(nn1)\binom{n}{1} = n = \binom{n}{n - 1}
  • generalizace předchozích dvou vzorečků… počítání doplňků: (nk)=(nnk)\binom{n}{k} = \binom{n}{n - k}
  • počet podmnožin dané množiny: k=0n(nk)=2n\sum_{k=0}^{n} \binom{n}{k} = 2^n
    • vlastně nn-bitové číslo – patří/nepatří

(nk)=(n1k)+(n1k1)\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}

  • kk-prvkové množiny obsahující/neobsahující nn… když obsahují, tak máme zbylých kk míst; když ne, tak k1k - 1 (samotné nn jedno zabírá)

Binomická věta

nN,a,bR:(a+b)n=k=0n(nk)ankbk\forall n \in \mathbb{N}, \forall a, b \in \mathbb{R}: \left(a + b\right)^n = \sum_{k = 0}^{n} \binom{n}{k} a^{n - k}b^k

Důkaz:

  • pro 00 funguje
  • jedná se o součty součinů, které si ze závorek vybírají aa nebo bb
    • ankbka^{n - k}b^k – musí jich být nn
    • (nk)\binom{n}{k} – kolika způsoby si lze z nn závorek vybrat k znaků

Zajímavosti:

  • (1+1)n=2n=k=0n(nk)\left(1 + 1\right)^n = 2^n = \sum_{k = 0}^{n}\binom{n}{k} – součet řady Pascalova trojúhelníka
  • (11)n=0=k=0n(nk)(1)k\left(1 - 1\right)^n = 0 = \sum_{k = 0}^{n}\binom{n}{k} \left(-1\right)^k – počet podmnožin sudé velikosti je roven počtu podmnožin velikosti liché

Odhady pro faktoriál

  • hloupý: 2n1n!nn2^{n - 1} \le n! \le n^n
  • rozumný: nn/2n!(n+12)nn^{n / 2} \le n! \le \left(\frac{n + 1}{2}\right)^n
  • wtf: e(ne)nn!en(ne)ne \cdot \left(\frac{n}{e}\right)^n \le n! \le en \cdot \left(\frac{n}{e}\right)^n

Lemma – a/g nerovnost: xyx+y2x,y0 \sqrt{xy} \le \frac{x + y}{2} \qquad \forall x, y \ge 0

(ab)20a22ab+b20a2+b22aba2+b22abx+y2xy \begin{aligned} \left(a - b\right)^2 &\ge 0 \\ a^2 - 2ab + b^2 &\ge 0 \\ a^2 + b^2 &\ge 2ab \\ \frac{a^2 + b^2}{2} &\ge ab \\ \frac{x + y}{2} &\ge \sqrt{xy} \end{aligned}

Důkaz rozumného:

  • n!=(n!)2=12n12n=1n2(n1)n1n! = \sqrt{\left(n!\right)^2} = \sqrt{1 \cdot 2 \cdot \ldots \cdot n \cdot 1 \cdot 2 \cdot \ldots \cdot n} = \sqrt{1 \cdot n} \cdot \sqrt{2 \cdot \left(n - 1\right)} \cdot \ldots \cdot \sqrt{n \cdot 1}
    • i(ni+1)AGi+ni+12=(n+12)n\sqrt{i \left(n - i + 1 \right)} \le^{\mathrm{AG}} \frac{i + n - i + 1}{2} = \left(\frac{n + 1}{2}\right)^n (je jich nn)
    • i(ni+1)nn\sqrt{i \left(n - i + 1\right)} \ge \sqrt{n}^n… vevnitř je vždy alespoň nn

Důkaz wtf (indukce):

  • n=1n = 1e11e1e \cdot 1 \cdot \frac{1}{e} \le 1
  • n1nn - 1 \rightarrow n: n!=n(n1)!IPen(n1)(n1e)n1=en(ne)n(en)n(n1)(n1e)n1=en(ne)n(n1n)ne1\begin{aligned} n! = n \left(n - 1\right)! &\le^\mathrm{IP} en \left(n - 1\right) \left(\frac{n - 1}{e}\right)^{n - 1} \\ &= en \left(\frac{n}{e}\right)^n \left(\frac{e}{n}\right)^n \left(n - 1\right) \left(\frac{n - 1}{e}\right)^{n - 1} \\ &= en \left(\frac{n}{e}\right)^n \underbrace{\left(\frac{n - 1}{n}\right)^n e}_{\le 1} \end{aligned}

Důkaz, toho proč ten výraz 1\le 1:

(11n)ne(e1n)ne=e1e=11+xex \begin{aligned} \left(1 - \frac{1}{n}\right)^n e &\le \left(e^{-\frac{1}{n}}\right)^n e = e^{-1} e = 1 \qquad 1 + x \le e^x \end{aligned}

  • pozn.: ab    a=bca \le b \implies a = b c pro c1c \le 1, proto to vlastně děláme

Princip inkluze/exkluze

Nechť A1,,AnA_1, \ldots, A_n jsou konečné množiny. Potom: i=0nAi=k=1n(1)k+1I([n]k)iIAi\left|\bigcup_{i = 0}^{n} A_i\right| = \sum_{k = 1}^{n} \left(-1\right)^{k + 1} \sum_{I \in \binom{\left[n\right]}{k}} \left|\bigcap_{i \in I} A_i\right|

Také lze zapsat jako i=0nAi=I[n](1)I+1iIAi\left|\bigcup_{i = 0}^{n} A_i\right| = \sum_{\emptyset \neq I \subseteq \left[n\right]} \left(-1\right)^{\left|I\right| + 1} \left|\bigcap_{i \in I} A_i\right|

Důkaz (počítací) – kolikrát se prvek xx nachází nalevo a napravo:

  • nalevo: 1 (ve sjednocení je jednou právě)
  • napravo:
    • předpokládejme, že se vyskytne v jj množinách – vyskytuje se tedy v každé kk-tici… (kjk \le j)
    • existuje (jk)\binom{j}{k} kk-prvkových podmnožin jj-prvkové množiny (a ve vzorci se znaménka střídají), lze počet výskytů vyjádřit následovně: j(j2)+(j3)+(1)j1(jj)=1j - \binom{j}{2} + \binom{j}{3} - \ldots + \left(-1\right)^{j - 1}\binom{j}{j} = 1

Grafy

Definice: graf je uspořádaná dvojice množin (V,E)\left(V, E\right), kde VV je konečná, neprázdná množina vrcholů a E(V2)E \subseteq \binom{V}{2} je množina hran.

  • {u,v}E\left\{u, v\right\} \in E… mezi u,vu, v vede hrana (jsou sousední)
  • vev \in e pro eEe \in E… vrchol leží v/na hraně

Odrudy

  • úplný Kn([n],(V2))K_n \equiv \left(\left[n\right], \binom{V}{2}\right)
    • opak je diskrétní
  • úplný bipartitní Km,nK_{m, n}:
    • V(Km,n)={a1,,am,b1,,bn}V\left(K_{m, n}\right) = \left\{a_1, \ldots, a_m, b_1, \ldots, b_n\right\} (rozdělíme na 2 části)
    • E(Km,n)={{ai,bj}i[m],j[n]}E\left(K_{m, n}\right) = \left\{\left\{a_i, b_j\right\} \mid i \in \left[m\right], j \in \left[n\right]\right\}
    • bipartitní – E E \subseteq\ úplného bipartitního
  • cesta Pn([n],{{i,i+1}0i<n})P_n \equiv \left(\left[n\right], \left\{\left\{i, i + 1\right\} \mid 0 \le i < n\right\}\right)
  • cyklus Cn([n],{{i,(i+1) mod n}0in})C_n \equiv \left(\left[n\right], \left\{\left\{i, \left(i + 1\right)\ \mathrm{mod}\ n\right\} \mid 0 \le i \le n\right\}\right)

Izomorfismus

Definice: grafy GG a HH jsou izomorfní (GH)f:V(G)V(H)\left(G \cong H\right) \equiv f: V\left(G\right) \mapsto V\left(H\right) bijekce t. ž. u,vV(G)\forall u, v \in V\left(G\right) platí: {u,v}E(G)    {f(u),f(v)}E(H)\left\{u, v\right\} \in E\left(G\right) \iff \left\{f\left(u\right), f\left(v\right)\right\} \in E\left(H\right)

  • vlastně to je takové přejmenování vrcholů

Grafové odhady

Nechť V={v1,,vn}V = \left\{v_1, \ldots, v_n\right\}.

  • počet všech grafů na VV je 2(n2)2^{\binom{n}{2}} (všechny možné dvojice; buďto tam jsou nebo nejsou)
  • počet neizomorfních grafů: počet všech grafů / počet tříd izomorfismu (ekvivalence)
    • izomorfismů je nejvýše n!n! (uvažujeme všechna přejmenování)
    • celkem tedy 2(n2)/n!\ge 2^\binom{n}{2} / n!
    • není to tak špatný odhad:

log2(n2)n!(n2)nlogn=n(n1)2nlogn=n22(11n2log2nn) \begin{aligned} \log \frac{2^\binom{n}{2}}{n!} &\ge \binom{n}{2} - n \log n \\ &= \frac{n \left(n - 1\right)}{2} - n \log n \\ & = \frac{n^2}{2} \left(1 - \frac{1}{n} - \frac{2 \cdot \log{2}{n}}{n}\right) \end{aligned}

Vlastnosti grafu

  • stupeň vrcholu vv grafu GG je degG(v)=#wV(G):{v,w}E(G)\mathrm{deg}_G\left(v\right) = \# w \in V(G): \left\{v, w\right\} \in E\left(G\right)
    • tzn. kolik hran vede do vrcholu
    • kk-regulární graf: stupeň všech vrcholů je kk
  • skóre grafu je uspořádaná nn-tice stupňů všech vrcholů
    • typicky d1d2dnd_1 \le d_2 \le \ldots \le d_n
    • 0di<n10 \le d_i < n - 1

Lemma: vV(G)deg(v)=2E(G)\sum_{v \in V\left(G\right)} \mathrm{deg}\left(v\right) = 2 \cdot \left|E\left(G\right)\right|

Důkaz: nechť KK je {(v,e)eE(G)ve}\left\{\left(v, e\right) \mid e \in E\left(G\right) \land v \in e\right\}; pak K=2E(G)=vdeg(v)\left|K\right| = 2 \cdot \left|E\left(G\right)\right| = \sum_{v} \mathrm{deg}(v)

  • první rovnost platí, jelikož každá hrana přispěje 2x
  • druhá rovnost platí, jelikož každý vrchol přispěje všemi hranami, které do něj jdou (tj. svým stupňem)
  • vyplývá z toho princip sudosti: počet vrcholů lichého stupně je sudý (jinak by se to nesečetlo na sudé číslo

Věta (testování skóre): Nechť d1d2dnd_1 \le d_2 \le \ldots \le d_n posloupnost přirozených čísel. Pak d1,d2,dn1d_1', d_2', \ldots d_{n - 1}' vznikne smazáním posledního prvku a odečtením 11 od dnd_n předchozích. Pak d1d2dnd_1 \le d_2 \le \ldots d_n je skórem grafu, když d1,d2,dn1d_1', d_2', \ldots d_{n - 1}' je skórem grafu.

Důkaz:

  • \Rightarrow… víme, že d1,d2,dn1d_1', d_2', \ldots d_{n - 1}' je skórem grafu, stačí tedy přilepit vrchol a propojit ho patřičnými hranamy k existujícímu grafu:
    • V(G)={v1,,vn1,vn}V\left(G\right) = \left\{v_1', \ldots, v_{n - 1}', v_n\right\}
    • E(G)=E(G){{vi,vn}ndnin1}E\left(G\right) = E\left(G'\right) \cup \left\{\left\{v'i, v_n\right\} \mid n - d_n \le i \le n - 1\right\}
    • pozor! opačně nefunguje, jelikož nemáme jistotu, že odebíráme od těch zprava
  • \Leftarrow
    • Nechť G:={G na {v1,,vn},i:degG(vi)=di}\mathcal{G} := \left\{G\ \text{na}\ \left\{v_1, \ldots, v_n\right\}, \mid \forall i: \mathrm{deg}_G\left(v_i\right) = d_i\right\}
      • = všechny možné grafy se správným tím skórem
    • lemma:  GG:j,ndnj<n:{vj,vn}E(G)\exists\ G \in \mathcal{G}: \forall j, n - d_n \le j < n: \left\{v_j, v_n\right\} \in E\left(G\right)
      • nechť j(G):=max{j{vj,vn}∉E(G)}j\left(G\right) := \mathrm{max}\left\{j \mid \left\{v_j, v_n\right\} \not\in E\left(G\right)\right\} (první díra zprava)
  • nechť GGG \in \mathcal{G} má minimální j(G)j\left(G\right)… pak j<ndnj < n - d_n
    • důkaz sporem: kdyby jndnj \ge n - d_n, pak i\exists i a k:{vj,vk}E(G){vi,vk}∉E(G)\exists k: \left\{v_j, v_k\right\} \in E\left(G\right) \land \left\{v_i, v_k\right\} \not\in E\left(G\right)
      • pro di<djd_i < d_j – z vjv_j jich vede více než s did_i (takže do nějaké do které djd_j vede did_i nevede)
      • di=djd_i = d_j je taky ok… jedna z viv_i vede do vnv_n
  • škrtnutím vyrobíme graf, který má menší jj… ↯

Graf HH je podgrafem grafu G(HG)V(H)V(G)E(H)E(G)G \left(H \subseteq G\right) \equiv V\left(H\right) \subseteq V\left(G\right) \land E\left(H\right) \subseteq E\left(G\right).

  • vznik tak, že z grafu odebíráme hrany/vrcholy

Graf HH je indukovaným podgrafem grafu G(HG)V(H)V(G)E(H)=E(G)(V(H)2)G \left(H \subseteq G\right) \equiv V\left(H\right) \subseteq V\left(G\right) \land E\left(H\right) = E\left(G\right) \cup \binom{V\left(H\right)}{2}.

  • vznik tak, že z grafu odebíráme pouze vrcholy (a s nimi spojené hrany)

Cesta v grafu délky kk je (2 pohledy):

  1. HGH \subseteq G t. ž. HPkH \cong P_k
  2. v0,e1,v1,,ek,vkv_0, e_1, v_1, \ldots, e_k, v_k t. ž.:
    • i:viV(G)\forall i: v_i \in V\left(G\right) + všechny viv_i jsou různé vrcholy
    • j:ejE(G)ej={vji,vj}\forall j: e_j \in E\left(G\right) \land e_j = \left\{v_{j - i}, v_j\right\} - obdobně lze definovat kružnici, jen ve=vkv_e = v_k

Sled (procházka/walk) v grafu GG je cesta, ve které se mohou vrcholy i hrany opakovat.

  • lemma: pokud existuje sled z xx do yy, pak existuje i cesta:
    • zvolíme nejkratší ze všech sledů… to je cesta; kdyby ne, pak \exists vrchol, který se tam vyskytuje 2x (tím pádem jde sled zkrátit)

Graf GG je souvislý (drží pohromadě)  u,vV(G) \ \equiv \forall u, v \in V\left(G\right) \exists\ cesta v GG z uu do vv

  • relace dosažitelnosti: \sim na V(G)V\left(G\right): uvu \sim v \equiv \exists cesta z uu do vv
    • je to ekvivalence: je reflexivní (cesta z uu do uu velikosti 0), symetrická (graf je neorientovaný) i tranzitivní (jen pozor na to, že to po slepení může být sled – je potřeba to ošetřit)

V souvislém grafu GG je vzdálenost vrcholu u,vu, v minimum z delek cest z uu do vv (značíme ρ(u,v)\rho\left(u, v\right)).

  • jedná se o metriku, jelikož splňuje následující:
    1. u,v:ρ(u,v)0\forall u, v: \rho\left(u, v\right) \ge 0
    2. u,v:ρ(u,v)=0    u=v\forall u, v: \rho\left(u, v\right) = 0 \iff u = v
    3. u,v:ρ(u,v)=ρ(v,u)\forall u, v: \rho\left(u, v\right) = \rho\left(v, u\right)
    4. u,v,w:ρ(u,v)ρ(u,w)+ρ(w,v)\forall u, v, w: \rho\left(u, v\right) \le \rho\left(u, w\right) + \rho\left(w, v\right) (trojúhelníková nerovnost)

Grafové operace

  • přidání hrany/vrcholu: G+vG + v, G+hG + h
  • smazání hrany/vrcholu:
    • Ge:=G(V,E{e})G - e := G\left(V, E \setminus \left\{e\right\}\right)
    • Gv:=G(Vv,E{eEv∉e})G - v := G\left(V \setminus v, E \setminus \left\{e \in E \mid v \not\in e\right\}\right)
  • dělení hrany G % e:=(V{z},(E{x,y})({x,z},{z,y}))G\ \%\ e := \left(V \cup \left\{z\right\}, \left(E \setminus \left\{x, y\right\}\right) \cup \left(\left\{x, z\right\}, \left\{z, y\right\}\right)\right)
  • kontrakce hrany G/e:=((V{x,y}){z},{eEe{x,y}}{(e{x,y}){z}eEe{x,y}=1}) G/e := \left(\left(V \setminus \left\{x, y\right\}\right) \cup \left\{z\right\}, \\ \left\{e \in E \mid e \cap \left\{x, y\right\} \neq \emptyset\right\} \cup \left\{\left(e \setminus \left\{x, y\right\}\right) \cup \left\{z\right\} \mid e \in E \land \left|e \cup \left\{x, y\right\}\right| = 1\right\}\right)

Stromy

Základní definice:

  • strom je souvislý acyklický graf
  • les je acyklický graf (soubor stromů)
  • list – vrchol stromu s deg(v)=1\mathrm{deg}\left(v\right) = 1
Základní vlastnosti

Lemma: Strom s alespoň 2 vrcholy má alespoň 2 listy (vrcholy, do kterých vede 1 hrana).

Důkaz: uvažme nejdelší cestu. Její krajní vrcholy jsou listy, jelikož:

  • pokud z nich vede cesta někam zpět do sebe, tak graf není strom
  • pokud z nich vede cesta někam, kde jsme ještě nebyli, tak není nejdelší

Lemma: nechť vv je list grafu GG. Pak GG je strom     Gv\iff G - v je strom.

Důkaz:

  • \RightarrowGvG-v je acyklický (cyklus jsme odstraněním nevytvořili) a souvislý (vedla přes něj pouze 1 cesta, a to ta do něj)
  • \Leftarrow… po přilepení je také souvislý ( xGv \forall x \in G - v \exists\ cesta z xx do vv) a acyklický (přilepený vrchol má stupeň 1, nemůže tedy tvořit cyklus)
Charakteristika stromu

Následující tvrzení jsou ekvivalentní:

  1. GG je souvislý a acyklický (standardní)
  2. mezi každými vrcholem x,yx, y vede právě 1 cesta (jsou jednoznačně souvislé)
  3. GG je souvislý a eE(G):Ge\forall e \in E\left(G\right): G - e souvislý není (je minimálně souvislý)
  4. GG je acyklický a e(V(G)2)E(G):G+e\forall e \in \binom{V\left(G\right)}{2} \setminus E\left(G\right): G + e obsahuje cyklus (je maximálné acyklický… přidáním libovolné hrany se vytvoří cyklus)
  5. GG je souvislý a E(G)=V(G)1\left|E\left(G\right)\right| = \left|V\left(G\right)\right| - 1 (Eulerova formule)

1    51 \implies 5: indukcí:

  • n=1n = 1 sedí (0 hran, 1 vrchol, je to strom)
  • nn+1n \rightarrow n + 1… nechť GGn+1n + 1 vrcholů…
    • GG má list (lemma), jehož odtržením máme stále strom (GG')… poštváním IP máme důkaz

1    21 \implies 2: indukcí:

  • n=1n = 1 platí
  • po přilepení:
    • zachová všechny staré cesty
    • xV(Gv)!\forall x \in V\left(G - v\right) \exists! cesta xsx \sim s a \forall cesty xvx \sim v jsou tvaru xsvx \sim s \sim v (jsou jednoznačné)

1    31 \implies 3: indukcí:

  • pro n=2n = 2 platí (odebráním hrany se vrcholy rozpadnou)
  • indukce n+1nn + 1 \rightarrow n:
    • IP: graf nn se rozpadne
    • po odebrání n+1n+1 hrany se graf také rozpadne

1    41 \implies 4:

  • acykličnost sedí
  • přidáním hrany vytvoříme cyklus, jelikož tam již existuje cesta a tohle vytvoří druhou
    • pozor! neplést si s implikací 4    14 \implies 1; tohle není spor

2    12 \implies 1:

  • je tím pádem souvislý
  • kdyby existovala kružnice, pak existují 2 různé cesty

3    13 \implies 1:

  • souvislost sedí
  • kdyby existoval cyklus, tak se odstraněním nestane nesouvislý

4    14 \implies 1:

  • acykličnost sedí
  • kdyby nebyl souvislý, tak přidání nevytvoří cyklus

5    15 \implies 1 – indukcí podle počtu vrcholů:

  • existuje vrchol, který je list
  • koukneme na skóre: i=1ndi=2E(G)=2n2\sum_{i = 1}^{n} d_i = 2 \cdot \left|E\left(G\right)\right| = 2n - 2