Zkouška Kantor 29. 1. 2025

1. [10 bodů] Dokažte následující vztah (výpočtem nebo kombinatorickou úvahou nebo nějak jinak), pro $n \geq 1$: $$\sum_{k=0}^{n}k \cdot \binom{n}{k} = n \cdot 2^{n-1}$$

2. (a) [2 body] Doplňte definici symetrické relace:
   Řekneme, že relace $R$ na množině $X$ je symetrická, pokud…

   (b) [3 body] Nechť $R$ je relace $\{(1, 1), (2, 2), (2, 3), (3, 2)\}$ na množině $X = \{1, 2, 3\}$.
   Je $R$ reflexivní relace? Je $R$ symetrická relace? Odpovědi dostatečně zdůvodněte.

   (c) Nyní nechť $Y = \{1, 2, 3, 4\}$

   • i. [4 body] Kolik je všech ekvivalencí na množině $Y$? (Nápověda: Ekvivalence nám dělí nosnou množinu na třídy ekvivalence.)

   • ii. [2 body] Kolik je všech relací na množině $Y$?

   • iii. [3 body] Kolik je reflexivních relací na množině $Y$? (Nápověda: Jak vypadá matice, která odpovídá reflexivní relaci?)

3. [10 bodů] Dokažte dolní a horní mez tohoto odhadu: $$n^{n/2} \leq n! \leq \left( \frac{n+1}{2} \right)^n$$

4. (a) [4 body] Formulujte Kuratowského větu.* Stačí formulace, větu nedokazujte.

   (b) [4 body] Je graf na obrázku rovinný? Buďto ho nakreslete rovinně, nebo nějakým přesvědčivým (!) způsobem argumentujte, proč rovinné nakreslení neexistuje.

   (c) [4 body] Průměrný stupeň grafu $G$ je průměr jeho stupňů, neboli číslo $$\frac{1}{n} \left( \sum_{v \in V(G)}\text{deg}(v) \right)$$ (kde $n$je počet vrcholů grafu$G$). Je pravdivé následující tvrzení? Buďto ho dokažte (třeba s použitím nějaké věty z přednášky), nebo najděte nějaký konkrétní protipříklad.

   Tvrzení: *Kdykoliv $G$ je graf, který má průměrný stupeň nejvýše $2,3$, pak je $G$ rovinný.

5. (a) [4 body] Doplňte definice grafu a souvislého grafu:

   • Graf je…

   • Řekneme, že graf $G$ je souvislý, pokud…

   (b) Pokud $t$ je přirozené číslo a $t \geq 2$, tak definujeme graf $G_t$ takto: vrcholy jsou všechny dvouprvkové množiny čísel z množiny $\{1, \ldots, t\}$ (neboli $V(G_t) = \binom{\{1, \ldots, t\}}{2}$) a dvě takové množiny tvoří hranu právě tehdy, když jsou disjunktní. Zde je například obrázek $G_5$:

   (Mimochodem, tyto grafy jsou celkem důležité a mají název: Kneserovy grafy.)
   [4 body] Pro každé $t \geq 2$ rozhodněte, zda je $G_t$ souvislý graf. Odpověď dostatečně zdůvodněte.

   (c) [3 body] Graf $G_t$ definovaný výše má všechny vrcholy stejného stupně. Jakého? (Bude to pochopitelně nějaké číslo, které závisí na $t$.) Odpověď dostatečně zdůvodněte.

   (d) [3 body] Nyní předpokládejme, že $t = 4k+3$ pro nějaké přirozené číslo $k$. Je graf $G_t$ (definovaný výše) eulerovský? Odpověď dostatečně zdůvodněte.