Zkouška Kantor 03. 02. 2025

1. (a) [2 body] Definujte, co je to strom:

   (b) [8 bodů] Nechť $T$ je strom. Dokažte (dostatečně podrobně), že pro něj platí Eulerův vzorec (ten dává do souvislosti počet jeho vrcholů a hran). Toto tvrzení je součástí obsáhlejší věty jménem Charakterizace stromů – tuto větu tedy při důkazu nepoužívejte.

2. (a) [2 body] Doplňte definici tranzitivní relace:
   Relace $R$ na množině $X$ je tranzitivní, pokud …

   (b) [6 bodů] Nechť $W = \{1, \ldots, 10\} \times \{1, \ldots, 10\}$ (t.j. $W$ je množina všech uspořádaných dvojic přirozených čísel $(i, j)$, kde $1 \leq i \leq 10$ a $1 \leq j \leq 10$). Na množině $W$ definujeme relace $R$ a $S$ takto:

   • $((x_1, y_1), (x_2, y_2)) \in R$ právě tehdy, když $x_1 = x_2$

   • $((x_1, y_1), (x_2, y_2)) \in S$ právě tehdy, když $y_1 = y_2$

   Je relace $R$ ekvivalence? Odpověď dostatečně zdůvodněte. Pokud je to ekvivalence, jak vypadá třída této ekvivalence, určená prvkem $(4, 7)$?

   (c) [4 body] Pro relace $R$ a $S$ definované výše uvažme relaci $R \cup S$ na množině $W$ (t.j. sjednocení těch dvou relací). Je tato relace ekvivalence? Odpověď dostatečně zdůvodněte. Pokud je to ekvivalence, jak vypadá třída této ekvivalence, určená prvkem $(4, 7)$?

3. Deset očíslovaných pirátů má truhlu s pokladem, která obsahuje 20 zlatých a 30 stříbrných mincí. Piráti si rozdělují poklad: náhodně vytáhnou z truhly jednu minci a dají ji prvnímu pirátovi (t.j. tomu, který má číslo 1). Pak ze zbylých mincí náhodně vytáhnou druhou minci a dají ji druhému pirátovi a tak dále. Skončí ve chvíli, kdy každý z pirátů má přesně jednu minci.

   (a) [4 body] Jaká je pravděpodobnost, že nějací dva piráti dostanou zlaté mince a zbylých osm dostane stříbrné mince?

   (b) [3 body] Písmenem $A$ označíme jev, že první pirát (t.j. ten s číslem 1) dostane zlatou minci. Písmenem $B$ označíme jev, že třetí pirát (t.j. ten s číslem 3) dostane zlatou minci. Jaká je pravděpodobnost, že nastane jev $A$? Jaká je pravděpodobnost, že nastane jev $B$? Odpovědi dostatečně zdůvodněte.

   (c) [4 body] Jsou jevy $A$ a $B$ definované výše nezávislé? Odpověď podpořte výpočtem podle definice nezávislosti jevů (pouze intuitivní zdůvodnění nestačí).

4. Pro $d \in \N$ definujeme graf $G_d$ takto: $V(G_d) = \{0, 1, \ldots, d\}^d$, tj. jeho vrcholy jsou všechny posloupnosti $d$ čísel, v nichž se vyskytují pouze čísla $0, 1, \ldots, d$. Dvě takové posloupnosti tvoří hranu právě tehdy, když se liší ve všech souřadnicích. Zde je například obrázek $G_2$:

   (a) [3 body] Definujte pojmy obarvení grafu a barevnosti grafu.

   (b) [4 body] Jakou barevnost má $G_2$ Odůvodněte dostatečně obě nerovnosti, tj. najděte nějaké optimální obarvení a dokažte, že nestačí méně barev.

   (c) [6 bodů] Jakou barevnost má $G_d$? Odůvodněte dostatečně obě nerovnosti. Tedy pro důkaz jedné nerovnosti popište přesně nějaké optimální obarvení (tj. když Vám někdo dá nějakou posloupnost délky $d$, ve které jsou jen čísla $0, \ldots, d$, tak byste měli být snadno schopni říct, jakou ji přiřadíte barvu) a odůvodněte, že tato funkce splňuje podmínky obarvení. Abyste odůvodnili druhou nerovnost, tak dokažte, že nestačí méně barev.

5. [4+10 bodů] Formulujte a dokažte větu, která je známá jako Věta o Dlouhém a Širokém. (To je věta, která dává do souvislosti velikosti řetězců a antiřetězců v částečně uspořádané množině.)