From a423a683b204c982f4ed604a2df3ec4d3f743da3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 24 Jan 2007 14:15:23 +0100 Subject: [PATCH] Stylisticka revize kapitoly o GHT. --- 4-ght/4-ght.tex | 67 ++++++++++++++++++++++++------------------------- 1 file changed, 33 insertions(+), 34 deletions(-) diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 2b26b1e..983c38f 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -1,5 +1,3 @@ -% Written by Milan Straka, 2006 - \def\li{\discretionary{-}{-}{-}li} \def\d{\delta} \def\st{$st$} @@ -32,19 +30,19 @@ pro n \h{Gomory-Hu Tree} \s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný ohodnocený graf $G=(V,E)$ -je strom $T=(V,F)$ takový,\nobreak{}\ \nobreak{}¾e $$\forall st \in F: \d(K_1)=\d(K_2)\hbox{ je minimální \st-øez, kde -$K_1$ a $K_2$ jsou komponenty $T\setminus st$}.$$ +je strom $T=(V,F)$ takový, ¾e pro ka¾dou hranu $st\in F$ platí: Oznaèíme-li $K_1$ a $K_2$ +komponenty lesa $T\setminus st$, je $\d(K_1)=\d(K_2)$ minimální \st-øez. [Pozor, $F$ nemusí být podmno¾ina pùvodních hran $E$.] \s{Dal¹í znaèení:} Pro $e\in F$ budeme øezem $\d(e)$ oznaèovat øez $\d(K_1)=\d(K_2)$ a $r(e)$ bude jeho kapacita. -\>K~èemu takový \GHT{} je (existuje-li)? To nám poví následující +\>K~èemu takový \GHT{} je (existuje-li)? To nám poví následující vìta: -\s{Vìta (o~vyu¾ití \GHT):} Buï $T=(V,F)$ \GHT{} pro graf $G=(V,E)$ a mìjme dva vrcholy $s$ a $t$. Dále +\s{Vìta (o~vyu¾ití \GHT):} Buï $T$ libovolný \GHT{} pro graf~$G$ a mìjme dva vrcholy $s$ a $t$. Dále nech» $P$ je cesta v~$T$ mezi vrcholy $s$ a $t$ a $e$ je hrana na cestì $P$ s~minimálním $r(e)$. -Pak $\d(e)$ je minimální \st-øez. +Pak $\d(e)$ je minimální \st-øez v~$G$. -\proof Nejprve si doká¾eme jedno drobné +\proof Nejprve si doká¾eme jedno drobné lemmátko: {\advance\leftskip by 2em\advance\rightskip by 2em \s{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e: @@ -54,8 +52,9 @@ $$r(x,z) \ge \min(r(x,y),r(y,z)).$$ \fig{4-ght-rez.eps}{\epsfxsize} -\noindent Vrchol $y$ musí být v~jedné z~komponent, BÚNO v~komponentì s~$x$. Pak ale $r(y,z) \le c(W)$, -proto¾e $\d(W)$ je také $yz$-øez. Tedy $\min(r(x,y),r(y,z)) \le r(x,z)$.\qed +\noindent Vrchol $y$ musí být v~jedné z~komponent, Pokud je v~komponentì s~$x$, pak $r(y,z) \le c(W)$, +proto¾e $\d(W)$ je také $yz$-øez. Pokud v~té druhé, analogicky platí $r(x,y) \le c(W)$. +\qed } \noindent Zpìt k~dùkazu vìty: @@ -63,7 +62,7 @@ Chceme dok Minimalitu doká¾eme indukcí podle délky cesty $P$: \itemize\ibull \:$\vert\,P\,\vert = 1$: Hrana $e$ je v~tomto pøípadì pøímo $st$, tak¾e i minimalita plyne z~definice \GHT. -\:$\vert\,P\,\vert > 1$: Cesta $P$ spojuje vrcholy $s$ a $t$, její první hrana je $sx$. +\:$\vert\,P\,\vert > 1$: Cesta $P$ spojuje vrcholy $s$ a $t$, její první hranu oznaème $sx$. Na¹e právì dokázané lemmátko øíká, ¾e $r(s,t) \ge \min (r(s,x),r(x,t))$. Urèitì je pravda, ¾e $r(s,x) \ge r(e)$, proto¾e $e$ byla hrana cesty $P$ s~nejmen¹ím $r(e)$. To, ¾e $r(x,t) \ge r(e)$, plyne z~indukèního pøedpokladu, proto¾e cesta mezi $x$ a $t$ @@ -101,13 +100,14 @@ Nyn $$\eqalignno{ c(U \cup X) &\ge c(U),&(1) \cr c(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$ -První nerovnost plyne z toho, ¾e $U \cup X$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. +První nerovnost plyne z toho, ¾e $\d(U \cup X)$ je nìjaký \st-øez, zatímco $\d(U)$ je minimální \st-øez. Druhou doká¾eme rozborem pøípadù. } Mno¾inu vrcholù si disjunktnì rozdìlíme na $X\setminus U$, $X \cap U$, $U \setminus X$ a $\$. -Ka¾dý z~øezù v~nerovnosti $(2)$ se skládá z~hran mezi tìmito skupinami vrcholù. +Ka¾dý z~øezù vystupujících v~nerovnosti $(2)$ mù¾eme zapsat jako sjednocení hran mezi nìkterými +z~tìchto skupin vrcholù. Vytvoøíme tedy tabulku hran mezi ètyømi oznaèenými skupinami vrcholù a ka¾dému øezu z~$(2)$ oznaèíme jemu odpovídající hrany. Proto¾e je graf neorientovaný, staèí nám jen horní trojúhelník tabulky. @@ -129,11 +129,11 @@ co \vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.eps}}\vss}\vskip-\baselineskip {\advance\hsize by -14em\itemcount=1 \:$t\in X$. Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Tentokrát se budou -hodit nerovnosti: +hodit tyto nerovnosti: $$\eqalignno{c(X \setminus U) &\ge c(U)&(3)\cr c(U \setminus X) + c(X \setminus U) &\le c(U) + c(X)&(4)}$$ -První platí proto, ¾e $X \setminus U$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez, druhou -doká¾eme opìt \uv{rozborem pøípadù}. +První platí proto, ¾e $\d(X \setminus U)$ je nìjaký \st-øez, zatímco $\d(U)$ je minimální \st-øez, druhou +doká¾eme opìt dùkladným rozborem pøípadù. } @@ -155,11 +155,11 @@ z~ \>Nyní se koneènì dostáváme ke konstrukci \GHT{}. Abychom mohli pou¾ívat indukci, zavedeme si trochu obecnìj¹í \GHT{}. -\s{Definice:} Mìjme neorientovaný graf $(V,E)$. {\I Èásteèný Gomory-Hu Tree} (alias \PGHT{}) pro $R \subseteq V$ je $((R,F),C)$, -kde $(R,F)$ je strom a mno¾ina $C=\{C(r) \;\vert\; r\in R\}$ je rozklad vrcholù $V$. Tento rozklad +\s{Definice:} Mìjme neorientovaný graf $(V,E)$. {\I Èásteèný Gomory-Hu Tree} (alias \PGHT{}) pro podmno¾inu vrcholù $R \subseteq V$ je dvojice $((R,F),C)$, +kde $(R,F)$ je strom a mno¾ina $C=\{C(r) \;\vert\; r\in R\}$ je rozklad mno¾iny vrcholù $V$. Tento rozklad nám øíká, k~jakým vrcholùm \PGHT{} máme pøilepit které vrcholy pùvodního grafu. Navíc musí platit, ¾e:\numlist\ndotted -\:$\forall r: r\in C(r)$, neboli ka¾dý vrchol \PGHT{} je pøilepen sám k~sobì, +\:$\forall r: r\in C(r)$, neboli ka¾dý vrchol \PGHT{} je pøilepen sám k~sobì, a \:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right)$ je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$. \endlist @@ -171,13 +171,13 @@ existuje \PGHT{}. \proof Doká¾eme indukcí podle velikosti mno¾iny $R$.\itemize\ibull \:$\vert R \vert = 1$: \PGHT{} má jediný vrchol $r\in R$ a $C(r)=V$. \:$\vert R \vert > 1$: Najdeme dvojici vrcholù $s,t\in R$ takovou, ¾e jejich minimální \st-øez $\d(W)$ -je nejmen¹í mo¾ný. Nyní vytvoøíme graf $G_1$ z~grafu $G$ zkontrahováním -v¹ech vrcholù $w\in W$ do jednoho vrcholu, který oznaèíme $v_1$, a vytvoøíme graf $G_2$ z~$G$ zkontrahováním -v¹ech vrcholù $w\in \overline W$ do jednoho vrcholu $v_2$.\foot{ +je nejmen¹í mo¾ný. Nyní vytvoøíme graf $G_1$ z~grafu $G$ kontrahováním +v¹ech vrcholù mno¾iny~$W$ do~jednoho vrcholu, který oznaèíme~$v_1$, a vytvoøíme graf $G_2$ z~$G$ kontrahováním +v¹ech vrcholù z~$\overline W$ do jednoho vrcholu $v_2$.\foot{ Proè to dìláme \uv{tak slo¾itì} a pøidáváme do $G_1$ vrchol $v_1$? Na první pohled to pøeci vypadá zbyteènì. Problém je v~tom, ¾e i kdy¾ dle HTL le¾í v¹echny minimální øezy oddìlující vrcholy z~$W$ v~mno¾inì vrcholù $W$, \ tìchto øezù celé v~podgrafu indukovaném~$W$ le¾et nemusí. K~tìmto øezùm toti¾ patøí i hrany, které -mají ve $W$ jenom jeden konec. Proto jsme do $G_1$ pøidali $v_1$, vedou do nìj v¹echny zajímavé +mají ve $W$ jenom jeden konec. Proto jsme do $G_1$ pøidali $v_1$ -- do~nìj vedou v¹echny zajímavé hrany, které mají ve $W$ jeden konec. Tím {\I zajímavé} myslíme to, ¾e z~ka¾dého vrcholu $w\in W$ vede do $v_1$ \ hrana, která z~nìj vedla do mno¾iny $V\setminus W$, pøípadnì ¾ádná, pokud do této mno¾iny ¾ádná hrana nevedla.} @@ -190,17 +190,18 @@ p pro $R_1$ na $G_1$ a $T_2=((R_2,F_2),C_2)$ pro $R_2$ na $G_2$. Nyní vytvoøíme \PGHT{} pro pùvodní graf. Oznaème $r_1$ ten vrchol $R_1$, pro který je $v_1 \in C(r_1)$, -obdobnì $r_2$. Oba \PGHT{} $T_1$ a $T_2$ spojíme hranou $r_1r_2$, tak¾e \PGHT{} pro $G$ -je $T=((R_1 \cup R_2,F_1 \cup F_2 \cup {r_1r_2}),C)$, pøièem¾ pro $r\in R_1$ je $C(r)=C_1(r)\setminus\{v_1\}$ -a pro $r\in R_2$ je $C(r)=C_2(r)\setminus\{v_2\}$ [odebrali jsme vrcholy $v_1$ a $v_2$ z~rozkladu $C$]. +a~obdobnì $r_2$. Oba \PGHT{} $T_1$ a $T_2$ spojíme hranou $r_1r_2$, tak¾e \PGHT{} pro $G$ +bude $T=((R_1 \cup R_2,F_1 \cup F_2 \cup {r_1r_2}),C)$. Tøídy rozkladu~$C$ zvolíme tak, ¾e pro $r\in R_1$ bude $C(r)=C_1(r)\setminus\{v_1\}$ +a pro $r\in R_2$ bude $C(r)=C_2(r)\setminus\{v_2\}$ [odebrali jsme vrcholy $v_1$ a $v_2$ z~rozkladu~$C$]. Chceme ukázat, ¾e tento $T$ je opravdu \PGHT. $C$ je urèitì rozklad v¹ech vrcholù a ka¾dé -$r\in C(r)$ z~indukèního pøedpokladu, tak¾e podmínka $1.$ je splnìna. Co se týèe podmínky $2.$, tak\itemize\ibull +$r\in C(r)$ z~indukèního pøedpokladu, tak¾e podmínka~1 je splnìna. Co se týèe podmínky~2, tak: +\itemize\ibull \:pro hranu \rr\ je $\d(W)$ urèitì minimální \rr-øez, proto¾e øez mezi $s$ a $t$ je souèasnì i \rr-øezem a je ze v¹ech mo¾ných minimálních øezù na $R$ nejmen¹í, \:pro hranu $e\ne r_1r_2$ je $\d(e)$ z~indukce minimální øez na jednom z~grafù $G_1$, $G_2$. -Tento øez také pøesnì odpovídá øezu v~grafu $G$, proto¾e v~$G_1$ i v~$G_2$ jsme poèítali -s~hranami vedoucími do $v_1$, $v_2$ a proto¾e jsme \PGHT{} napojili pøes vrcholy, +Tento øez také pøesnì odpovídá øezu v~grafu~$G$, proto¾e v~$G_1$ i v~$G_2$ jsme poèítali +s~hranami vedoucími do~$v_1$, $v_2$ a proto¾e jsme \PGHT{} napojili pøes vrcholy, k~nim¾ byly $v_1$ a $v_2$ pøilepeny. HTL nám navíc øíká, ¾e existuje minimální øez, který ¾ije pouze v~pøíslu¹ném z~grafù $G_1$, $G_2$, @@ -213,16 +214,16 @@ Nyn vrcholù $s,t$ tak, aby byl minimální \st-øez nejmen¹í mo¾ný, je èasovì nároèné. Proto si poslední vìtu je¹tì o~nìco vylep¹íme. -\s{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$ a $t$ +\s{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$~a~$t$ takové, aby byl minimální \st-øez nejmen¹í mo¾ný. Staèí zvolit \ vrcholy $s,t\in R$ -a nalézt minimální \st-øez $\d(W)$. +a zvolit $\d(W)$ jako minimální \st-øez. \proof Nejprve si uvìdomme, proè jsme v~pøedchozím dùkazu potøebovali, aby byl $\d(W)$ nejmen¹í ze v¹ech mo¾ných \st-øezù. Bylo to jenom proto, ¾e jsme jím v~\PGHT{} nakonec separovali vrcholy $r_1$ a $r_2$ a potøebovali jsme záruku, aby byl $\d(W)$ opravdu minimální \rr-øez. Nyní musíme ukázat, ¾e námi nalezený \st-øez $\d(W)$ je také minimálním \rr-øezem. -Pro spor tedy pøedpokládejme, ¾e minimální \rr-øez $\d(X)$ má men¹í kapacitu ne¾ $\d(W)$. +Pro spor tedy pøedpokládejme, ¾e nìjaký \rr-øez $\d(X)$ má men¹í kapacitu ne¾ $\d(W)$. Navíc vezmìme ten pøípad, kdy se to stalo \uv{poprvé}, tak¾e pro ka¾dé men¹í $R$ je v¹echno v~poøádku (to mù¾eme, proto¾e pro $\vert R \vert=1$ v¹echno v~poøádku bylo). @@ -244,7 +245,5 @@ nalezneme v~ zpracujeme rekurzivnì. Celou výstavbu tedy zvládneme v~èase $\O(n\tau)$, èili $\O(n^{5/3}m)$ pro neohodnocené grafy. -\todo{Odkazy na rychlej¹í algoritmy} - \references \bye -- 2.39.2