Skuska 17.6 Valtr
-
- Matfyz(ák|ačka) level I
- Příspěvky: 10
- Registrován: 15. 6. 2005 13:36
- Typ studia: Informatika Bc.
- Bydliště: poprad
- Kontaktovat uživatele:
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)
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)
Re: Skuska 17.6 Valtr
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ů...
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ů...
Re: Skuska 17.6 Valtr
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á..
(b) Ma-li graf dve navzajem hranove disjunktne HK, potom je 3-souvisly.
pořád mi to odolává..
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
-
- Supermatfyz(ák|ačka)
- Příspěvky: 403
- Registrován: 11. 11. 2006 14:10
- Typ studia: Informatika Mgr.
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Skuska 17.6 Valtr
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?Him píše: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á..
Osiris
Re: Skuska 17.6 Valtr
Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.
Diky
Diky
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Skuska 17.6 Valtr
Mne to unika i tak, jak si to, prosim te, nakonec vyresil?Him píše:Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.
Diky
Re: Skuska 17.6 Valtr
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.Guest píše:Mne to unika i tak, jak si to, prosim te, nakonec vyresil?Him píše:Osiris: pokud neni definovano, jaka je to souvislost, tak se mysli, tusim, vrcholova. Hranova je jednoducha.
Diky
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
-
- Matfyz(ák|ačka) level I
- Příspěvky: 25
- Registrován: 3. 2. 2008 14:36
- Typ studia: Informatika Bc.
- Bydliště: Praha
Re: Skuska 17.6 Valtr
Resene je to take tady:
http://mff.lokiware.info/KombinatorikaA ... 008?v=1dlb
http://mff.lokiware.info/KombinatorikaA ... 008?v=1dlb
Re: Skuska 17.6 Valtr
Diky!
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW