Posledni kousky Q-Heapu a jejich aplikace na kostry.

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

diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex
index 6e599c6561b9715ed3c309f2a98f0778fa9b9f60..edd3578c71cfe1a64d1256cf6252870c98539363 100644 (file)
--- a/4-ght/4-ght.tex
+++ b/4-ght/4-ght.tex
@@ -53,7 +53,7 @@ Pak $\d(e)$ je minim
 
 \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
@@ -183,10 +183,9 @@ hrany, kter
 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$.
 
@@ -231,9 +230,7 @@ Proto
 $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,