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 akademického 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 na mail).

Relace

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

Funkce

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

Vlastnosti relace

Ekvivalence

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

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]</em>

Uspořádání

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

Definice (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ě:

Definice (lexikografické uspořádání): Nechť XX je abeceda a \le uspořadání na XX. Pak definujeme lexikografické uspořádání (X2,LEX)\left(X^2, \le_{LEX}\right) následně: (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)

Dlouhý a široký

Definice ((anti)řetězec): pro (X,)\left(X, \le\right) ČUM:

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:

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 (z 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: 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

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)

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

(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: budeme počítat dvěma způsoby:

Vlastnosti kombinačních čísel:

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:

Poznámka:

Odhady pro faktoriál

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

Důkaz: (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):

Důkaz (wtf): Indukce:

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}

Princip inkluze/exkluze

Věta (inkluze a 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:

Grafy

Definice (graf): 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.

Odrudy

Definice (izomorfismus): 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)

Grafové odhady

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

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

Tvrzení: 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)

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:

Definice (podgraf): 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).

Definice (indukovaný podgraf): 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}.

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

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

Tvrzení: pokud existuje sled z xx do yy, pak existuje i cesta.

Definice (souvislost): Graf GG je souvislý  u,vV(G) \ \equiv \forall u, v \in V\left(G\right) \exists\ cesta v GG z uu do vv

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

Grafové operace

Stromy

Definice (strom les, list):

Tvrzení: 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ž:

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

Důkaz:

Věta (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)</em>

Důkaz: 1    51 \implies 5: indukcí:

1    21 \implies 2: indukcí:

1    31 \implies 3: indukcí:

1    41 \implies 4:

2    12 \implies 1:

3    13 \implies 1:

4    14 \implies 1:

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