Knizka: Sazba pracovni verze

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

diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex
index 313dc540b141dec21cd256e72f0eedc983c3724c..5e988e66a897abbb50dc8fbb239ff12e099dadf8 100644 (file)
--- a/4-ght/4-ght.tex
+++ b/4-ght/4-ght.tex
@@ -84,8 +84,8 @@ Nyn
 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}
 
@@ -93,18 +93,18 @@ vrcholy z~$U$. Pak existuje mno
 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{
 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ù.
@@ -126,17 +126,15 @@ $(2)$ tedy plat
 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:
+\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
@@ -184,6 +182,7 @@ do t
 
 \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)$