From d52f9cf66604dc7445d2299d12cd85c38199790d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 9 Nov 2006 18:38:59 +0100 Subject: [PATCH] Bug fixes. --- 4-ght/4-ght.tex | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/4-ght/4-ght.tex b/4-ght/4-ght.tex index 824c09b..44127b0 100644 --- a/4-ght/4-ght.tex +++ b/4-ght/4-ght.tex @@ -227,7 +227,7 @@ Pro spor tedy p Navíc vezmìme ten pøípad, kdy se to stalo \uv{poprvé}, tak¾e pro ka¾dé men¹í $R$ je v¹echno v~poøádku (to mù¾eme, proto¾e pro $\vert R \vert=1$ v¹echno v~poøádku bylo). -Proto¾e byl $\d(W)$ minimální \st-øez a $\d(X)$ má men¹í kapacitu, $\d(X)$ nemù¾e separovat +Proto¾e $\d(W)$ je minimální \st-øez a $\d(X)$ má men¹í kapacitu, $\d(X)$ nemù¾e separovat $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$. @@ -235,8 +235,8 @@ B \centerline{\epsfysize=2.2cm\epsfbox{4-ght-rezx.eps}} \smallskip -Podívejme se nyní na \PGHT{} $T_1$ 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. 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)$ 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í. -- 2.39.5