# Zkouška Ida/Pangrác 10. 02. 2026

1.
- a. [2 body] Doplňte definici tranzitivní relace.
- b. [6 bodů] Nechť $W = \{1, \dots, 10\} \times \{1, \dots, 10\}$ (t.j. W je množina všech uspořádaných dvojic přirozených čísel (i, j), kde $1 \leq i, j \leq 10$). Na množině W definujeme relace R a S takto (níže). 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)? 
  - ((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$.
- 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)?
2. [2 + 10 bodů] **Formulujte** a **dokažte** Binomickou větu.
3. Máme tři běžné šestistěnné kostky - bílou, šedou a černou. Označme jako jev A to, že na bílé kostce padlo sudé čislo, jako jev B to, še součet hodů na bílé a šedé je sudý a jako jev C to, že součet všech tří kostek je sudý.
- a. [4 body] Jsou jevy A a B nezávislé? Svou odpověď podpořte relevantním výpočtem.
- b. [2 body] Definujete podmíněnou pravděpodobnost (pravděpodobnost jevu D za podmínky, že nastal jev E).
- c. [4 body] Určete pravděpodobnost jevu A **za podmínky**, že nastal jev C.
4. Pro $d \in \mathbb{N}$ definujeme graf $G_d$ takto: $V(G_d) = (0, 1)^d$, t.j. jeho vrcholy jsou všechny d-tice nul a jedniček, a dvě takové d-tice tvoří hranu právě tehdy, když se liší přesně ve dvou souřadnicích.
- a. [2 body] Definujte **stupeň vrcholu** v grafu.
- b. [4 body] Pro která d je graf $G_d$ **souvislý**? Odpověď dostatečně zdůvodněte.
- c. [4 body] Mají všechny vrcholy grafu $G_d$ stejný **stupeň**? V závislosti na parametru d určete, jakých hodnot mohou stupně vrcholů grafu $G_d$ nabývat.
- d. [2 body] Pro která d je graf $G_d$ **eulerovský**? Odpověď dostatečně odůvodněte.
5.
- a. [3 body] Formulujte **Kuratowského větu** pro rovinné grafy.
- b. [10 bodů] Pro $n \geq 4$ uvažujme graf $C^2_n$ vzniklý z kružnice $C_n$, přidáním hran spojujících vrcholy ve vzdálenosti 2 na původní kružnici. (Pro $n \geq 5$ tím pádem přidáme n nových hran, pro $n = 4$ jen 2 hrany.) Rozhodněte, pro která $ n \in \{4, 5, 6, 7\}$ je graf $C^2_n$ rovinný. Svou odpověď přiměřeně zdůvodněte.