# Skuskova pisomka 11.1. varianta B

<{ForumPost(poster="Anonymous", timestamp=2007-01-12 14:07:16)}>
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.
<{/ForumPost}>