Zkouška 8.1.2021 14:00 - Martin Mareš
Napsal: 8. 1. 2021 19:19
1. Definujte uspořádání, lineární uspořádání, nejmenší a minimální prvek.
2. Definujte obarvení a barevnost grafu. Vyslovte a dokažte větu o 5 barvách (pro rovinné grafy).
3. Dokažte, že doplněk nesouvislého grafu je vždy souvislý. (Doplněk má stejné vrcholy a hrany vedou právě tam, kde v původním grafu nevedly.)
4. Po dlouhé noci se M opilých námořníků vrací do N kajut (samozřejmě náhodně). Jaká je střední hodnota (a) počtu námořníků v konkrétní kajutě, (b) počtu prázdných kajut?
2. Definujte obarvení a barevnost grafu. Vyslovte a dokažte větu o 5 barvách (pro rovinné grafy).
3. Dokažte, že doplněk nesouvislého grafu je vždy souvislý. (Doplněk má stejné vrcholy a hrany vedou právě tam, kde v původním grafu nevedly.)
4. Po dlouhé noci se M opilých námořníků vrací do N kajut (samozřejmě náhodně). Jaká je střední hodnota (a) počtu námořníků v konkrétní kajutě, (b) počtu prázdných kajut?