# Zkouška 26.1.2007 - Král'

<{ForumPost(poster="MarPol", timestamp=2007-01-26 16:59:20)}>
1. Definujte, kdy je relace ekvivalencí. Kolik tříd ekvivalence mají   následující tři ekvivalence definované na X={1,2,..20}  
   (a) xRy <=> x-y je dělitelné 5  
   (b) xRy <=> x=y nebo |x-y|=10  
   (c) xRy <=> x*y>0  
2. Zformulujte a dokažte větu o maximálním počtu hran v n-vrcholovém grafu bez K<sub>3</sub>.  
3. Pro každé k>=1 určete nejmenší možný počet listů ve stromu s dvěma vrcholy stupně k. (Zdůvodněte)  
4. Kolik je vzájemně neizomorfních grafů s 8 vrcholy, jejichž každý vrchol má stupeň 0 nebo 2 nebo 7?
<{/ForumPost}>

<{ForumPost(poster="kubiq", timestamp=2007-01-26 17:46:05)}>
Ja sem mel  
  
Napiste definici prosteho zobrazeni. Kolik je prostych zobrazeni z X={1,3} do Y={2,4,6}? (Zduvodnete)  
  
Zformulujte a dokazte vetu o 5 barvach.  
  
Jaky je maximalni pocet sten rovinneho nakresleni grafu s 80 vrcholy? (Zduvodnete)  
  
Odvodte vzorec pro pocet permutaci mnoziny {1,2,..,n} s prave jednim pevnym bodem.
<{/ForumPost}>

<{ForumPost(poster="yderf", timestamp=2007-01-27 00:03:10)}>
1. definujte pojem farebnost grafu a rozhodnite o farebnosti K_5, K_3,3  
2. PIE, sformulujte a dokaz  
3. {citujem} necht pro n>=1 znaci symbol G_n graf, jehoz vrcholy jsou vsechny slova delky n nad triprvkovou abecedou {a,b,c} (napr. pre n=5 jeden z vrcholo je aacbb) a dva vrcholy tvori hranu, prave kdyz se odpovidejici slova lisi na jedinem miste a jinak se shoduji. rozhodnette, pro ktere n=1,2,.. se graf G_n da nakreslit jednim uzavretym tahem bez opakovani hran. zduvodnete.  
4. pocet kostier uplneho bipratitneho grafu K_2,n  
  
bolo to celkom v pohode zadanie, trojka vyzera skaredo, ale je velmi lahka ;-)
<{/ForumPost}>

<{ForumPost(poster="MacJariel", timestamp=2007-01-27 15:40:12)}>
1. Definujte pojem 2-souvisleho grafu. Rozhodnete, kdy je uplny bipartitni graf *K<sub>m,n</sub>* 2-souvisly. (Zduvodnete.)  
2. Zformulujte princip inkluze a exkluze a dokazte ho. Uvedte presnou formulaci ("Pro kazde n >= 1 a pro kazdych...").  
3. Kolik je vsech neizomorfnich podgrafu grafu C<sub>6</sub> takovych, ze neobsahuji zadny izolovany vrchol? (C<sub>6</sub> znamena kruznici na 6 vrcholech) Jak receno, dva izomorfni podgrafy nepovazujeme za ruzne a pocitame je za jeden.  
4. Urcete pocet vzajemne neizomorfnich grafu na 5 vrcholech, ktere jako podgraf neobsahuji cestu delky 3. Odpoved zduvodnete.\[/i]
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-01-28 13:47:00)}>

 > MarPol wrote:1. Definujte, kdy je relace ekvivalencí. Kolik tříd ekvivalence mají   následující tři ekvivalence definované na X={1,2,..20}  
 >    (a) xRy <=> x-y je dělitelné 5  
 >    (b) xRy <=> x=y nebo |x-y|=10  
 >    (c) xRy <=> x*y>0  
 > 2. Zformulujte a dokažte větu o maximálním počtu hran v n-vrcholovém grafu bez K<sub>3</sub>.  
 > 3. Pro každé k>=1 určete nejmenší možný počet listů ve stromu s dvěma vrcholy stupně k. (Zdůvodněte)  
 > 4. Kolik je vzájemně neizomorfních grafů s 8 vrcholy, jejichž každý vrchol má stupeň 0 nebo 2 nebo 7?

<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-01-28 13:47:54)}>
del
<{/ForumPost}>