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.