\input ../sgr.tex
-\prednaska{4}{Gomory-Hu Trees}{zapsal Milan Straka}
+\prednaska{4}{Gomory-Hu Trees}{}
Cílem této kapitoly je vytvoøit datovou strukturu, která po urèitém
pøedzpracování doká¾e rychle konstruovat pro libovolnou dvojici vrcholù v~grafu
grafu v~èase $\tau=\O(n^{2/3}m)$ pro~jednotkové kapacity, $\O(n^2m)$ pro obecné.
Nalézt minimální \st-øez pro ka¾dou dvojici vrcholù
bychom tedy dokázali v~èase $\O(n^2\tau)$. Tento výsledek budeme
-chtít zlep¹it.
+chtít zlep¹it. \cite{gomoryhu}
\s{Znaèení:} Máme\li{} graf $(V,E)$ a $U\subseteq V$, $\d(U)$ znaèí hrany vedoucí
mezi $U$ a $\overline U$, formálnì tedy $\d(U)=E \cap ((U \times \overline U) \cup (\overline U \times U))$.
\proof Buï $W$ minimální $xz$-øez.
-\centerline{\epsfysize=1.5cm\epsfbox{4-ght-rez.eps}}
+\fig{4-ght-rez.eps}{5cm}
\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
\:$t\not\in X$.\par
Doká¾eme dvì nerovnosti. Nerovnost $$\eqalignno{c(U \cup X) &\ge c(U)&(1)}$$
platí proto, ¾e $U \cup X$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í
-$$\eqalignno{\d(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$
+$$\eqalignno{c(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$
doká¾eme \uv{rozborem pøípadù}.
}
do $v_1$ \<nejlevnìj¹í> hrana, která z~nìj vedla do mno¾iny $V\setminus W$, pøípadnì ¾ádná, pokud
do této mno¾iny ¾ádná hrana nevedla.}
-\medskip
-\centerline{\epsfysize=2cm\epsfbox{4-ght-g1g2.eps}}
+\fig{4-ght-g1g2.eps}{0.9\hsize}
-Dále vytvoøíme mno¾iny vrcholù $R_1=R \cap \overbrace W$ a $R_2=R \cap W$. Dle indukèního
+Dále vytvoøíme mno¾iny vrcholù $R_1=R \cap \overline W$ a $R_2=R \cap W$. Dle indukèního
pøedpokladu ($R_1$ i $R_2$ jsou men¹í ne¾ $R$) existuje \PGHT{} $T_1=((R_1,F_1),C_1)$
pro $R_1$ na $G_1$ a $T_2=((R_2,F_2),C_2)$ pro $R_2$ na $G_2$.
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).
-Proto¾e byl $\d(W)$ minimální \st-øez a $\d(X)$ má men¹í kapacitu, $\d(X)$ nemù¾e separovat
+Proto¾e $\d(W)$ je minimální \st-øez a $\d(X)$ má men¹í kapacitu, $\d(X)$ nemù¾e separovat
$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$.
BÚNO nech» $X$ separuje $s$ a $r_1$.
-\medskip
-\centerline{\epsfysize=2.2cm\epsfbox{4-ght-rezx.eps}}
-\smallskip
+\fig{4-ght-rezx.eps}{12cm}
-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$.
-Tato hrana definuje øez $\d(U)$, co¾ je minimální $sr_1$-øez. Proto¾e $\d(X)$ je $sr_1$-øez,
+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$.
+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,
je $c(U) \le c(X) < c(W)$. Teï si staèí uvìdomit, ¾e $v_1\in C(r_1)$, tak¾e $\d(U)$
separuje nejenom $s$ a $r_1$, ale také $s$ a $v_1$. Tím pádem ale separuje také $s$ a $t$.
To je spor, proto¾e $c(U) < c(W)$, a pøitom $\d(W)$ mìl být minimální.
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
projects / ga.git / blobdiff