Skuska 17.6 Valtr

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
misiak7
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

Příspěvek od misiak7 »

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)
Flavius Vespasianus

Re: Skuska 17.6 Valtr

Příspěvek od Flavius Vespasianus »

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ů...
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 17.6 Valtr

Příspěvek od Him »

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á..
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 ;)
Osiris
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

Příspěvek od Osiris »

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á..
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
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 17.6 Valtr

Příspěvek od Him »

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 ;)
Návštěvník

Re: Skuska 17.6 Valtr

Příspěvek od Návštěvník »

Him píše: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?
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 17.6 Valtr

Příspěvek od Him »

Guest píše:
Him píše: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.
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 ;)
dobry_den
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

Příspěvek od dobry_den »

Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 17.6 Valtr

Příspěvek od Him »

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 ;)
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“