# Skuska u Valtra 12.1.2007

<{ForumPost(poster="Kudo", timestamp=2007-01-12 23:23:11)}>
Ja osobne som este nebol na skuske. Idem v pondelok 15.1.2007 ale dostali sa ku mne nejake zadania, ktore boli 12.1.2007 tak ix tu davam :  
  
1.počet zobrazení z čtyřprvkový do pěti prvkový množiny a kolik z nich je  
prostých  
2.definici izomorfismu grafů + nakreslit všechny neizomorfní stromy na 6  
vrcholech  
3.co je tranzitivní relace a určit jestli jsou x^4>y, x>y^2 a x<>y  
tranzitivní  
4.napsat vzorec pro PIE  
5.důkaz věty o 4 barvách pro graf bez K_3  
6.ukázat, pro která n existuje graf se skóre (1,3,3,...,3,3) //1 jednička a  
n-1 trojek  
  
druhe zadanie :  
1a) definicia suvislosti komplenty, kolko max/min je komponent na n vrcholoch  
1b) def potencna mnozina, kedy ma neparny pocet prvkov  
1c) def bipartitny graf na m,n, kedy ma neparny pocet hran  
2) farbenie 5 farbami  
3) dokaz, ze v orientovanom 2suv grafe je vzdy cesta medzi 2 vrcholmi, pouzi lemmu o usiach  
4) cislo je bezstvorcove, ak nema medzi delitelmi 2.mocninu. mas cisla 1-120, kolko z nich je bezstv? pouzi PIE  
  
dufam ze pomoze
<{/ForumPost}>

<{ForumPost(poster="nardew", timestamp=2007-01-14 18:04:09)}>

 > Kudo wrote:5.důkaz věty o 4 barvách pro graf bez K_3

mozem vediet co je to za dokaz, lebo k farebnosti grafov sme robili len dokaz vety o piatich farbach, ale na nic taketo si nespominam.
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-01-14 20:20:29)}>
no ten dokaz sme nerobili ten mas spravit priblizne navod : Mat. indukcia :  je ze dokazes ze existuje vrxol stupne max. 3 z /E/<=2/V/-4  odoberies vrxol a podla induk. predpokladu a zafarbis 3 farbami a potom prides ten a zafarbis 4 farbou. Asi tak to mi pisal kamos ja som to tiez presne nevedel
<{/ForumPost}>

<{ForumPost(poster="nardew", timestamp=2007-01-14 23:22:04)}>
diky, vdaka tomu hintu s vrcholom stupna <= 3 je to uz easy potom
<{/ForumPost}>

<{ForumPost(poster="tk", timestamp=2007-01-18 18:28:30)}>
Jo, v zadání přímo bylo napsaný něco jako: Využijte toho, že má graf "dost málo" hran a tudíž vrchol "dostatečně malého" stupně.   
Takže bez problémů.
<{/ForumPost}>