# Skuska 3.6.2008 <{ForumPost(poster="Vinc", timestamp=2008-06-03 15:56:57)}> 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. <{/ForumPost}> <{ForumPost(poster="huuuuu", timestamp=2008-06-03 18:57:02)}> 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 <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2009-05-29 20:59:39)}> Nevite nekdo nahodou tu vytvorujici funkci? <{/ForumPost}> <{ForumPost(poster="Him", timestamp=2009-05-29 21:46:32)}> Guest: **Tahacek:** [http://kam.mff.cuni.cz/~eva/kg/gf.pdf](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 :)) <{/ForumPost}> <{ForumPost(poster="cermi", timestamp=2009-05-29 22:25:23)}> > 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? <{/ForumPost}> <{ForumPost(poster="Him", timestamp=2009-05-30 00:11:57)}> Dle [Medveda](http://www.forum.matfyz.info/viewtopic.php?f=240&t=4424) 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 <{/ForumPost}> <{ForumPost(poster="Him", timestamp=2009-05-31 08:58:21)}> 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 <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2009-05-31 17:01:53)}> > Him wrote:Guest: > > **Tahacek:** [http://kam.mff.cuni.cz/~eva/kg/gf.pdf](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? <{/ForumPost}> <{ForumPost(poster="Him", timestamp=2009-05-31 17:12:52)}> Opravil jsem svuj prispevek, zkus kouknout tam.. idea je asi jasna.. nestiham, tak jsem to nepsal prilis peclive O:-) <{/ForumPost}> <{ForumPost(poster="Anonymous", timestamp=2009-05-31 17:28:53)}> Diky, ja uz to pak taky pochopil - dlouho jsem tam totiz nevidel tu pravidelnost :) <{/ForumPost}>