\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
\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$.
$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$ (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,