4-ght/4-ght.tex

   1 % Written by Milan Straka, 2006
   2
   3 \def\li{\discretionary{-}{-}{-}li}
   4 \def\d{\delta}
   5 \def\st{$st$}
   6 \def\rr{$r_1r_2$}
   7 \def\GHT{GHT}
   8 \def\PGHT{ÈGHT}
   9 \def\th#1{\s{#1}}
  10 \def\proof{\noindent{\it Dùkaz:} }
  11
  12 \input ../sgr.tex
  13
  14 \prednaska{4}{Gomory-Hu Trees}{zapsal Milan Straka}
  15
  16 \h{Gomory-Hu Trees}
  17
  18 Cílem této pøedná¹ky bylo vytvoøit datovou strukturu, která po urèitém
  19 pøedzpracování doká¾e rychle konstruovat minimální øezy pro libovolnou
  20 dvojici vrcholù v~grafu.
  21
  22 Zatím umíme nalézt minimální \st-øez pro zadanou dvojici vrcholù v~èase
  23 $\tau=\O(n^{2/3}m)$. Nalézt minimální \st-øez pro ka¾dou dvojici vrcholù
  24 bychom tedy dokázali v~èase $\O(n^2\tau)$. Tento výsledek budeme
  25 chtít zlep¹it.
  26
  27 \s{Znaèení:} Máme\li{} graf $(V,E)$ a $U\subseteq V$, $\d(U)$ znaèí hrany vedoucí
  28 mezi $U$ a $V\setminus U$. Formálnì tedy $\d(U)=E \cap (U \times (V \setminus U))$.
  29 Kapacitu øezu $W$ budeme znaèit $c(W)$ a $r(s,t)$ budeme znaèit kapacitu nejmen¹ího \st-øezu.
  30
  31 \s{Pozorování:} Minimální øez rozdìluje graf jen na~dvì komponenty (v¹imnìte si, ¾e pro
  32 separátory nic takového neplatí) a ka¾dý minimální øez je tím pádem v¾dy mo¾né zapsat jako $\d(W)$
  33 pro nìjakou mno¾inu $W\subset V$.
  34
  35 \s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný ohodnocený graf $G=(V,E)$
  36 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
  37 $K_1$ a $K_2$ jsou komponenty $T\setminus st$}.$$
  38 Pozor, $F$ nemusí být podmno¾ina pùvodních hran $E$.
  39
  40 \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.
  41
  42 K~èemu takový \GHT{} je (existuje-li)? To nám poví následující
  43
  44 \th{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
  45 nech» $P$ je cesta v~$T$ mezi vrcholy $s$ a $t$ a $e$ je hrana na cestì $P$ s~minimálním $r(e)$.
  46 Pak $\d(e)$ je minimální \st-øez.
  47
  48 \proof Nejprve si doká¾eme jedno drobné
  49
  50 {\advance\leftskip by 2em
  51 \th{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e $r(x,z) \ge \min(r(x,y),r(y,z))$.
  52
  53 \proof Buï $W$ minimální $xz$-øez.
  54
  55 \centerline{\epsfysize=1.5cm\epsfbox{4-ght-rez.eps}}
  56
  57 \noindent Vrchol $y$ musí být v~jedné z~komponent, BÚNO v~komponentì s~$x$. Pak ale $r(y,z) \le c(W)$,
  58 proto¾e $W$ je také $yz$-øez. Tedy $\min(r(x,y),r(y,z)) \le r(x,z)$.\qed
  59 }
  60
  61 \noindent Zpìt k~dùkazu vìty:
  62 Chceme dokázat, ¾e $\d(e)$ je minimální \st-øez. To, ¾e je to nìjaký øez, plyne z~definice \GHT.
  63 Minimalitu doká¾eme indukcí podle délky cesty $P$.\itemize\ibull
  64 \:$\vert\,P\,\vert = 1$: Hrana $e$ je v~tomto pøípadì pøímo $st$, tak¾e i minimalita plyne z~definice \GHT.
  65 \:$\vert\,P\,\vert > 1$: Cesta $P$ spojuje vrcholy $s$ a $t$, její první hrana je $sx$.
  66 Na¹e právì dokázané lemmátko øíká, ¾e $r(s,t) \ge \min (r(s,x),r(x,t))$.
  67 Urèitì je pravda, ¾e $r(s,x) \ge r(e)$, proto¾e $e$ byla hrana cesty $P$ s~nejmen¹ím $r(e)$.
  68 To, ¾e $r(x,t) \ge r(e)$, plyne z~indukèního pøedpokladu, proto¾e cesta mezi $x$ a $t$
  69 je krat¹í ne¾ cesta $P$. Dostáváme tak, ¾e $r(s,t) \ge \min(r(s,x),r(x,t)) \ge r(e)$.
  70 \endlist
  71 \qed
  72 Pokud doká¾eme \GHT{} sestrojit, nalézt minimální \st-øez pro libovolnou dvojici vrcholù
  73 doká¾eme stejnì rychle jako nalézt hranu s~nejmen¹í kapacitou na cestì mezi $s$ a $t$ v~\GHT.
  74 K~tomu mù¾eme pou¾ít napøíklad Sleator-Tarjanovy stromy, které tuto operaci
  75 doká¾ou provést v~amortizovaném èase $\O(\log n)$, nebo mù¾eme vyu¾ít toho,
  76 ¾e máme spoustu èasu na~pøedvýpoèet, a minimální hrany si pro ka¾dou dvojici
  77 prostì pøichystat pøedem. Také lze vymyslet redukci na problém nalezení spoleèného
  78 pøedchùdce vrcholù ve stromì (nebude to \GHT) a pou¾ít jedno z~øe¹ení tohoto problému.
  79
  80 \h{Konstrukce GHT}
  81
  82 Nyní se nauèíme \GHT{} konstruovat, èím¾ také rozptýlíme obavy o~jejich existenci.
  83 Nejprve v¹ak budeme potøebovat jedno u¾iteèné lemma s~hnusnì technickým dùkazem:
  84
  85 \vbox to 0pt{\vskip-\baselineskip\rightline{\epsfysize=2cm\epsfbox{4-ght-htl.eps}}\vss}\vskip-\baselineskip
  86 {
  87 \advance\rightskip by 17em
  88 \th{Hnusnì technické lemma (HTL):} Buïte¾ $s,t$ vrcholy grafu $(V,E)$, $\d(U)$ minimální \st-øez a $u\ne v$ dva rùzné
  89 vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální  $uv$-øez.
  90 [To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.]
  91
  92 \proof Nech» je $\d(X)$ minimální $uv$-øez.
  93 BÚNO mù¾eme pøedpokládat, ¾e $s$ je v~$U$ a $t$ není v~$U$, $u$ je v~$X$ a $v$ není v~$X$ a $s$ je v~$X$.
  94 Pokud by tomu tak nebylo, mù¾eme vrcholy pøeznaèit.
  95
  96 }
  97
  98 Nyní mohou nastat dva pøípady:\numlist\nalpha
  99 \vbox to 0pt{\vskip -1cm\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip
 100 {\advance\hsize by -14em
 101 \:$t$ není prvek $X$.\par
 102 Doká¾eme dvì nerovnosti. Nerovnost $$\eqalignno{c(\d(U \cup X)) &\ge c(\d(U))&(1)}$$
 103 platí proto, ¾e $U \cup X$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í
 104 $$\eqalignno{c(\d(U \cap X)) + c(\d(U \cup X)) &\le c(\d(U)) + c(\d(X))&(2)}$$
 105 doká¾eme \uv{rozborem pøípadù}.
 106
 107 }
 108
 109 Mno¾inu vrcholù si disjunktnì rozdìlíme na $X\setminus U$, $X \cap U$, $U \setminus X$ a $\<ostatní>$.
 110 Ka¾dý z~øezù v~nerovnosti $(2)$ se skládá z~hran mezi tìmito skupinami vrcholù.
 111 Vytvoøíme tedy tabulku hran mezi ètyømi oznaèenými skupinami vrcholù a ka¾dému
 112 øezu z~$(2)$ oznaèíme jemu odpovídající hrany. Proto¾e je graf neorientovaný,
 113 staèí nám jen horní trojúhelník tabulky.
 114 Pro pøehlednosti si oznaèíme $L_1=\d(U \cap X), L_2=\d(U \cup X), P_1=\d(U)$ a $P_2=\d(X)$.
 115 $$\matrix{&X\setminus U&X \cap U&U \setminus X&\<ostatní>\cr\noalign{\smallskip}
 116 X\setminus U&\hbox{---}&L_1,P_1&P_1,P_2&L_2,P_2\cr
 117 X \cap U&&\hbox{---}&L_1,P_2&L_1,L_2,P_1,P_2\cr
 118 U \setminus X&&&\hbox{---}&L_2,P_1\cr
 119 \<ostatní>&&&&\hbox{---}\cr
 120 }$$
 121
 122 Vidíme, ¾e ke ka¾dé hranì øezu na levé stranì nerovnosti máme vpravo její protìj¹ek
 123 a navíc hrany mezi $U\setminus X$ a $X \setminus U$ poèítáme jenom vpravo. Nerovnost
 124 $(2)$ tedy platí.
 125
 126 Nyní staèí nerovnosti $(2)$ a $(1)$ odeèíst, èím¾ získáme $$c(\d(U \cap X)) \le c(\d(X)),$$
 127 co¾ spolu s~obrázkem dokazuje, ¾e $\d(U \cap X)$ je také minimální $uv$-øez.
 128
 129 \vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.eps}}\vss}\vskip-\baselineskip
 130 {\advance\hsize by -14em\itemcount=1
 131 \:$t$ je prvek $X$.\par
 132 Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Nerovnost $$\eqalignno{c(\d(X \setminus U)) &\ge c(\d(U))&(3)}$$
 133 platí proto, ¾e $X \setminus U$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í
 134 $$\eqalignno{c(\d(U \setminus X)) + c(\d(X \setminus U)) &\le c(\d(U)) + c(\d(X))&(4)}$$
 135 doká¾eme opìt \uv{rozborem pøípadù}.
 136
 137 }
 138
 139 Oznaème $L_1=\d(U \setminus X), L_2=\d(X \setminus U), P_1=\d(U)$ a $P_2=\d(X)$ a vytvoøme tabulku:
 140 $$\matrix{&X\setminus U&X \cap U&U \setminus X&\<ostatní>\cr\noalign{\smallskip}
 141 X\setminus U&\hbox{---}&L_2,P_1&L_1,L_2,P_1,P_2&L_2,P_2\cr
 142 X \cap U&&\hbox{---}&L_1,P_2&P_1,P_2\cr
 143 U \setminus X&&&\hbox{---}&L_1,P_1\cr
 144 \<ostatní>&&&&\hbox{---}\cr
 145 }$$
 146
 147 Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme
 148 $$c(\d(U \setminus X)) \le c(\d(X)),$$
 149 z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez.
 150 \endlist
 151 \qed
 152
 153 \bigskip
 154 Nyní se koneènì dostáváme ke konstrukci \GHT{}. Abychom mohli pou¾ívat
 155 indukci, zavedeme si trochu obecnìj¹í \GHT{}.
 156
 157 \s{Definice:} Mìjme neorientovaný graf $(V,E)$. {\I Èásteèný Gomory-Hu Tree} (alias \PGHT{}) pro $R \subseteq V$ je $((R,F),C)$,
 158 kde $(R,F)$ je strom a mno¾ina $C=\{C(r) \;\vert\; r\in R\}$ je rozklad vrcholù $V$. Tento rozklad
 159 nám øíká, k~jakým vrcholùm \PGHT{} máme pøilepit které vrcholy pùvodního grafu.
 160 Navíc musí platit, ¾e:\numlist\ndotted
 161 \:$\forall r: r\in C(r)$, neboli ka¾dý vrchol \PGHT{} je pøilepen sám k~sobì,
 162 \:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right)
 163 \hbox{ je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$}.$
 164 \endlist
 165
 166
 167 \th{Vìta (o~existenci \PGHT{}):} Buï $(V,E)$ neorientovaný ohodnocený graf. Pro ka¾dou podmno¾inu vrcholù $R$
 168 existuje \PGHT{}.
 169
 170 \proof Doká¾eme indukcí podle velikosti mno¾iny $R$.\itemize\ibull
 171 \:$\vert R \vert = 1$: \PGHT{} má jediný vrchol $r\in R$ a $C(r)=V$.
 172 \:$\vert R \vert > 1$: Najdeme dvojici vrcholù $s,t\in R$ takové, ¾e jejich minimální \st-øez $\d(W)$
 173 je ze v¹ech mo¾ných minimálních \st-øezù nejmen¹í. Nyní vytvoøíme graf $G_1$ z~grafu $G$ zkontrahováním
 174 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
 175 v¹ech vrcholù $w\in V\setminus W$ do jednoho vrcholu $v_2$.
 176
 177 \medskip
 178 \centerline{\epsfysize=2cm\epsfbox{4-ght-g1g2.eps}}
 179
 180 [Proè to dìláme \uv{tak slo¾itì} a pøidáváme do $G_1$ vrchol $v_1$? Mì osobnì to dlouho pøi¹lo zbyteèné.
 181 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ù
 182 $W$, \<hrany> tìchto øezù celé ve $W$ le¾et nemusí. K~tìmto øezùm toti¾ patøí i hrany, které
 183 mají ve $W$ jenom jeden konec. Proto jsme do $G_1$ pøidali $v_1$, vedou do nìj v¹echny zajímavé
 184 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
 185 do $v_1$ \<nejlevnìj¹í> hrana, která z~nìj vedla do mno¾iny $V\setminus W$, pøípadnì ¾ádná, pokud
 186 do této mno¾iny ¾ádná hrana nevedla.]
 187
 188 Dále vytvoøíme mno¾iny vrcholù $R_1=R \cap (V\setminus W)$ a $R_2=R \cap W$. Dle indukèního
 189 pøedpokladu ($R_1$ i $R_2$ jsou men¹í ne¾ $R$) existuje \PGHT{} $T_1=((R_1,F_1),C_1)$
 190 pro $R_1$ na $G_1$ a $T_2=((R_2,F_2),C_2)$ pro $R_2$ na $G_2$.
 191
 192 Nyní vytvoøíme \PGHT{} pro pùvodní graf. Oznaème $r_1$ vrchol $R_1$, pro který je $v_1 \in C(r_1)$,
 193 obdobnì $r_2$. Oba \PGHT{} $T_1$ a $T_2$ spojíme hranou $r_1r_2$, tak¾e \PGHT{} pro $G$
 194 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\}$
 195 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$].
 196
 197 Chceme ukázat, ¾e tento $T$ je opravdu \PGHT. $C$ je urèitì rozklad v¹ech vrcholù a ka¾dé
 198 $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
 199 \:pro hranu $r1r2$ je $\d(W)$ urèitì minimální $r_2r_2$-øez, proto¾e øez mezi \rr\ to
 200 je a byl ze v¹ech mo¾ných minimálních øezù na $R$ nejmen¹í,
 201 \:pro hranu $e\ne r_1r_2$ je $\d(e)$ z~indukce minimální øez na jednom z~grafù $G_1$, $G_2$.
 202 Tento øez také pøesnì odpovídá øezu v~grafu $G$, proto¾e v~$G_1$ i v~$G_2$ jsme poèítali
 203 s~hranami vedoucími do $v_1$, $v_2$ a proto¾e jsme \PGHT{} napojili pøes vrcholy,
 204 k~nim¾ byly $v_1$ a $v_2$ pøilepeny.
 205
 206 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$,
 207 tak¾e nalezený øez je minimální pro celý graf $G$.
 208 \endlist
 209 \endlist
 210 \qed
 211
 212 Nyní víme, ¾e \GHT{} existují, a také víme, jak by se daly konstruovat. Nicménì nalezení
 213 vrcholù $s,t$ tak, aby byl minimální \st-øez nejmen¹í mo¾ný, je èasovì nároèné.
 214 Proto si poslední vìtu je¹tì o~nìco vylep¹íme.
 215
 216 \th{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$ a $t$
 217 takové, aby byl minimální \st-øez nejmen¹í mo¾ný. Staèí zvolit \<libovolné> vrcholy $s,t\in R$
 218 a nalézt minimální øez $\d(W)$.
 219
 220 \proof Nejprve si uvìdomme, proè jsme v~pøedchozím dùkazu potøebovali, aby byl $W$ nejmen¹í ze v¹ech
 221 mo¾ných \st-øezù. Bylo to jenom proto, ¾e jsme jím v~\PGHT{} nakonec separovali vrcholy $r_1$ a $r_2$
 222 a potøebovali jsme záruku, aby byl $\d(W)$ opravdu minimální \rr-øez. Nyní musíme ukázat,
 223 ¾e námi nalezený \st-øez $\d(W)$ je také minimálním \rr-øezem.
 224
 225 Pro spor tedy pøedpokládejme, ¾e minimální \rr-øez $\d(X)$ má men¹í kapacitu ne¾ $\d(W)$.
 226 Navíc vezmìme ten pøípad, kdy se to stalo \uv{poprvé}, tak¾e pro ka¾dé men¹í $R$ je
 227 v¹echno v~poøádku (to mù¾eme, proto¾e pro $\vert R \vert=1$ v¹echno v~poøádku bylo).
 228
 229 Proto¾e byl $\d(W)$ minimální \st-øez a $\d(X)$ má men¹í kapacitu, $\d(X)$ nemù¾e separovat
 230 $s$ a $t$. Pøitom ale separuje $r_1$ a $r_2$, tak¾e musí separovat buï $s$ a $r_1$, nebo $t$ a $r_2$.
 231 BÚNO nech» $X$ separuje $s$ a $r_1$.
 232
 233 \medskip
 234 \centerline{\epsfysize=2.2cm\epsfbox{4-ght-rezx.eps}}
 235 \smallskip
 236
 237 Podívejme se nyní na \PGHT{} $T_1$ a naleznìme v~nìm nejlevnìj¹í hranu $e$ na cestì spojující $s$ a $r_1$.
 238 Tato hrana definuje øez $\d(U)$, co¾ je minimální $sr_1$-øez. Proto¾e $\d(X)$ je $sr_1$-øez,
 239 $c(\d(U)) \le c(\d(X)) < c(\d(W))$. Teï si staèí uvìdomit, ¾e $v_1\in C(r_1)$, tak¾e $\d(U)$
 240 separuje nejenom $s$ a $r_1$, ale také $s$ a $v_1$. Tím pádem ale separuje také $s$ a $t$.
 241 To je spor, proto¾e $c(\d(U)) < c(\d(W))$ a pøitom $\d(W)$ mìl být minimální.
 242 \qed
 243
 244 Teï u¾ doká¾eme \GHT{} konstruovat efektivnì -- v~ka¾dém kroku vybereme dva vrcholy $s$ a $t$,
 245 nalezneme v~èase $\O(\tau)$ minimální \st-øez, a výsledné komponenty s~pøidanými $v_1,v_2$
 246 zpracujeme rekurzivnì. Celou výstavbu tedy zvládneme v~èase $\O(n\tau)=\O(n^{5/3}m)$.
 247 Nalézt minimální \st-øezy pro v¹echny dvojice pak doká¾eme v~èase $\O(n^2)$, pøípadnì
 248 v~èase $\O(n^2\log n)$ (zále¾í na zpùsobu hledání nejlevnìj¹í hrany v~\GHT).
 249
 250 \bye