# pis zk 17.1. 07 skupina A(asi)

<{ForumPost(poster="Anonymous", timestamp=2007-01-17 19:32:15)}>
(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.
<{/ForumPost}>