Skuska 3.6.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.

Skuska 3.6.2008

Příspěvekod Vinc » 3. 6. 2008 14:56

1. Urcte maximalnu nezavislu mnozinu v danom bipartitnom grafe

2. Urcte vytvarajucu funkciu pre postupnost (2, 1, 3, 2, 4, 3, 5, 4, ...)

3. Rozhodnite, pre ktore prirodzene cisla m, n obsahuje uplny bipartitny graf K_m,n Hamiltonovsku kruznicu

4. Urcte maximalny tok v danej sieti

5. Nech p >= 3 je prvocislo. Dokazte, ze existuje system (p^2) + 1 mnozin, z ktorych kazda ma velkost p a maju spolocny najviac jeden prvok, ktory nema SRR

6. Dokazte, ze v kazdom vrcholovo k-suvislom grafe lezi kazdych k vrcholov na spolocnej kruznici

7. Dokazte, ze v bipartitnom grafe, ktoreho vsetky vrcholy v jednej partite maju lichy stupen, prechadza kazdou hranou sudy pocet HK. Je pravda, ze i celkovy pocet HK je sudy?

8. Napiste vetu z prednasky, ktora Vam pripadala najprekvapivejsia a napiste preco.
Vinc
Matfyz(ák|ačka) level I
 
Příspěvky: 9
Registrován: 4. 11. 2006 22:29
Typ studia: Informatika Mgr.

Re: Skuska 3.6.2008

Příspěvekod huuuuu » 3. 6. 2008 17:57

1. Urcte maximalnu nezavislu mnozinu v danom bipartitnom grafe
~~pres max. tok
2. Urcte vytvarajucu funkciu pre postupnost (2, 1, 3, 2, 4, 3, 5, 4, ...)
~~snad ok
3. Rozhodnite, pre ktore prirodzene cisla m, n obsahuje uplny bipartitny graf K_m,n Hamiltonovsku kruznicu
~~ m = n, n >= 2, pak treba Lovaszova veta
4. Urcte maximalny tok v danej sieti
~~ obrazek...
5. Nech p >= 3 je prvocislo. Dokazte, ze existuje system (p^2) + 1 mnozin, z ktorych kazda ma velkost p a maju spolocny najviac jeden prvok, ktory nema SRR
~~ pres KPR
6. Dokazte, ze v kazdom vrcholovo k-suvislom grafe lezi kazdych k vrcholov na spolocnej kruznici
~~ indukci od k = 2, uzivani mengerovy vety, popripadne pridat trokovy vrchol ... no chce si to s tim pohrat, uz si nepamatuju presne
7. Dokazte, ze v bipartitnom grafe, ktoreho vsetky vrcholy v jednej partite maju lichy stupen, prechadza kazdou hranou sudy pocet HK. Je pravda, ze i celkovy pocet HK je sudy?
~~ lizatkove grafy, docela obtizne
huuuuu
 

Re: Skuska 3.6.2008

Příspěvekod Návštěvník » 29. 5. 2009 19:59

Nevite nekdo nahodou tu vytvorujici funkci?
Návštěvník
 

Re: Skuska 3.6.2008

Příspěvekod Him » 29. 5. 2009 20:46

Guest:

Tahacek: http://kam.mff.cuni.cz/~eva/kg/gf.pdf - tohle nam doporucoval cvicici

Nejak takto:

(1, 2, 3, 4, ...) - v tahaku
(1, 0, 2, 0, 3, 0, 4, ...) - 1/(1-x^2)^2
(0, 1, 0, 2, 0, 3, 0, 4, ...) - x/(1-x^2)^2
(0, 1, 0, 1, 0, 1, 0, 1, ...) - x/(1-x^2)

(0, 3, 0, 4, 0, 5, 0, 6, ...) - x/(1-x^2)^2 + 2x/(1-x^2)
(1, 3, 2, 4, 3, 5, 4, 6, ...) - 1/(1-x^2)^2 + x/(1-x^2)^2 + 2x/(1-x^2)

(0, 1, 3, 2, 4, 3, 5, 4, ...) .. vynasobeno x, x*( 1/(1-x^2)^2 + x/(1-x^2)^2 + 2x/(1-x^2) )

a ted k te vytvorujici funkci prictes dvojku:

2 + x*( 1/(1-x^2)^2 + x/(1-x^2)^2 + 2x/(1-x^2) ) ... to by melo byt vsechno

(zakaz lincovani za chyby od 21:46 :))
Naposledy upravil Him dne 31. 5. 2009 16:11, celkově upraveno 1
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 ;)
Him
Supermatfyz(ák|ačka)
 
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 3.6.2008

Příspěvekod cermi » 29. 5. 2009 21:25

1. Urcte maximalnu nezavislu mnozinu v danom bipartitnom grafe
~~pres max. tok


Jak se dělá tohle? Navíc na wikipedii píšou, že hledání maximální nezávislé množiny v grafu je NP úplný problém, což ale hledání maximálního toku není. Můžeš to nějak stručně objasnit prosím?
Čermi
Obrázek
cermi
Matfyz(ák|ačka) level I
 
Příspěvky: 15
Registrován: 31. 1. 2008 18:44
Typ studia: Informatika Bc.
Login do SIS: cermj7am

Re: Skuska 3.6.2008

Příspěvekod Him » 29. 5. 2009 23:11

Dle Medveda jde zapojit maximalni parovani. Maximalni parovani se v bipartitnim grafu najde jednoduse, staci udelat zdroj (s hranami k partite A) a stok (spojeny hranami k partite B) a vsechny hrany ohodnotit 1. A potom plati: #vrcholu - velikost max. toku = velikost max. nezavisle mnoziny

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

Re: Skuska 3.6.2008

Příspěvekod Him » 31. 5. 2009 07:58

Jak se řeší ten 5-tý příklad? Podle té nápovědy se má použít KPR. Takže když je p společná velikost množin, tak n = p - 1 je řád KPR. KPR má n^2 + n + 1 přímek / bodů, což když se přepíše pomocí p tak vyjde: p^2 - p + 1. V zadání je ale p^2 + 1 množin, takže mi jich ještě p chybí. Nevíte někdo, co s tím?

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

Re: Skuska 3.6.2008

Příspěvekod Návštěvník » 31. 5. 2009 16:01

Him píše:Guest:

Tahacek: http://kam.mff.cuni.cz/~eva/kg/gf.pdf - tohle nam doporucoval cvicici

Nejak takto:

(1, 3, 2, 4, 3, 5, 4, ...) - v tahaku


nevite nekdo, jak tuhle vetu z toho tahaku dostat?
Návštěvník
 

Re: Skuska 3.6.2008

Příspěvekod Him » 31. 5. 2009 16:12

Opravil jsem svuj prispevek, zkus kouknout tam.. idea je asi jasna.. nestiham, tak jsem to nepsal prilis peclive O:-)
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 ;)
Him
Supermatfyz(ák|ačka)
 
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Skuska 3.6.2008

Příspěvekod Návštěvník » 31. 5. 2009 16:28

Diky, ja uz to pak taky pochopil - dlouho jsem tam totiz nevidel tu pravidelnost :)
Návštěvník
 


Zpět na DMI011 Kombinatorika a grafy I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků