NDMI002/Zkouška Pangrác 19. 1. 2026

(a) [2 body] Definujte, co je to strom

(b) [8 bodů] Mějme přirozené číslo $n \ge 2$ a nechť $T$ je strom, ve kterém pro každé přirozené číslo $k$ takové, aby platilo $2 \le k \le n$ , existuje právě jeden vrchol stupně $k$ . Určete v závislosti na parametru $n$ , kolik má $T$ listů.

(a) [2 body] Nechť $(X, \le)$ je nějaká částečně uspořádaná množina.

$x \in X$ je nejmenší prvek č.u.m pokud

$x \in X$ je minimální prvek č.u.m pokud

(b) [5 bodů] Nechť $W = \{ 1, ..., 10 \} \times \{ 1, ..., 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 \le x_2$
$((x_1, y_1), (x_2, y_2)) \in S$ právě tehdy, když $y_1 \le y_2$

Je relace $R$ částečné uspořádání? Pokud ano, jaké jsou všechny minimální prvky?

(c) [5 bodů] Pro relace $R$ a $S$ definované výše uvažme relaci $R \cap S$ na množině $W$ . Je tato relace částečné uspořádání? Pokud ano, jaké jsou všechny minimální prvky?

Formulujte dokažte větu o existenci dobrého 5-obarvení pro rovinné grafy.

Spoiler: alespoň ta věta

Pro každý rovinný graf $G$ platí $\chi(G) \le 5$

Jinými slovy: Každý rovinný graf je 5-obarvitelný. To znamená, že vrcholy libovolného grafu, který lze nakreslit v rovině bez křížení hran, lze obarvit nejvýše pěti barvami tak, aby žádné dva sousední vrcholy neměly stejnou barvu.

V osudí se nachází 10 bílých a 20 černých kuliček. Vylosujeme popořadě a bez vrácení 10 kuliček (vybíráme vždy náhodně 1 kulčiku, uniformně ze všech, které jsou v tuto chvíli v osudí). Jako $A_i$ označme jev $i$ -tá vylosovaná kulička je bílá, $i \in \{1, ..., 10 \}$ .

a. [4 body] Jaká je pravděpodobnost, že žádná z vylosovaných kuliček není bílá?

Spoiler: řešení

Nejjednodušeji to vyřešíme tak, že si zvolíme vhodný pravděpodobnostní prostor. Zvolme si tedy takový, kde bude elementární jev vytažení 10-tice kuliček, a který bude klasický, všechny desetice kuliček budou stejně pravděpodobné, tedy kuličky budou rozlišitelné (jde si tutéž úlohu představit s lidmi, vybíráme 10 černých). Jev $B$ bude jev, že všech 10 kuliček je černých. $|B|$ pak bude $\binom{20}{10}$ , a $|\Omega| = \binom{30}{10}$ . $P(B) = \frac{|B|}{|\Omega|} = \frac{\binom{20}{10}}{\binom{30}{10}}$

Po úpravě výrazu $\frac{\binom{20}{10}}{\binom{30}{10}}$ dostaneme $\frac{20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{30 \cdot 29 \cdot 28 \cdot 27 \cdot 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot 21}$ . Z toho je vidět, že existuje i jiné řešení, vycházející z podmíněné pravděpodobnosti. V něm budeme používat stejný pravděpodobnostní prostor jako v zadání, tedy elementární jev bude vytažení jedné kuličky z osudí. Kolik možností máme na vytažení první černé kuličky? 20. Kolik na vytažení druhé černé, za předpokladu, že 1. vytažená byla bílá? 19. Kolik na vytažení 3. černé, za předpokladu, že 1. a 2. vytažená byla bílá? 18. A tak dále, aby celkově bylo deset členů v součinu. Ve jmenovateli podobně, ale počítáme počty všech, tj. Kolik možností máme na vytažení 1. kuličky? 30. Kolik na vytažení 2. kuličky, za předpokladu, že jedna už byla vytažena? 29. Kolik na vytažení 3. kuličky, za předpokladu, že dvě už byly vytaženy? 28. Atd, pro 10 kuliček.

Definujme si $B_i = \overline{A_i}$ , tedy jako opačný jev k jevu $A_i$ , tedy, že $i$ -tá kulička je černá. Ze zadání chceme pravděpodobnost vytažení 10 černých kuliček, což je $P(B_1 \cap B_2 \cap ... \cap B_{10})$ Spočteme př. $P(B_1 \cap B_2)$ . Z definice podmíněné pravděpodobnosti máme $P(B_2 | B_1 ) = \frac{P(B_1 \cap B_2)}{P(B_1)}$

To si upravíme na $P(B_1 \cap B_2) = P(B_2 | B_1) \cdot P(B_1)$

Podobně $P((B_1 \cap B_2) \cap B_3) = P(B_1 \cap B_2) \cdot P(B_3 \ \mid \ B_1 \cap B_2)$ , tedy $P(B_1 \cap B_2 \cap B_3) = P(B_2 | B_1) \cdot P(B_1) \cdot P(B_3 \ \mid \ B_1 \cap B_2)$ . Takto můžeme pokračovat až do $P(B_1 \cap B_2 \cap ... \cap B_{10})$ .

$P(B_1 \cap B_2 \cap ... \cap B_{10}) = P(B_{10} \ \mid \ B_1 \cap ... \cap B_9) \cdot P(B_9 \ \mid \ B_1 \cap ... \cap B_8 ) \cdot ... \cdot P(B_1)$

Všimněte si, že ty podmíněné pravděpodobnosti odpovídají úvahám na začátku. Tedy tak dostaneme přesně ten zlomek $\frac{20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{30 \cdot 29 \cdot 28 \cdot 27 \cdot 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot 21}$ , když přemýšlíme v součinu pravděpodobností, tak takto $\frac{20}{30}\cdot\frac{19}{29}\cdot\frac{18}{28}\cdot\frac{17}{27}\cdot\frac{16}{26}\cdot\frac{15}{25}\cdot\frac{14}{24}\cdot\frac{13}{23}\cdot\frac{12}{22}\cdot\frac{11}{21}$

b. [4 body] Jaká je pravděpodobnost jevu $A_2$ ?

Spoiler: řešení

Využijeme větu o úplné pravděpodobnosti: $P(A_2) = P(A_2 \cap A_1) + P(A_2 \cap \overline{A_1}) = P(A_2 \mid A_1) \cdot P(A_1) + P(A_2 \mid \overline{A_1}) \cdot P(\overline{A_1})$

$P(A_2 \mid A_1)$ , tedy pravděpodobnost vytažení 2. kuličky bílé za podmínky, že 1. vytažená byla též bílá, už umíme spočítat, to je $\frac{9}{29}$ , $P(A_1)$ je $\frac{10}{30}$ , $P(A_2 \mid \overline{A_1})$ , tedy pravděpodobnost vytažení 2. kuličky bílé za podmínky, že 1. vytažená byla černá, je $\frac{10}{29}$ , a $P(\overline{A_1})$ je $1 - P(A_1) = \frac{20}{30}$ . V součinu tedy: $P(A_2) = P(A_2 \mid A_1) \cdot P(A_1) + P(A_2 \mid \overline{A_1}) \cdot P(\overline{A_1}) = \frac{9}{29} \cdot \frac{10}{30} + \frac{10}{29} \cdot \frac{20}{30} = \frac{1}{3}$ To je zajímavej moment, že to vyšlo $\frac{1}{3}$, tedy stejně, jako kdybychom kuličky vraceli. Myslím si, že schválně, aby to nás trochu zmátlo. Obecně to když kuličky nevracíme stejně nevychází.

c. [4 body] Jsou jevy $A_1$ , $A_2$ , $A_3$ nezávislé? Odpověď podpořte výpočtem podle def. nezávislosti jevů, pouze intuitivní zdůvodnění nestačí.

Spoiler: řešení

Jevy $A_1$ , $A_2$ , $A_3$ jsou z definice nezávislé, když platí: $P(A_1 \cap A_2 \cap A_3) = P(A_1) \cdot P(A_2) \cdot P(A_3)$

$P(A_2)$ jsme spočetli v b. jako $\frac{1}{3}$

$\begin{aligned} P(A_3) &= P(A_3 | A_1 \cap A_2) \cdot P(A_1 \cap A_2) \\ &+ P(A_3 | A_1 \cap \overline{A_2}) \cdot P(A_1 \cap \overline{A_2}) \\ &+ P(A_3 | \overline{A_1} \cap A_2) \cdot P(\overline{A_1} \cap A_2) \\ &+ P(A_3 | \overline{A_1} \cap \overline{A_2}) \cdot P(\overline{A_1} \cap \overline{A_2}) \end{aligned}$

$\begin{aligned} P(A_3 | A_1 \cap A_2) &= \frac{8}{28} \\ P(A_1 \cap A_2) = P(A_2 | A_1) \cdot P(A_1) &= \frac{9}{29} \cdot \frac{10}{30} \\ \\ P(A_3 | A_1 \cap \overline{A_2}) &= \frac{9}{28} \\ P(A_1 \cap \overline{A_2}) = P(\overline{A_2} | A_1) \cdot P(A_1) &= \frac{20}{29} \cdot \frac{10}{30} \\ \\ P(A_3 | \overline{A_1} \cap A_2) &= \frac{9}{28} \\ P(\overline{A_1} \cap A_2) = P(A_2 | \overline{A_1}) \cdot P(\overline{A_1}) &= \frac{10}{29} \cdot \frac{20}{30} \\ \\ P(A_3 | \overline{A_1} \cap \overline{A_2}) &= \frac{10}{28} \\ P(\overline{A_1} \cap \overline{A_2}) = P(\overline{A_2} | \overline{A_1}) \cdot P(\overline{A_1}) &= \frac{19}{29} \cdot \frac{20}{30} \end{aligned}$

Pro kontrolu je dobré si zkusit sečíst $P(A_1 \cap A_2)$ , $P(A_1 \cap \overline{A_2})$ , $P(\overline{A_1} \cap A_2)$ , $P(\overline{A_1} \cap \overline{A_2})$ , které dohromady musí být 1, pokrývají 100 % všech možností.

Takže když dosadíme vyjde:

$P(A_3) = \left( \frac{10 \cdot 9}{30 \cdot 29} \cdot \frac{8}{28} \right) + \left( \frac{10 \cdot 20}{30 \cdot 29} \cdot \frac{9}{28} \right) + \left( \frac{20 \cdot 10}{30 \cdot 29} \cdot \frac{9}{28} \right) + \left( \frac{20 \cdot 19}{30 \cdot 29} \cdot \frac{10}{28} \right)$

$P(A_3) = \frac{8 \ 120}{24 \ 360} = \frac{1}{3}$

Takže víme, že $P(A_1) = P(A_2) = P(A_3) = \frac{1}{3}$

Teď ještě potřebujeme $P(A_1 \cap A_2 \cap A_3)$ , tj. že 1. kulička je bílá, 2. kulička je bílá a zároveň 3. kulička je bílá.

$\begin{aligned} P(A_1 \cap A_2 \cap A_3) &= P(A_1 \cap A_2) \cdot P(A_3 \mid A_1 \cap A_2) \\ &= P(A_1) \cdot P(A_2 \mid A_1) \cdot P(A_3 \mid A_1 \cap A_2) \end{aligned}$

tah ( $A_1$ ): V osudí je 10 bílých z celkem 30 kuliček.

$P(A_1) = \frac{10}{30}$

tah ( $A_2$ ): Pokud byla první bílá, v osudí zbývá 9 bílých z celkem 29 kuliček.

$P(A_2 | A_1) = \frac{9}{29}$

tah ( $A_3$ ): Pokud byly první dvě bílé, v osudí zbývá 8 bílých z celkem 28 kuliček.

$P(A_3 | A_1 \cap A_2) = \frac{8}{28}$

Takže už můžeme vyhodnotit: $P(A_1 \cap A_2 \cap A_3) = P(A_1) \cdot P(A_2) \cdot P(A_3)$

$P(A_1 \cap A_2 \cap A_3) = \frac{10}{30} \cdot \frac{9}{29} \cdot \frac{8}{28}$

$P(A_1) \cdot P(A_2) \cdot P(A_3) = \left(\frac{1}{3}\right)^3$

Levá a prává strana se nerovná, výraz neplatí, jevy tedy jsou závislé. (což bychom intuitivně čekali, že když kuličky nevracím, tak budou, ale zase tady byly ty matoucí výsledky $\frac{1}{3}$ , které někoho mohly zmást, proto taky chtěli abychom to uměli říct výpočtem.)

(a) [4 body] Formulujte Kuratowského větu (věta ekvivalentně charakterizuje rovinné grafy). Stačí formulace, větu nedokazujte.

Spoiler: řešení

graf je rovinný $\iff$ graf neobsahuje žádné dělení $K_5$ nebo $K_{3,3}$

(b) [8 bodů] Rozhodněte, zda $K_6$ je rovinný. Pokud ne, určete minimální počet hran, které je nutné z tohoto grafu odebrat, aby výsledný graf rovinný byl.

Spoiler: řešení

Věta: Rovinný graf na $v$ vrcholech ( $v \ge 3$ ) má nejvýše $3v-6$ hran.

Jak se na větu přišlo btw

Maximální rovinný graf (tedy rovinný graf s největším možným počtem hran, přidání další hrany by způsobilo, že rovinný nebude) s $\ge 3$ vrcholy je triangulace = hranice všech stěn odpovídá trojúhelníku v grafu.

V triangulaci je každá stěna ohraničena 3 hranami, každou hranu ale tak započítáme 2x (zevnitř a zevně té stěny):

$3f = 2e$

$f = \frac 2 3 \cdot e$ , dosadíme do Eulerovy formule:

$v + \frac 2 3 e = e + 2$

$3v - 6 = e$

Každý rovinný graf má méně nebo rovno hran jako maximální rovinný graf, tudíž má nejvýš $3v - 6$ hran.

Tak ověříme: $K_6$ má $v=6$ a $e=\binom{6}{2} = \frac{6 \cdot 5}{2!} = 15$ .

$15 \le 3 \cdot 6 - 6$

$15 \le 12$ neplatí, graf není rovinný. Z toho vyplývá, že je třeba odstranit 3 hrany, aby rovinný byl. Rozhodnout, jestli je $K_6$ rovinný, by šlo i podle Kuratowského věty, protože $K_5$ je podgrafem $K_6$ . Ale Kuratowského věta už nám neřekne, kolik hran je třeba odebrat.