od MJS » 24. 6. 2009 18:22
1. Dokazte nebo vyvratte: Necht T je strom na alespon 3 vrcholech nemajici zadny vrchol stupne 2 a necht C je kruznice prochazejici vsemi listy stromu T (a nemajici zadny dalsi vrchol). Potom pridanim hran kruznice C ke stromu T vznikne 3-souvisly graf.
Pry to jde nejak jakkoliv ukopat.
2. Dokazte nebo vyvratte:
a) Ma-li G HK, potom jeho vrch. souvislost je >=2.
b) Ma-li G dve navzajem hran. disj. HK, potom je 3-souvisly.
c) Ma-li G vsechny stupne sude a > nez 2, potom ma HK.
a) Ano, jednoduche, b) ne, staci najit protipriklad c) ne: staci napr, vzit dvakrat K4,4, coz je nesouvisle a tudiz nema HK
3. Max. tok. na oboustranne zorientovanem K_8 s kapacitami 12.
Jasne = 84
4. Hallova veta + dukaz.
Vsechno za 6 bodu, body ? : >17 >14 >11
[b]1.[/b] Dokazte nebo vyvratte: [i]Necht T je strom na alespon 3 vrcholech nemajici zadny vrchol stupne 2 a necht C je kruznice prochazejici vsemi listy stromu T (a nemajici zadny dalsi vrchol). Potom pridanim hran kruznice C ke stromu T vznikne 3-souvisly graf.[/i]
Pry to jde nejak jakkoliv ukopat.
[b]2.[/b] Dokazte nebo vyvratte:
a) Ma-li G HK, potom jeho vrch. souvislost je >=2.
b) Ma-li G dve navzajem hran. disj. HK, potom je 3-souvisly.
c) Ma-li G vsechny stupne sude a > nez 2, potom ma HK.
a) Ano, jednoduche, b) ne, staci najit protipriklad c) ne: staci napr, vzit dvakrat K4,4, coz je nesouvisle a tudiz nema HK
[b]3.[/b] Max. tok. na oboustranne zorientovanem K_8 s kapacitami 12.
Jasne = 84
[b]4.[/b] Hallova veta + dukaz.
Vsechno za 6 bodu, body ? : >17 >14 >11