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

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

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

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

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

    (b) [5 bodů] Nechť W={1,...,10}×{1,...,10}W = \{ 1, ..., 10 \} \times \{ 1, ..., 10 \} Na množině WW definujeme relace RR a SS takto:

    • ((x1,y1),(x2,y2))R((x_1, y_1), (x_2, y_2)) \in R právě tehdy, když x1x2x_1 \le x_2

    • ((x1,y1),(x2,y2))S((x_1, y_1), (x_2, y_2)) \in S právě tehdy, když y1y2y_1 \le y_2

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

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

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

  4. 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 AiA_i označme jev ii-tá vylosovaná kulička je bílá, i{1,...,10}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 BB bude jev, že všech 10 kuliček je černých. B|B| pak bude (2010)\binom{20}{10} , a Ω=(3010)|\Omega| = \binom{30}{10}. P(B)=BΩ=(2010)(3010)P(B) = \frac{|B|}{|\Omega|} = \frac{\binom{20}{10}}{\binom{30}{10}}

    Po úpravě výrazu (2010)(3010)\frac{\binom{20}{10}}{\binom{30}{10}} dostaneme 2019181716151413121130292827262524232221\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 Bi=AiB_i = \overline{A_i}, tedy jako opačný jev k jevu AiA_i, tedy, že ii-tá kulička je černá. Ze zadání chceme pravděpodobnost vytažení 10 černých kuliček, což je P(B1B2...B10)P(B_1 \cap B_2 \cap ... \cap B_{10}) Spočteme př. P(B1B2)P(B_1 \cap B_2). Z definice podmíněné pravděpodobnosti máme P(B2B1)=P(B1B2)P(B1)P(B_2 | B_1 ) = \frac{P(B_1 \cap B_2)}{P(B_1)}

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

    Podobně P((B1B2)B3)=P(B1B2)P(B3  B1B2)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(B1B2B3)=P(B2B1)P(B1)P(B3  B1B2)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(B1B2...B10)P(B_1 \cap B_2 \cap ... \cap B_{10}).

    P(B1B2...B10)=P(B10  B1...B9)P(B9  B1...B8)...P(B1)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 2019181716151413121130292827262524232221\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 2030192918281727162615251424132312221121\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 A2A_2?

    Spoiler: řešení

    Využijeme větu o úplné pravděpodobnosti: P(A2)=P(A2A1)+P(A2A1)=P(A2A1)P(A1)+P(A2A1)P(A1)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(A2A1)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 929\frac{9}{29}, P(A1)P(A_1) je 1030\frac{10}{30}, P(A2A1)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 1029\frac{10}{29}, a P(A1)P(\overline{A_1}) je 1P(A1)=20301 - P(A_1) = \frac{20}{30}. V součinu tedy: P(A2)=P(A2A1)P(A1)+P(A2A1)P(A1)=9291030+10292030=13P(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 A1A_1, A2A_2, A3A_3 nezávislé? Odpověď podpořte výpočtem podle def. nezávislosti jevů, pouze intuitivní zdůvodnění nestačí.

  5. (a) [4 body] Formulujte Kuratowského větu (věta ekvivalentně charakterizuje rovinné grafy). Stačí formulace, větu nedokazujte. (b) [8 bodů] Rozhodněte, zda K6K_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.