Skuskova pisomka 11.1. varianta B

[Návštěvník]

maximum bolo 21 bodov, na trojku stacilo 8.

1. (5 bodov)
pro prirozene cislo n>=5 definujeme graf G takto: Mnozina vrcholu sestava ze vsech dvouprvkovych podmnozin {1,2...,n}, a dve takove podmnoziny jsou v grafu G spojeny hranou, prave kdyz maji prazdny prunik. Urcete, kolik vrcholu a hran ma graf G, a rozhodnete, zda je souvisly.

2. (vsetky moznosti za 2 body)
a)
Na mnozine X = {1,2,3,4,5,6,7,8} definujeme relaci castecneho usporadani <= takto: a<=b prave kdyz b je delitelne a. Nakreslete Hasseuv diagram usporadane mnoziny (X,<=).
b)
Definujte zobrazeni mnoziny X na mnozinu Y. Naleznete priklad mnoziny X a zobrazeni f:X->X, ktere je na, ale neni proste.
c)
Usporadejte funkce (kde promenna n je prirozene cislo) podle rychlosti rustu, tj. urcete, ktera z nich pro velke n nabyva nejvetsi hodnoty, ktera druhe nejvetsi, atd.
10 n^3 (n/2 spodni cela cast)! 7^n 2^n^2


3. (5 bodov)
Kolik ma uplny bipartitni graf K3,5 eulerovskych podmnozin hran? Kolik z nich obsahuje lichy pocet hran?

4. (5 bodov)
Zformulujte a dokazte Spernerovu vetu o nezavislych systemech podmnozin.

spravne odpovede:
1.
V= (n nad 2)
|E| =.5 *suma deg v = .5 *(n nad 2)*(n-2 nad 2)
dokazat souvislost
2.
c)
bolo treba jednotlive mocniny zlogaritmovat a porovnat. ten faktorial bolo treba odhadnut pomocou niecoho napriklad Gaussa.
10n^3 < 7^n < (n/2 spodni cela cast)! < 2^n^2

3.
|E| ... zisti sa napriklad tak, ze sa nakresli graf.
dim C = |E| - |V| + 1 = 8
2^ dimC = 2^8 ... pocet vsetkych eulerovskych podmnozin
pocet lichych podmnozin... 0 (vsetky podmnoziny su sude, dokaze sa to nejako z tych elementarnych kruznic)

4.
napisat dokaz z prednasky.