Zkouška 26.1.2007 - Král'

MarPol
Matfyz(ák|ačka) level I
Příspěvky: 28
Registrován: 11. 10. 2006 11:01

Zkouška 26.1.2007 - Král'

Příspěvek od MarPol »

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?
Naposledy upravil(a) MarPol dne 28. 1. 2007 13:48, celkem upraveno 1 x.
kubiq
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 23. 1. 2007 17:14
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Příspěvek od kubiq »

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

moje obludene :D

Příspěvek od yderf »

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 ;-)
Uživatelský avatar
MacJariel
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 23. 1. 2007 15:07

Příspěvek od MacJariel »

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]
Návštěvník

Re: Zkouška 26.1.2007 - Král'

Příspěvek od Návštěvník »

MarPol píše: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?
Návštěvník

Re: Zkouška 26.1.2007 - Král'

Příspěvek od Návštěvník »

del
Odpovědět

Zpět na „2006“