skuska 15.05.2008

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.
Uživatelský avatar
nardew
Matfyz(ák|ačka) level II
Příspěvky: 59
Registrován: 2. 11. 2006 10:15
Typ studia: Informatika Bc.
Bydliště: Otava - Jizni Mesto

skuska 15.05.2008

Příspěvek od nardew »

tak je tu zadanie z predterminu: bolo to dost odlisne od tych z predoslych rokov, v prvom rade co do poctu prikladov tak aj zlozenia prikladov. ani jeden som tu zatial nevidel. neviem ci to bolo len tym predterminom alebo to bude tak bezat aj nadalej. no, k veci:

1.) spocitat pocet kostier grafu, ktory vyzeral ako trojuholnik a vo vnutri bol v nom zo strednych priecok vytvoreny dalsi trojuholnik. druha skupina mala nejaky iny. bol to jediny priklad, ktory sa lisil medzi skupinami

2.) rozhodnut, ktore z nasledujucich mnozinovych systemov maju SRR
a.) M1 = {a, b, d}, M2 = {a, c}, M3 = {b, c}, M4 = {b, d}
b.) M1 = {a, c}, M2 = {a, c}, M3 = {b, c}, M4 = {a, b}
c.) M1 = {a, b}, M2 = {a, e}, M3 = {b, c}, M4 = {a, b, d}, M5 = {a, c}, M6 = {b, e, f}, M7 = {a, b, c}

3.) nasledujuca mapka znazornuje deltu rieky Mgwebwe na ostrove Papua Nova Guinea. Kolik stavidel je potreba a staci postavit, aby bylo mozno zamezit pristupu zralokov z mora do vnutrozemneho jazera? (Stavidla je mozno stavet jen na rovnych usecich rieky, nikoli v miestach, kde sa rieka vetvi). Odpoved zdovodnite. no a podtym bola zobrazena mala mapka s riecnou sietou. proste hladanie maximalneho toku

4.) existuju 3 navzajom ortogonalni latinske stvorce radu 5? pokud si myslite, ze ano, sestrojte takove 3 ctverce. pokud si myslite ze nikoliv, dokazte sve tvrzeni.

Znasledujucich troch prikladov staci vyriesit dva:
5.) Dokazte nasledujuce tvrdenia:
a.) Pokud je G 3-regularni graf obsahujici Ham. k., pak lze jeho hrany obarvit 3 barvami tak, ze ziadne dve hrany stejne barvy nemaji spolocny vrchol
b.) Je-li G n-regularny graf na 2n vrcholoch, pak G obsahuje perfectne parovanie

6.) Dokazte, ze mnozinovy system sestavajuci z primek nejake konecne projektivni roviny ma vzdy system ruznych reprezentantov.

7.) Graf se nazyva vonkajsie rovinny, pokud ho lze nakreslit v rovine bez krizeni hran tak, ze vsechny jeho vrcholy lezi na hranici vonkajsej steny. Dokazte, ze pokud graf neobsahuje deleni grafu K4 a K2, 3 jako podgraf, pak je vonakjsie rovinny.

A TERAZ POZOR!!
8.) Napiste vetu z prednasky (nebo skript), ktera sa vam nejvice libila. A napiste proc.

co sa tyka bodovania, tak prve 4 pocetne boli po 5 bodov, zvysne 3 dokazove po 10.
stupnica (tymi vrchnymi hranicami som si nie isty):
40 - 33 jeden
32 - 23 dva
22 - 17 tri
16 - 13 ustne

inak kedze to bol predtermin, tak kratochvil tym co mali stvorky termin nezaratal.
inak vyhodnocovanie bolo celkom zaujimave, zvlast vyhlasovanie priemerneho cisla poctu kostier prveho prikladu. rozne vysledky sa pohybovali od -1000 do 500 a takmer uplne kazdy mal iny vysledok :)

to je na dnes odo mna vsetko, good luck do dalsich kol
lickra
Matfyz(ák|ačka) level I
Příspěvky: 21
Registrován: 13. 6. 2006 22:24

Re: skuska 15.05.2008

Příspěvek od lickra »

Kratochvil 4 nezapisoval ani loni :-) nejen na predterminech
Medved_

Re: skuska 15.05.2008

Příspěvek od Medved_ »

Jak vypada ta ustni? Kdyz treba pisemku napisete na dvojku, ale pak chcete bojovat o jednicku... Co tak muzu cekat za dukaz? Pta se treba i na ty dlouhe dukazy typu Kuratowskeho, Hallova, nebo Mersenova veta?
hardwire2
Matfyz(ák|ačka) level I
Příspěvky: 24
Registrován: 5. 1. 2008 19:57
Typ studia: Informatika Bc.

Re: skuska 15.05.2008

Příspěvek od hardwire2 »

Jak na 4ku? Slo by to pres KPR tak, ze bych ukazal, ze nejdou sestrojit 4 ctverce radu 5 tak, ze budou navzajem ortogonalni? Ani 3 ctverce radu 4? Nejak nevidim, ze z toho plyne, ze nejdou sestrojit 3 navzajem ortogonalni ctverce radu 5.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: skuska 15.05.2008

Příspěvek od hippies »

Medved_ píše:Jak vypada ta ustni? Kdyz treba pisemku napisete na dvojku, ale pak chcete bojovat o jednicku... Co tak muzu cekat za dukaz? Pta se treba i na ty dlouhe dukazy typu Kuratowskeho, Hallova, nebo Mersenova veta?
Ano, i ty muzes cekat :twisted:
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Medved_

Re: skuska 15.05.2008

Příspěvek od Medved_ »

hippies píše:Ano, i ty muzes cekat :twisted:
Tak to je fajn, protoze ty dukazy jsou moc hezke, ale sam se clovek nedokope se je jen tak pro nic za nic ucit :lol:
Medved_

Re: skuska 15.05.2008

Příspěvek od Medved_ »

Podle me KPR radu 5 existuje, protoze protoze existuje konecne teleso s n prvky (napr. Z5). Takze ted vime, ze existuji i 4 navzajem ortogonalni latinske ctverce radu 5. No a ted uz to proste musis nakreslit, to asi nebude uplna pohoda, ale pocitam ze za +- 15 minut to vymyslis.
hardwire2 píše:Jak na 4ku? Slo by to pres KPR tak, ze bych ukazal, ze nejdou sestrojit 4 ctverce radu 5 tak, ze budou navzajem ortogonalni? Ani 3 ctverce radu 4? Nejak nevidim, ze z toho plyne, ze nejdou sestrojit 3 navzajem ortogonalni ctverce radu 5.
Uživatelský avatar
nardew
Matfyz(ák|ačka) level II
Příspěvky: 59
Registrován: 2. 11. 2006 10:15
Typ studia: Informatika Bc.
Bydliště: Otava - Jizni Mesto

Re: skuska 15.05.2008

Příspěvek od nardew »

hardwire2 píše:Nejak nevidim, ze z toho plyne, ze nejdou sestrojit 3 navzajem ortogonalni ctverce radu 5.
vidis velmi spravne, lebo tie stvorce existuju :)

(existuje n-1 lat. stvorcov radu n prave vtedy ked existuje KPR radu n. 5 bolo prvocislo, cize KPR existovala a teda aj tie stvorce. stacilo ich len sikovne napisat)
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“