From 74ac76ed70bc9adc7e3fbf40dcfa006241288478 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 15 Jan 2010 16:55:29 +0100 Subject: [PATCH] Drobne preklepy. --- 3-goldberg/3-goldberg.tex | 38 +++++++++++++++++++++----------------- 1 file changed, 21 insertions(+), 17 deletions(-) diff --git a/3-goldberg/3-goldberg.tex b/3-goldberg/3-goldberg.tex index 92cc877..6e528c9 100644 --- a/3-goldberg/3-goldberg.tex +++ b/3-goldberg/3-goldberg.tex @@ -114,7 +114,6 @@ Uka Proè je druhá svorka nezáporná, je zøejmé, nebo» tok na~hranì je v¾dy nezáporný a~souèet nezáporných èísel je nezáporné èíslo. Proto $\sum_{u \in A}{f^\Delta(u) \le 0}$. Zároveò v¹ak v~$A$ je aspoò jeden vrchol s~kladným pøebytkem, toti¾~$v$, proto v~$A$ musí být také vrchol se~záporným pøebytkem -- a~jediný takový je zdroj. Tím je dokázáno, ¾e $z \in A$, tedy ¾e vede nenasycená cesta z~vrcholu~$v$ do~zdroje. - \qed \s{Invariant V (Vý¹ka):} $\forall v \in V$ platí $h(v)\leq 2N$. @@ -175,29 +174,34 @@ D \s{Rozbor èasové slo¾itosti algoritmu:} \numlist\ndotted -\:Inicializace vý¹ek \dots $\O(1)$. -\:Inicializace vlny~$f$ \dots $\O(M)$. -\:Výbìr vrcholu~$u$ s~kladným pøebytkem -- vezmeme první vrchol v~$P$ \dots $\O(1)$. -\:Výbìr vrcholu~$v$, do~kterého vede z~$u$ hrana s~kladnou rezervou a~který je ní¾e ne¾~$u$ -- vezmeme první hranu z~$L(u)$ \dots $\O(1)$. +\:Inicializace vý¹ek \dots\ $\O(1)$. +\:Inicializace vlny~$f$ \dots\ $\O(M)$. +\:Výbìr vrcholu~$u$ s~kladným pøebytkem -- vezmeme první vrchol v~$P$ \dots\ $\O(1)$. +\:Výbìr vrcholu~$v$, do~kterého vede z~$u$ hrana s~kladnou rezervou a~který je ní¾e ne¾~$u$ -- vezmeme první hranu z~$L(u)$ \dots\ $\O(1)$. - Pøevedení pøebytku: \dots $\O(1)$. + Pøevedení pøebytku: \dots\ $\O(1)$. \itemize\idot - \:Nasycené pøevedení \dots $\O(1)$. + \:Nasycené pøevedení \dots\ $\O(1)$. \itemize\idot - \:Rezerva hrany~$uv$ klesne na~nulu $\Rightarrow$ hrana~$uv$ vypadne z~$L(u)$ \dots $\O(1)$. - \:Pøebytek vrcholu~$v$ se~zvý¹í $\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots $\O(1)$. - \:Pøebytek vrcholu~$u$ mo¾ná také klesne na~nulu $\Rightarrow$ pak by vrchol~$u$ vypadnul z~$P$ \dots $\O(1)$. + \:Rezerva hrany~$uv$ klesne na~nulu $\Rightarrow$ hrana~$uv$ vypadne z~$L(u)$ \dots\ $\O(1)$. + \:Pøebytek vrcholu~$v$ se~zvý¹í $\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots\ $\O(1)$. + \:Pøebytek vrcholu~$u$ mo¾ná také klesne na~nulu $\Rightarrow$ pak by vrchol~$u$ vypadnul z~$P$ \dots\ $\O(1)$. \endlist - \:Nenasycené pøevedení \dots $\O(1)$. + \:Nenasycené pøevedení \dots\ $\O(1)$. \itemize\idot - \:Rezerva hrany~$uv$ zùstane nezáporná $\Rightarrow$ hrana~$uv$ zùstane v~$L(u)$ \dots $\O(1)$. + \:Rezerva hrany~$uv$ zùstane nezáporná $\Rightarrow$ hrana~$uv$ zùstane v~$L(u)$ \dots\ $\O(1)$. \:Vynuluje se~pøebytek vrcholu~$u$~$\Rightarrow$ vrchol $u$ vypadne z~$P$ \dots~$\O(1)$. - \:Pøebytek vrcholu~$v$ se~zvý¹í~$\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots $\O(1)$. + \:Pøebytek vrcholu~$v$ se~zvý¹í~$\Rightarrow$ pokud je¹tì nebyl v~seznamu~$P$, tak se~tam pøidá \dots\ $\O(1)$. \endlist \endlist \:Zvednutí vrcholu~$u$ \dots $\O(N)$. - Musíme obejít v¹echny hrany do~$u$ a~z~$u$, kterých je nejvý¹e~$2N-2$, porovnat vý¹ky a~pøípadnì tyto hrany~$uv$ odebrat ze~seznamu~$L(u)$ resp. pøidat do~$L(v)$. Abychom pro~odebrání hrany~$uv$ ze~seznamu~$L(u)$ nemuseli procházet celý seznam, budeme si~$\forall v \in V$ pamatovat je¹tì $L^{-1}(v) := $ seznam ukazatelù na~hrany~$uv$ v~seznamech~$L(u)$. +Musíme obejít v¹echny hrany do~$u$ a~z~$u$, kterých je nejvý¹e~$2N-2$, porovnat +vý¹ky a~pøípadnì tyto hrany~$uv$ odebrat ze~seznamu~$L(v)$ resp. pøidat +do~$L(u)$. Abychom pro~odebrání hrany~$uv$ ze~seznamu~$L(v)$ nemuseli procházet +celý seznam, budeme si~$\forall u \in V$ pamatovat je¹tì $L^{-1}(u) := $ seznam +ukazatelù na~hrany~$uv$ v~seznamech~$L(v)$. + \endlist Vidíme, ¾e ka¾dé zvednutí je sice drahé, ale je jich zase pomìrnì málo. Naopak pøevádìní pøebytkù je èastá operace, tak¾e je výhodné, ¾e trvá konstantní èas. @@ -205,9 +209,9 @@ Vid \s{Shrnutí:} \itemize\ibull -\:V¹ech zvednutí je $\O(N^2)$ (viz lemma Z), ka¾dé trvá $\O(N) \dots \O(N^3).$ -\:V¹ech nasycených pøevedení je $\O(NM)$ (viz lemma S), ka¾dé trvá $\O(1) \dots \O(NM).$ -\:V¹ech nenasycených pøevedení je $\O(N^2M)$ (viz lemma N), ka¾dé trvá $\O(1) \dots \O(N^2M).$ +\:V¹ech zvednutí je $\O(N^2)$ (viz lemma Z), ka¾dé trvá $\O(N)$ \dots\ $\O(N^3).$ +\:V¹ech nasycených pøevedení je $\O(NM)$ (viz lemma S), ka¾dé trvá $\O(1)$ \dots\ $\O(NM).$ +\:V¹ech nenasycených pøevedení je $\O(N^2M)$ (viz lemma N), ka¾dé trvá $\O(1)$ \dots\ $\O(N^2M).$ \endlist Dohromady má tedy Goldbergùv algoritmus èasovou slo¾itost $\O(N^2M)$. Vidíme, ¾e u¾ v~tomto obecném pøípadì to není hor¹í ne¾ Dinicùv algoritmus. Pøí¹tì si~uká¾eme, ¾e mù¾e mít i~mnohem lep¹í. Nejdøíve ale zformulujme v¹echna dokázaná tvrzení do~následující vìty: -- 2.39.2