Pomoc s příkladem

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

Pomoc s příkladem

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

Ahoj, netušíte někdo jak se počíta následující příklad ? Lámu si s tím hlavu už půl dne, a k žádnýmu výsledku sem nedošel :(

Uvažujme síť tvaru hyperkrychle Qn s vrcholy {0,1}^n, kde mezi vrcholy u,v vede hrana, pokud v vznikne z u změnou jedné nuly na jedničku. Kapacita (u,v) je definována jako:

c(u,v) = (1 + | n - 2*k | ) / ((n-1) nad k)

přičemž k je počet jedniček vrcholu u. Určete veliksot maximálního toku z vrcholu (0,...,0) do (1,...,1).

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

Re: Pomoc s příkladem

Příspěvek od Him »

Jedine co se blizi tomu tvemu prikladu, co jsem kde videl je zde: http://labts.troja.mff.cuni.cz/~machl5b ... ons_11.pdf

Snad to nejak pomuze
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 ;)
ondr4
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 31. 5. 2009 11:17
Typ studia: Informatika Bc.

Re: Pomoc s příkladem

Příspěvek od ondr4 »

Ahoj,
nedavno jsem resil skoro stejnou ulohu. Rozdil byl v "kapacitovem vzorci". Resil jsem to tak, ze si vezmu graf te n-dimenzionalni krychle a upravim jej. Na zacatku bude zdroj. Vsechny vrcholy, ktere jsou se Z spojene jednou hranou oznacim jako prvni vrstvu. Vrcholy, ktere jeste nemam oznacene a jsou spojene s 1. vrstvou jednou hranou, oznacim jako druha vrsva, atp. Pak si vypocitam jak velky je soucet kapacit mezi jednotlivymi vrstvami. Z kazdeho vrcholu ve vrstve vede (n-k) hran (pocet nul u vrcholu) a ve vrstve je (n nad k) vrcholu. Timhle vynasobim "kapacitovy vzorec" a pokud mas stesti neco se pokrati (ja mel :-) ) a vyjde neco z ceho muzes odvodit, mezi kterymi vrstvami je soucet kapacit hran nejmensi...a to je hledany maximalni tok.
Doufam, ze ti to pomuze ;-)
Návštěvník

Re: Pomoc s příkladem

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

Diky moc, pred chvilej sem se dopracoval k tomu reseni jak tady popisujes ty sice trochu oklikou ale vysledek je stejnej :)
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“