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