Zkouška 26.1.2007 - Král'

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₃.

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?

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.

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 ;-)

1. Definujte pojem 2-souvisleho grafu. Rozhodnete, kdy je uplny bipartitni graf K_m,n 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₆ takovych, ze neobsahuji zadny izolovany vrchol? (C₆ 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]

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₃.
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?

del