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.
Pomoc s příkladem
Re: Pomoc s příkladem
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
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
-
- 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
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
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
Re: Pomoc s příkladem
Diky moc, pred chvilej sem se dopracoval k tomu reseni jak tady popisujes ty sice trochu oklikou ale vysledek je stejnej