# Skuska 17.6 Valtr

<{ForumPost(poster="misiak7", timestamp=2008-06-17 19:27:46)}>
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)
<{/ForumPost}>

<{ForumPost(poster="Flavius Vespasianus", timestamp=2008-06-17 19:50:21)}>
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ů...
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-05-31 13:25:52)}>
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á..
<{/ForumPost}>

<{ForumPost(poster="Osiris", timestamp=2009-05-31 14:02:02)}>

 > 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?
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-05-31 14:03:46)}>
Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.   
  
Diky
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-05-31 16:25:04)}>

 > 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?
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-05-31 16:30:59)}>

 > 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.
<{/ForumPost}>

<{ForumPost(poster="dobry_den", timestamp=2009-05-31 16:35:08)}>
Resene je to take tady:  
[http://mff.lokiware.info/KombinatorikaA ... 008?v=1dlb](http://mff.lokiware.info/KombinatorikaAGrafy/ZkouskaLS2008?v=1dlb)
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-05-31 16:37:21)}>
Diky!
<{/ForumPost}>