Fórum studentů MFF UK

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

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

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

Snad to nejak pomuze

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.