pis zk 17.1. 07 skupina A(asi)

(vyucujici: Matousek)

1.kolik je vzajemne neizomorfnich grafu s 9. vrcholy, jejichz kazdy vrchol ma stupen 0 nebo 2.

2.a) definujte bijektivni zobrazeni, kolik je bijektivnich zobrazeni z X do Y. X= a,b,c,d Y= 3,2,5,9

b) definujte pojem kostry grafu. kolik nejvice hran muze mit kostra uplneho bipartitniho grafu K20,10

c) usporadejte nasledujici funkce podle rychlosti rustu:
2n nad 2 ; n! ; 4na odmocninu z n ; odmocnina z n na 4 ;

3. necht Q je graf na mnozine vrcholu {0,1}^n }(tj vrcholy jsou usporadane n/tice nu la jednicek), pricemz mezi vrcholy vede hrana prave tehdy, pokud se lisi pouze v jedine souradnici. rozhodnete, pro ktera n = 1.2... se graf Q da nakreslit jednim uzvrenym tahem

4. Jakou dimenzi ma prostor kruznic (sestavajici se z vsech eulerovskych podmnozih hran) souvisleho grafu G s n vrcholy a m hranami?
   Vase tvrzeni dokazte.