From cfd44263953d4c33c5c11552cb70c6ab25041983 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 4 Nov 2011 22:26:24 +0100 Subject: [PATCH] Goldberg: Par drobnosti, brzy prepracuji vyrazneji --- 4-goldberg/4-goldberg.tex | 25 ++++++++++++++++++------- 1 file changed, 18 insertions(+), 7 deletions(-) diff --git a/4-goldberg/4-goldberg.tex b/4-goldberg/4-goldberg.tex index 70544d4..f091177 100644 --- a/4-goldberg/4-goldberg.tex +++ b/4-goldberg/4-goldberg.tex @@ -1,17 +1,28 @@ \input lecnotes.tex -\prednaska{3}{Goldbergùv algoritmus}{(zapsala Markéta Popelová)} +\prednaska{4}{Goldbergùv algoritmus}{} -Pøedstavíme si~nový algoritmus pro~hledání maximálního toku v~síti, který se~uká¾e být stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(MN^{2})$) a~po~nìkolika vylep¹eních bude i~lep¹í. Nejdøíve si~pøipomeòme definice, které budeme potøebovat: +Pøedstavíme si~nový algoritmus pro~hledání maximálního toku v~síti, který +se~uká¾e být stejnì dobrý jako {\I Dinicùv algoritmus} ($\O(MN^{2})$) +a~po~nìkolika vylep¹eních bude i~lep¹í. Nejdøíve si~pøipomeòme definice, které +budeme potøebovat: -\s{Definice:} Mìjme sí» $S=(V,E,z,s,c)$, tok~$f$ a~libovolný vrchol~$v$. Pak $f^{\Delta}(v)$ nazýváme {\I pøebytek} ve~vrcholu~$v$ a~definujeme ho takto: $$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$ Pøebytek ve~vrcholu~$v$ je tedy souèet v¹eho, co do~vrcholu~$v$ pøiteèe, minus souèet v¹eho, co z~$v$ odteèe. +\s{Definice:} Mìjme sí» $S=(V,E,z,s,c)$, tok~$f$ a~libovolný vrchol~$v$. Pak +$f^{\Delta}(v)$ nazýváme {\I pøebytek} ve~vrcholu~$v$ a~definujeme ho takto: +$$f^{\Delta}(v):=\sum_{uv \in E}{f(uv)} - \sum_{vu \in E}{f(vu)}.$$ Pøebytek +ve~vrcholu~$v$ je tedy souèet v¹eho, co do~vrcholu~$v$ pøiteèe, minus souèet +v¹eho, co z~$v$ odteèe. -\s{Definice:} Dále pro~libovolnou hranu~$uv \in E$ definujeme její {\I rezervu} následovnì: -$$r(uv) = c(uv) - f(uv) + f(vu).$$ Rezerva hrany znaèí, co je¹tì je mo¾no po~této hranì poslat. +\s{Definice:} Dále pro~libovolnou hranu~$uv \in E$ definujeme její {\I rezervu} +následovnì: $$r(uv) = c(uv) - f(uv) + f(vu).$$ Rezerva hrany znaèí, co je¹tì je +mo¾no po~této hranì poslat. -\s{Poznámka:} Dále budeme oznaèovat písmenem~$N$ poèet vrcholù a~$M$ poèet hran, tedy~$N = \vert V \vert$ a~$M = \vert E \vert$. +\s{Poznámka:} Dále budeme oznaèovat písmenem~$N$ poèet vrcholù a~$M$ poèet +hran, tedy~$N = \vert V \vert$ a~$M = \vert E \vert$. -Goldbergùv algoritmus na~rozdíl od~Dinicova algoritmu zaèíná s~ohodnocením hran, které pravdìpodobnì není tokem (budeme ho nazývat {\I vlna}), a~postupnì ho zmen¹uje a¾ na~korektní tok. +Goldbergùv algoritmus na~rozdíl od~Dinicova algoritmu zaèíná s~ohodnocením +hran, které pravdìpodobnì není tokem (budeme ho nazývat {\I vlna}), a~postupnì +ho zmen¹uje a¾ na~korektní tok. \s{Definice:} Funkce $f:E \rightarrow {\bb R}_{0}^{+}$ je {\I vlna} v~síti~$(V, E, z, s, c)$ tehdy, kdy¾ jsou splnìny následující dvì podmínky: \numlist\ndotted -- 2.39.2