Zkouška 2026-??-?? Fiala

1. Definuj zobrazení a bijektivní zobrazení. Nechť $X$ je konečná množina a pro zobrazení $f: X \to X$ platí, že pro každé $x \in X$ existuje $k > 0$ takové, že $f^{(k)}(x) = x$. Jaké vlastnosti má $f$?

2. Definuj indukovaný podgraf. Kolik neizomorfních indukovaných podgrafů má úplný bipartitní graf $K_{10,5}$?

3. Definuj obarvení grafu a chromatické číslo. Najdi graf na $8$ vrcholech, jehož chromatické číslo je $3$ a jehož všechny vrcholy mají stupeň $2$.

4. Zformuluj a dokaž větu o velikosti řetězce a nezávislé množiny v částečném uspořádání. (Věta o dlouhém a širokém)

5. Sepiš přehledově definice, tvrzení a souvislosti z Ramseyho teorie. Důkazy tvrzení uvádět nemusíte.

6. Dokaž, že v každém souvislém grafu existují vrcholy $u, v$ takové, že $G - u$ a $G - v$ jsou taktéž souvislé.

7. Pro každé přirozené $n$ definujme graf na vrcholech $\{0, 1\}^n$. Hrana mezi dvěma vrcholy $(x_1, x_2, \dots, x_n)$ a $(y_1, y_2, \dots, y_n)$ povede vždy, když se tyto body liší právě ve třech souřadnicích. Pro jaké $n$ v tomto grafu existuje uzavřený tah přes všechny hrany?