Skuska 17.6 Valtr

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)

Body byly myslím
20-24
16-19.5
12-15.5
8.5-11.5 (možnost opravy na ústním)

Jinak souhlasím, že to nic tak těžkého nebylo a hlavně opravování bylo docela mírné - chyběla mi půlka (prostřední :)) důkazu té Hallovy věty a měl jsem to za 6 bodů...

Jak se pls řeší příklad:

(b) Ma-li graf dve navzajem hranove disjunktne HK, potom je 3-souvisly.

pořád mi to odolává..

Him wrote:Jak se pls řeší příklad:

(b) Ma-li graf dve navzajem hranove disjunktne HK, potom je 3-souvisly.

pořád mi to odolává..

Pokud má dvě hranově disujunktní HK, pak mezi každými dvěma vrcholy grafu vedou 4 hranově disjunktní cesty => je hranově 4-souvislý, Jde ti o vrcholovou, nebo hranovou k-souvislost?

Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.

Diky

Him wrote:Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.

Diky

Mne to unika i tak, jak si to, prosim te, nakonec vyresil?

Guest wrote:

Him wrote:Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.

Diky

Mne to unika i tak, jak si to, prosim te, nakonec vyresil?

Vrcholovou jsem bohuzel nevyresil. Hranova je jednoducha - pouzijes Ford-Fulkersonovu vetu (zhruba receno: Graf G je hranove k-souvisly <=> mezi kazdymi dvema ruznymi vrcholy vede >= k hranove disjunktnich cest.) a v tom grafu mas dve hamiltonovske kruznice, takze dve hranove disjunktni cesty mas v ramci jedne HK (jedna cesta povede po smeru hodinovych rucicek a druha proti, kdyz si vrcholy HK nakreslis jako kruznici) a dalsi dve v ramci druhe HK. Takze graf je hranove 4-souvisly.

Resene je to take tady:
http://mff.lokiware.info/KombinatorikaA ... 008?v=1dlb

Diky!