Skuska 3.6.2008

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.

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

Nevite nekdo nahodou tu vytvorujici funkci?

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 :))

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?

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

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

Him wrote: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?

Opravil jsem svuj prispevek, zkus kouknout tam.. idea je asi jasna.. nestiham, tak jsem to nepsal prilis peclive O:-)

Diky, ja uz to pak taky pochopil - dlouho jsem tam totiz nevidel tu pravidelnost :)