4-ght/4-ght.tex

   1 \def\li{\discretionary{-}{-}{-}li}
   2 \def\d{\delta}
   3 \def\st{$st$}
   4 \def\rr{$r_1r_2$}
   5 \def\GHT{GHT}
   6 \def\PGHT{ČGHT}
   7
   8 \input ../sgr.tex
   9
  10 \prednaska{4}{Gomory-Hu Trees}{}
  11
  12 Cílem této kapitoly je popsat datovou strukturu, která velice kompaktně
  13 popisuje minimální $st$-řezy pro všechny dvojice vrcholů $s,t$ v~daném
  14 neorientovaném grafu. Tuto strukturu poprvé popsali Gomory a Hu v~článku \cite{gomoryhu}.
  15
  16 Zatím umíme nalézt minimální \st-řez pro zadanou dvojici vrcholů v~neorientovaném
  17 grafu v~čase $\tau=\O(n^{2/3}m)$ pro~jednotkové kapacity, $\O(n^2m)$ pro obecné.
  18 Nalézt minimální \st-řez pro každou dvojici vrcholů
  19 bychom tedy dokázali v~čase $\O(n^2\tau)$. Tento výsledek budeme
  20 chtít zlepšit.
  21
  22 \s{Značení:} Máme\li{} graf $(V,E)$ a $U\subseteq V$, $\d(U)$ značí hrany vedoucí
  23 mezi $U$ a $\overline U$, formálně tedy $\d(U)=E \cap ((U \times \overline U) \cup (\overline U \times U))$.
  24 Kapacitu řezu $\d(W)$ budeme značit $d(W)$ a $r(s,t)$ bude kapacita nejmenšího \st-řezu.
  25
  26 \s{Pozorování:} Minimální řez rozděluje graf jen na~dvě komponenty (všimněte si, že pro
  27 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)$
  28 pro nějakou množinu $W\subset V$.
  29
  30 \h{Gomory-Hu Tree}
  31
  32 \s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný nezáporně ohodnocený graf $G=(V,E)$
  33 je strom $T=(V,F)$ takový, že pro každou hranu $st\in F$ platí: Označíme-li $K_1$ a $K_2$
  34 komponenty lesa $T\setminus st$, je $\d(K_1)=\d(K_2)$ minimální \st-řez.
  35 [Pozor, $F$ nemusí být podmnožina původních hran $E$.]
  36
  37 \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.
  38
  39 \>K~čemu takový \GHT{} je (existuje-li)? To nám poví následující věta:
  40
  41 \s{Věta (o~využití \GHT):} Buď $T$ libovolný \GHT{} pro graf~$G$ a mějme dva vrcholy $s$ a $t$. Dále
  42 nechť $P$ je cesta v~$T$ mezi vrcholy $s$ a $t$ a $e$ je hrana na cestě $P$ s~minimálním $r(e)$.
  43 Pak $\d(e)$ je minimální \st-řez v~$G$.
  44
  45 \proof Nejprve si dokážeme jedno drobné lemmátko:
  46
  47 {\advance\leftskip by 2em\advance\rightskip by 2em
  48 \s{Lemmátko:} Pro každou trojici vrcholů $x,y,z$ platí, že:
  49 $$r(x,z) \ge \min(r(x,y),r(y,z)).$$
  50
  51 \proof Buď $W$ minimální $xz$-řez.
  52
  53 \fig{4-ght-rez.epdf}{}
  54
  55 \noindent Vrchol $y$ musí být v~jedné z~komponent, Pokud je v~komponentě s~$x$, pak $r(y,z) \le d(W)$,
  56 protože $\d(W)$ je také $yz$-řez. Pokud v~té druhé, analogicky platí $r(x,y) \le d(W)$.
  57 \qed
  58 }
  59
  60 \noindent Zpět k~důkazu věty:
  61 Chceme dokázat, že $\d(e)$ je minimální \st-řez. To, že je to nějaký řez, plyne z~definice \GHT.
  62 Minimalitu dokážeme indukcí podle délky cesty $P$:
  63 \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í hranu označme $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 \qeditem
  71 \endlist
  72
  73 Pokud dokážeme \GHT{} sestrojit, nalézt minimální \st-řez pro libovolnou dvojici vrcholů
  74 dokážeme stejně rychle jako nalézt hranu s~nejmenší kapacitou na cestě mezi $s$ a $t$ v~\GHT.
  75 K~tomu můžeme použít například Sleator-Tarjanovy stromy, které tuto operaci
  76 dokážou provést v~amortizovaném čase $\O(\log n)$, nebo můžeme využít toho,
  77 že máme spoustu času na~předvýpočet, a minimální hrany si pro každou dvojici
  78 prostě přichystat předem. Také lze vymyslet redukci na problém nalezení společného
  79 předchůdce vrcholů ve stromě (nebude to \GHT) a použít jedno z~řešení tohoto problému.
  80
  81 \h{Konstrukce GHT}
  82
  83 Nyní se naučíme \GHT{} konstruovat, čímž také rozptýlíme obavy o~jejich existenci.
  84 Nejprve však budeme potřebovat jedno užitečné lemma s~hnusně technickým důkazem:
  85
  86 \s{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é
  87 vrcholy z~$U$. Pak existuje množina vrcholů $W \subseteq U$ taková, že $\d(W)$ je minimální $uv$-řez.
  88 \foot{To důležité a netriviální je, že celá $W$ leží v~$U$.}
  89
  90 \fig{4-ght-htl.epdf}{}
  91
  92 \proof Nechť je $\d(X)$ minimální $uv$-řez.
  93 BÚNO můžeme předpokládat, že $s\in U$ a $t\not\in U$, $u\in X$ a $v\not\in X$ a $s\in X$.
  94 Pokud by tomu tak nebylo, můžeme vrcholy přeznačit nebo některou z~množin nahradit jejím doplňkem.
  95
  96 \checkroom{40pt}
  97
  98 Nyní mohou nastat následující dva případy:\numlist\nalpha
  99 \vbox to 0pt{\vskip 10pt\rightline{\putepdf{height 2.5cm}{4-ght-htl-a.epdf}}\vss}\vskip-\baselineskip
 100 \:$t\not\in X$. Tehdy si všimneme, že platí:
 101 \hangindent=-14em\hangafter=-100
 102 $$\eqalignno{
 103 d(U \cup X) &\ge d(U),&(1) \cr
 104 d(U \cap X) + d(U \cup X) &\le d(U) + d(X)&(2)}$$
 105 První nerovnost plyne z toho, že $\d(U \cup X)$ je nějaký \st-řez, zatímco $\d(U)$ je minimální \st-řez.
 106 Druhou dokážeme rozborem případů.
 107
 108 Množinu vrcholů si disjunktně rozdělíme na $X\setminus U$, $X \cap U$, $U \setminus X$ a $\<ostatní>$.
 109 Každý z~řezů vystupujících v~nerovnosti $(2)$ můžeme zapsat jako sjednocení hran mezi některými
 110 z~těchto skupin 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: $$d(U \cap X) \le 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{\vskip 20pt\rightline{\putepdf{height 2.5cm}{4-ght-htl-b.epdf}}\vss}\vskip-\baselineskip
 130 \:$t\in X$. Postupovat budeme obdobně jako v~předchozím případě. Tentokrát se budou
 131 hodit tyto nerovnosti:
 132 \hangindent=-14em\hangafter=-100
 133 $$\eqalignno{d(X \setminus U) &\ge d(U)&(3)\cr
 134 d(U \setminus X) + d(X \setminus U) &\le d(U) + d(X)&(4)}$$
 135 První platí proto, že $\d(X \setminus U)$ je nějaký \st-řez, zatímco $\d(U)$ je minimální \st-řez, druhou
 136 dokážeme opět důkladným rozborem případů.
 137
 138 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:
 139 $$\matrix{&X\setminus U&X \cap U&U \setminus X&\<ostatní>\cr\noalign{\smallskip}
 140 X\setminus U&\hbox{---}&L_2,P_1&L_1,L_2,P_1,P_2&L_2,P_2\cr
 141 X \cap U&&\hbox{---}&L_1,P_2&P_1,P_2\cr
 142 U \setminus X&&&\hbox{---}&L_1,P_1\cr
 143 \<ostatní>&&&&\hbox{---}\cr
 144 }$$
 145
 146 Stejně jako v~předchozím případě nerovnost $(4)$ platí. Odečtením $(4)$ a $(3)$ získáme:
 147 $$d(U \setminus X) \le d(X),$$
 148 z~čehož opět dostaneme, že $\d(U \setminus X)$ je také minimální $uv$-řez.
 149 \qeditem
 150 \endlist
 151
 152 \bigskip
 153 \>Nyní se konečně dostáváme ke konstrukci \GHT{}. Abychom mohli používat
 154 indukci, zavedeme si trochu obecnější \GHT{}.
 155
 156 \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)$,
 157 kde $(R,F)$ je strom a množina $C=\{C(r) \;\vert\; r\in R\}$ je rozklad množiny vrcholů $V$. Tento rozklad
 158 nám říká, k~jakým vrcholům \PGHT{} máme přilepit které vrcholy původního grafu.
 159 Navíc musí platit, že:\numlist\ndotted
 160 \:$\forall r: r\in C(r)$, neboli každý vrchol \PGHT{} je přilepen sám k~sobě, a
 161 \:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right)$
 162 je minimální \st-řez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$.
 163 \endlist
 164
 165
 166 \s{Věta (o~existenci \PGHT{}):} Buď $(V,E)$ neorientovaný nezáporně ohodnocený graf. Pro každou podmnožinu vrcholů $R$
 167 existuje \PGHT{}.
 168
 169 \proof Dokážeme indukcí podle velikosti množiny $R$.\itemize\ibull
 170 \:$\vert R \vert = 1$: \PGHT{} má jediný vrchol $r\in R$ a $C(r)=V$.
 171 \:$\vert R \vert > 1$: Najdeme dvojici vrcholů $s,t\in R$ takovou, že jejich minimální \st-řez $\d(W)$
 172 je nejmenší možný. Nyní vytvoříme graf $G_1$ z~grafu $G$ kontrahováním
 173 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
 174 všech vrcholů z~$\overline W$ do jednoho vrcholu $v_2$.\foot{
 175 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ě.
 176 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ů
 177 $W$, \<hrany> těchto řezů celé v~podgrafu indukovaném~$W$ ležet nemusí. K~těmto řezům totiž patří i hrany, které
 178 mají ve $W$ jenom jeden konec. Proto jsme do $G_1$ přidali $v_1$ -- do~něj vedou všechny zajímavé
 179 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
 180 do $v_1$ \<nejlevnější> hrana, která z~něj vedla do množiny $V\setminus W$, případně žádná, pokud
 181 do této množiny žádná hrana nevedla.}
 182
 183 \fig{4-ght-g1g2-before.epdf}{width 0.45\hsize}
 184 \fig{4-ght-g1g2-after.epdf}{width 0.9\hsize}
 185 \finalfix{\bigskip}
 186
 187 Dále vytvoříme množiny vrcholů $R_1=R \cap \overline W$ a $R_2=R \cap W$. Dle indukčního
 188 předpokladu ($R_1$ i $R_2$ jsou menší než $R$) existuje \PGHT{} $T_1=((R_1,F_1),C_1)$
 189 pro $R_1$ na $G_1$ a $T_2=((R_2,F_2),C_2)$ pro $R_2$ na $G_2$.
 190
 191 Nyní vytvoříme \PGHT{} pro původní graf. Označme $r_1$ ten vrchol $R_1$, pro který je $v_1 \in C_1(r_1)$,
 192 a~obdobně $r_2$. Oba \PGHT{} $T_1$ a $T_2$ spojíme hranou $r_1r_2$, takže \PGHT{} pro $G$
 193 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\}$
 194 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$].
 195
 196 Chceme ukázat, že tento $T$ je opravdu \PGHT. $C$ je určitě rozklad všech vrcholů a každé
 197 $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:
 198 \itemize\ibull
 199 \:pro hranu \rr\ je $\d(W)$ určitě minimální \rr-řez, protože řez mezi $s$ a $t$ je současně
 200 i \rr-řezem a je 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 \qeditem
 209 \endlist
 210 \endlist
 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 \s{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 zvolit $\d(W)$ jako minimální \st-řez.
 219
 220 \proof Nejprve si uvědomme, proč jsme v~předchozím důkazu potřebovali, aby byl $\d(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 nějaký \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 $\d(W)$ je 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 \fig{4-ght-rezx.epdf}{width 12cm}
 234
 235 Podívejme se nyní na \PGHT{} $T_1$ (víme, že ten je korektní) a nalezněme v~něm nejlevnější hranu $e$ na cestě spojující $s$ a $r_1$.
 236 Tato hrana definuje řez $\d(U)$, což je minimální $sr_1$-řez, podle HTL i v~celém~$G$. Protože $\d(X)$ je $sr_1$-řez,
 237 je $d(U) \le d(X) < d(W)$. Teď si stačí uvědomit, že $v_1\in C(r_1)$, takže $\d(U)$
 238 separuje nejenom $s$ a $r_1$, ale také $s$ a $v_1$. Tím pádem ale separuje také $s$ a $t$.
 239 To je spor, protože $d(U) < d(W)$, a přitom $\d(W)$ měl být minimální.
 240 \qed
 241
 242 Teď už dokážeme \GHT{} konstruovat efektivně -- v~každém kroku vybereme dva vrcholy $s$ a $t$,
 243 nalezneme v~čase $\O(\tau)$ minimální \st-řez a výsledné komponenty s~přidanými $v_1,v_2$
 244 zpracujeme rekurzivně. Celou výstavbu tedy zvládneme v~čase $\O(n\tau)$, čili $\O(n^{5/3}m)$
 245 pro neohodnocené grafy.
 246
 247 \references
 248 \bye