Zkouska 11.1.2007

[marie 56]

1. Odvodte vzorec pro pocet permutaci mnoziny {1,2,...,n} s prave jednim pevnym bodem.
2.
a) Definujte proste zobrazeni mnoziny X do mnoziny Y. Naleznete priklad mnoziny X a zobrazeni X -> X, ktere je proste ale neni na.
b) Na mnozine X = {1, 2,...,8} definujeme relaci castecneho usporadani takto: aRb prave kdyz a=b nebo b>a+2. Nakreslete Hasseuv diagram teto usporadane mnoziny.
c) usporadejte nasledujici funkce (kde promenna n je prirozene cislo) podle rychlosti rustu, tj. urcete, ktera z nich pro velke n nabyva nejvetsi hodnoty, druhe nejvetsi, atd.
10^n (2n)! 10n^5 2^n^2
3. Bud G=(V,E) graf. Zobrazeni f: V->V nazveme automorfismem grafu G, pokud je to isomorfismus grafu G s nim samotnym. Kolik automorfismu maji Kn (uplny graf na n vrcholech), Pn (cesta delky n), Cn (kruznice delky n).
4.Zformulujte a dokazte Erdosovo Szekeresovo lemma.