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

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

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