\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))$.
-Kapacitu øezu $\d(W)$ budeme znaèit $c(W)$ a $r(s,t)$ bude kapacita nejmen¹ího \st-øezu.
+Kapacitu øezu $\d(W)$ budeme znaèit $d(W)$ a $r(s,t)$ bude kapacita nejmen¹ího \st-øezu.
\s{Pozorování:} Minimální øez rozdìluje graf jen na~dvì komponenty (v¹imnìte si, ¾e pro
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)$
\h{Gomory-Hu Tree}
-\s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný ohodnocený graf $G=(V,E)$
+\s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný nezápornì ohodnocený graf $G=(V,E)$
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$.]
\fig{4-ght-rez.eps}{\epsfxsize}
-\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)$.
+\noindent Vrchol $y$ musí být v~jedné z~komponent, Pokud je v~komponentì s~$x$, pak $r(y,z) \le d(W)$,
+proto¾e $\d(W)$ je také $yz$-øez. Pokud v~té druhé, analogicky platí $r(x,y) \le d(W)$.
\qed
}
Nejprve v¹ak budeme potøebovat jedno u¾iteèné lemma s~hnusnì technickým dùkazem:
\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é
-vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální $uv$-øez.
-[To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.]
+vrcholy z~$U$. Pak existuje mno¾ina vrcholù $W \subseteq U$ taková, ¾e $\d(W)$ je minimální $uv$-øez.
+\foot{To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.}
\fig{4-ght-htl.eps}{\epsfxsize}
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$.
Pokud by tomu tak nebylo, mù¾eme vrcholy pøeznaèit nebo nìkterou z~mno¾in nahradit jejím doplòkem.
-Nyní mohou nastat dva pøípady:\numlist\nalpha
-\vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip
-{\advance\hsize by -14em
+\checkroom{40pt}
+
+Nyní mohou nastat následující dva pøípady:\numlist\nalpha
+\vbox to 0pt{\vskip 10pt\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip
\:$t\not\in X$. Tehdy si v¹imneme, ¾e platí:
+\hangindent=-14em\hangafter=-100
$$\eqalignno{
-c(U \cup X) &\ge c(U),&(1) \cr
-c(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$
+d(U \cup X) &\ge d(U),&(1) \cr
+d(U \cap X) + d(U \cup X) &\le d(U) + d(X)&(2)}$$
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 $\<ostatní>$.
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ù.
a navíc hrany mezi $U\setminus X$ a $X \setminus U$ poèítáme jenom vpravo. Nerovnost
$(2)$ tedy platí.
-Nyní staèí nerovnosti $(2)$ a $(1)$ odeèíst, èím¾ získáme: $$c(U \cap X) \le c(X),$$
+Nyní staèí nerovnosti $(2)$ a $(1)$ odeèíst, èím¾ získáme: $$d(U \cap X) \le d(X),$$
co¾ spolu s~obrázkem dokazuje, ¾e $\d(U \cap X)$ je také minimální $uv$-øez.
-\vbox to 0pt{\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.eps}}\vss}\vskip-\baselineskip
-{\advance\hsize by -14em\itemcount=1
+\vbox to 0pt{\vskip 20pt\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-b.eps}}\vss}\vskip-\baselineskip
\:$t\in X$. Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Tentokrát se budou
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)}$$
+\hangindent=-14em\hangafter=-100
+$$\eqalignno{d(X \setminus U) &\ge d(U)&(3)\cr
+d(U \setminus X) + d(X \setminus U) &\le d(U) + d(X)&(4)}$$
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ù.
-}
-
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:
$$\matrix{&X\setminus U&X \cap U&U \setminus X&\<ostatní>\cr\noalign{\smallskip}
X\setminus U&\hbox{---}&L_2,P_1&L_1,L_2,P_1,P_2&L_2,P_2\cr
}$$
Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme:
-$$c(U \setminus X) \le c(X),$$
+$$d(U \setminus X) \le d(X),$$
z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez.
\qeditem
\endlist
\endlist
-\s{Vìta (o~existenci \PGHT{}):} Buï $(V,E)$ neorientovaný ohodnocený graf. Pro ka¾dou podmno¾inu vrcholù $R$
+\s{Vìta (o~existenci \PGHT{}):} Buï $(V,E)$ neorientovaný nezápornì ohodnocený graf. Pro ka¾dou podmno¾inu vrcholù $R$
existuje \PGHT{}.
\proof Doká¾eme indukcí podle velikosti mno¾iny $R$.\itemize\ibull
\fig{4-ght-g1g2-before.eps}{0.45\hsize}
\fig{4-ght-g1g2-after.eps}{0.9\hsize}
+\finalfix{\bigskip}
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$.
-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)$,
+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)$,
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$].
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)$
+je $d(U) \le d(X) < d(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í.
+To je spor, proto¾e $d(U) < d(W)$, a pøitom $\d(W)$ mìl být minimální.
\qed
Teï u¾ doká¾eme \GHT{} konstruovat efektivnì -- v~ka¾dém kroku vybereme dva vrcholy $s$ a $t$,
projects / ga.git / blobdiff