# Zkouška 16.1. varianta A

<{ForumPost(poster="Wololo", timestamp=2007-01-16 19:01:47)}>
1) Určete počet reflexivních relací na dané množině s *n* prvky.  
2) 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í?  
3) Je pravda, že pokud zobrazení *g* ° *f* je prosté, pak také *f* je prosté ? Dokažte nebo vyvraťte.  
4) Kolik je takových slov délky *n*, ve kterých dvě sousední písmena nejsou stejná, jestliže abeceda má *k* písmen ?  
5) Formulujte a dokažte větu o lineárním rozšíření částečného uspořádání ("topologické třídění")  
6) Strom lze ekvivalentně popsat jako "maximální graf bez kružnic". Formulujte a dokažte.  
7) Automorfismus grafu *G* je isomorfismus *G* s *G*. Určete počet automorfismů prázdného grafu *D<sub>n</sub>*.
<{/ForumPost}>