Zkouška 16.01.07 varianta B

Určete počet symetrických relací na dané množině s <b>n</b> prvky.

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í ?

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.

Kolik <b>různých</b> slov (i nesmyslných) délky 7 lze složit z písmen AABBCCC?

Dokažte <b>Spernerovu</b> větu o nezávislém systému množin.

Strom lze ekvivalentně popsat jako "minimální souvislý graf." Formulujte a dokažte.