# Zkouška 16.01.07 varianta B

<{ForumPost(poster="Honza-mff", timestamp=2007-01-16 16:54:52)}>
1) Určete počet symetrických relací na dané množině s <b>n</b> prvky.  
  
2) Dokažte, že relace <= ( kroucené) na množině {1,2,...,n} je částečné uspořádání, jestliže <b>a</b> <= <b>b</b> právě když <b>a</b> = <b>b</b> nebo <b>a</b> je liché a <b>b</b> je sudé. 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í <b>g</b> (složeno) <b>f</b> je <b>na</b>, pak také <b>g</b> je <b>na</b> ? Dokažte, nebo vyvraťte.  
  
4) Kolik <b>různých</b> slov (i nesmyslných) délky 7 lze složit z písmen AABBCCC?  
  
5) Dokažte <b>Spernerovu</b> větu o nezávislém systému množin.  
  
6) Strom lze ekvivalentně popsat jako "minimální souvislý graf." Formulujte a dokažte.  
  
7) Automorfismus grafu <b>G</b> je isomorfismus G s G. Určete počet automorfismů úplného grafu <b>Kn</b>.
<{/ForumPost}>