# Zkouška Pangrác 8. 1. 2026

## Příklad 1

Definujte, co musí splňovat binární relace $R \subseteq X \times X$, aby byla ekvivalence.

Jednotlivé vlastnosti rozepište.

---

## Příklad 2

Formulujte a dokažte Princip inkluze a exkluze.

---

## Příklad 3

Mějme dvě hrací férové kostky – šestistěnnou a dvanáctistěnnou. Hodíme oběma kostkama a jako $X$ označíme číslo, které padlo na šestistěnné kostce, jako $Y$ číslo, které padlo na dvanáctistěnné kostce a jako $Z$ výsledek na dvanáctistěnné zmenšený o výsledek šestistěnné kostky.

a) Jaká je pravděpodobnost, že hodnota $Z$ bude záporná?

b) Spočtěte střední hodnoty náhodných veličin $X$, $Y$, $Z$.

---

## Příklad 4

Pro $n \in \mathbb{N}$ ($n \ge 3$) definujme graf s vrcholy
$V = \{0,1\}^n$
(posl. nul a jedniček délky $n$) a hranami
$
E = \{\{(a_1,\dots,a_n),(b_1,\dots,b_n)) : \lvert \{ i : a_i \ne b_i \} \rvert \text{lichá} \}\}
$
(hrany spojují ty $n$-tice, které se liší v lichém počtu pozic).

V závislosti na $n$ rozhodněte, zda $G$ je:

a) souvislý,
b) bipartitní,
c) eulerovský.

Odpovědi zdůvodněte.

---

## Příklad 5

Nechť $k \in \mathbb{N}$ a $G = (V,E)$ je strom. Pro každé z následujících tvrzení rozhodněte, zda je pravdivé:

a) Pokud $\exists v \in V : \deg v = k$, potom $G$ má (alespoň) $k$ listů.

b) Pokud $G$ má $k$ listů, potom $\exists v \in V : \deg v \ge k$.

c) Pokud $G$ má právě $k$ listů, potom
$\forall v \in V : \deg v \le k$

Odpovědi zdůvodněte.