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