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