Zkouška 16.1. varianta A

Určete počet reflexivních relací na dané množině s n prvky.

Dokažte, že relace "≤" ("kroucené") na množině {1,2,..10} je částečné uspořádání, jestliže a ≤ b, právě když a = b nebo b > a + 2. Určete minimální a maximální prvky tohoto částečného uspořádání. Kolik má toto uspořádání lineárních rozšíření?

Je pravda, že pokud zobrazení g ° f je prosté, pak také f je prosté ? Dokažte nebo vyvraťte.

Kolik je takových slov délky n, ve kterých dvě sousední písmena nejsou stejná, jestliže abeceda má k písmen ?

Formulujte a dokažte větu o lineárním rozšíření částečného uspořádání ("topologické třídění")

Strom lze ekvivalentně popsat jako "maximální graf bez kružnic". Formulujte a dokažte.

Automorfismus grafu G je isomorfismus G s G. Určete počet automorfismů prázdného grafu D_n.