Sjednoceni znaceni kapacit mezi kapitolami 3 a 4.

[ga.git] / 4-ght / 4-ght.tex

diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex
index d396fecda31ac8e5489e39f446f7eb52ba51ba16..4d6f3345acebb7f61fe601f0c8b0783976a3e25b 100644 (file)
--- a/4-ght/4-ght.tex
+++ b/4-ght/4-ght.tex
@@ -21,7 +21,7 @@ cht
 
 \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))$.
 
 \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)$
 
 \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)$


@@ -52,8 +52,8 @@ $$r(x,z) \ge \min(r(x,y),r(y,z)).$$
 
 \fig{4-ght-rez.eps}{\epsfxsize}
 
 
 \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
 }
 
 \qed
 }
 


@@ -98,8 +98,8 @@ Nyn
 {\advance\hsize by -14em
 \:$t\not\in X$. Tehdy si v¹imneme, ¾e platí:
 $$\eqalignno{
 {\advance\hsize by -14em
 \:$t\not\in X$. Tehdy si v¹imneme, ¾e platí:
 $$\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ù.
 
 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ù.
 


@@ -123,15 +123,15 @@ Vid
 a navíc hrany mezi $U\setminus X$ a $X \setminus U$ poèítáme jenom vpravo. Nerovnost
 $(2)$ tedy platí.
 
 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
 \:$t\in X$. Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Tentokrát se budou
 hodit tyto nerovnosti:
 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
 \:$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)}$$
+$$\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ù.
 
 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ù.
 


@@ -146,7 +146,7 @@ U \setminus X&&&\hbox{---}&L_1,P_1\cr
 }$$
 
 Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme:
 }$$
 
 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
 z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez.
 \qeditem
 \endlist


@@ -235,9 +235,9 @@ B
 
 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,
 
 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$.
 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$,
 \qed
 
 Teï u¾ doká¾eme \GHT{} konstruovat efektivnì -- v~ka¾dém kroku vybereme dva vrcholy $s$ a $t$,