Fórum studentů MFF UK

Otázky z odpoledne:
1) Princíp inkluze a exkluze + důkaz
2) Dokázat ekvivalenci: (d1, d2, ..., dn) je skóre stromu <=> suma (di, i=1..n) = 2n - 2
3) Dokázat ekvivalenci: V(G) = E(G) + (počet komponent G) <=> graf G je les
4) Kolik je asymetrických relací na množině {1..n} (je ich (2^n) * 3^((n^2 - n)/2))

1) Věta o pěti barvách + důkaz
2) Erdős - Szekeresovo lemma + důkaz
3) Dokázat, že pro každý graf platí: pro všechny v z V(G):deg(v)>=d, potom v grafu existuje cesta délky d
4) Kolik existuje permutací z množiny {1_n} s k pevnými body

Naprosto pohodová zkouška, není se čeho bát