dnes to bolo trochu odlisne od tych predoslych Kratochvilovskych skusok - boli len 4 otazky a vacsmi teoreticke, menej pocitacie, no i tak si myslim ze pomerne jednoduche (teda tie dnesne). A navyse uz nebola anketa, ze ktora veta naj..(smiesnejsia).. skoda
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.
2. Dokazte nebo vyvratte kazde z nasledujicich tvrzeni:
(a) Ma-li graf HK, potom jeho vrcholova souvislost je alespon 2.
(b) Ma-li graf dve navzajem hranove disjunktne HK, potom je 3-souvisly.
(c) Ma-li graf vsechny stupne sude a vetsi nez 2, potom ma HK
3. Urcete maximalni tok v siti o 8 vrcholech (z nichz jeden je zdroj a jeden je stok), pricemz z kazdeho vrcholu do kazdeho jineho vrcholu vede orientovana hrana majici kapacitu 12. Odpoved zduvodnete!
4. Zformulujte a dokazte Hallovu vetu.
Hodnotenie: kazdy priklad za 6 bodov
19.5 - 24 ...1
16 - 19 ...2
12.5 - 15.5 ...3
(priblizne, a myslim ze este nejaka hranica na ustne doskusanie)
Moje pozorovania: ked je graf k-suvisly, tak defaultne sa mysli vrcholovo (napriek tomu, ze niekde to bolo napisane, a niekde nie). V 3. priklade sa mysli obojstranna orientacia, teda {x,y} -> (x,y),(y,x)
dnes to bolo trochu odlisne od tych predoslych Kratochvilovskych skusok - boli len 4 otazky a vacsmi teoreticke, menej pocitacie, no i tak si myslim ze pomerne jednoduche (teda tie dnesne). A navyse uz nebola anketa, ze ktora veta naj..(smiesnejsia).. skoda :)
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.
2. Dokazte nebo vyvratte kazde z nasledujicich tvrzeni:
(a) Ma-li graf HK, potom jeho vrcholova souvislost je alespon 2.
(b) Ma-li graf dve navzajem hranove disjunktne HK, potom je 3-souvisly.
(c) Ma-li graf vsechny stupne sude a vetsi nez 2, potom ma HK
3. Urcete maximalni tok v siti o 8 vrcholech (z nichz jeden je zdroj a jeden je stok), pricemz z kazdeho vrcholu do kazdeho jineho vrcholu vede orientovana hrana majici kapacitu 12. Odpoved zduvodnete!
4. Zformulujte a dokazte Hallovu vetu.
Hodnotenie: kazdy priklad za 6 bodov
19.5 - 24 ...1
16 - 19 ...2
12.5 - 15.5 ...3
(priblizne, a myslim ze este nejaka hranica na ustne doskusanie)
Moje pozorovania: ked je graf k-suvisly, tak defaultne sa mysli vrcholovo (napriek tomu, ze niekde to bolo napisane, a niekde nie). V 3. priklade sa mysli obojstranna orientacia, teda {x,y} -> (x,y),(y,x)