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 bd5b8cf4a60b301f0443a7856f7572c42b2cdc09..5e988e66a897abbb50dc8fbb239ff12e099dadf8 100644 (file)
--- a/4-ght/4-ght.tex
+++ b/4-ght/4-ght.tex
@@ -1,31 +1,27 @@
-% Written by Milan Straka, 2006
-

 \def\li{\discretionary{-}{-}{-}li}
 \def\d{\delta}
 \def\st{$st$}
 \def\rr{$r_1r_2$}
 \def\GHT{GHT}
 \def\PGHT{ÈGHT}
 \def\li{\discretionary{-}{-}{-}li}
 \def\d{\delta}
 \def\st{$st$}
 \def\rr{$r_1r_2$}
 \def\GHT{GHT}
 \def\PGHT{ÈGHT}

-\def\th#1{\s{#1}}
-\def\proof{\noindent{\it Dùkaz:} }

 
 \input ../sgr.tex
 
 
 \input ../sgr.tex
 

-\prednaska{4}{Gomory-Hu Trees}{zapsal Milan Straka}
+\prednaska{4}{Gomory-Hu Trees}{}

 
 

-Cílem této kapitoly je vytvoøit datovou strukturu, která po urèitém
-pøedzpracování doká¾e rychle konstruovat pro libovolnou dvojici vrcholù v~grafu
-minimální øez, který ji oddìluje.
+Cílem této kapitoly je popsat datovou strukturu, která velice kompaktnì
+popisuje minimální $st$-øezy pro v¹echny dvojice vrcholù $s,t$ v~daném
+neorientovaném grafu. Tuto strukturu poprvé popsali Gomory a Hu v~èlánku \cite{gomoryhu}.

 
 Zatím umíme nalézt minimální \st-øez pro zadanou dvojici vrcholù v~neorientovaném
 grafu v~èase $\tau=\O(n^{2/3}m)$ pro~jednotkové kapacity, $\O(n^2m)$ pro obecné.
 Nalézt minimální \st-øez pro ka¾dou dvojici vrcholù
 bychom tedy dokázali v~èase $\O(n^2\tau)$. Tento výsledek budeme
 
 Zatím umíme nalézt minimální \st-øez pro zadanou dvojici vrcholù v~neorientovaném
 grafu v~èase $\tau=\O(n^{2/3}m)$ pro~jednotkové kapacity, $\O(n^2m)$ pro obecné.
 Nalézt minimální \st-øez pro ka¾dou dvojici vrcholù
 bychom tedy dokázali v~èase $\O(n^2\tau)$. Tento výsledek budeme

-chtít zlep¹it. \cite{gomoryhu}
+chtít zlep¹it.

 
 \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)$


@@ -33,30 +29,32 @@ pro n
 
 \h{Gomory-Hu Tree}
 
 
 \h{Gomory-Hu Tree}
 

-\s{Definice:} {\I Gomory-Hu Tree} (dále jen \GHT) pro neorientovaný ohodnocený graf $G=(V,E)$
-je strom $T=(V,F)$ takový,\nobreak{}\ \nobreak{}¾e $$\forall st \in F: \d(K_1)=\d(K_2)\hbox{ je minimální \st-øez, kde
-$K_1$ a $K_2$ jsou komponenty $T\setminus st$}.$$
-Pozor, $F$ nemusí být podmno¾ina pùvodních hran $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$.]

 
 \s{Dal¹í znaèení:} Pro $e\in F$ budeme øezem $\d(e)$ oznaèovat øez $\d(K_1)=\d(K_2)$ a $r(e)$ bude jeho kapacita.
 
 
 \s{Dal¹í znaèení:} Pro $e\in F$ budeme øezem $\d(e)$ oznaèovat øez $\d(K_1)=\d(K_2)$ a $r(e)$ bude jeho kapacita.
 

-\>K~èemu takový \GHT{} je (existuje-li)? To nám poví následující
+\>K~èemu takový \GHT{} je (existuje-li)? To nám poví následující vìta:

 
 

-\th{Vìta (o~vyu¾ití \GHT):} Buï $T=(V,F)$ \GHT{} pro graf $G=(V,E)$ a mìjme dva vrcholy $s$ a $t$. Dále
+\s{Vìta (o~vyu¾ití \GHT):} Buï $T$ libovolný \GHT{} pro graf~$G$ a mìjme dva vrcholy $s$ a $t$. Dále

 nech» $P$ je cesta v~$T$ mezi vrcholy $s$ a $t$ a $e$ je hrana na cestì $P$ s~minimálním $r(e)$.
 nech» $P$ je cesta v~$T$ mezi vrcholy $s$ a $t$ a $e$ je hrana na cestì $P$ s~minimálním $r(e)$.

-Pak $\d(e)$ je minimální \st-øez.
+Pak $\d(e)$ je minimální \st-øez v~$G$.

 
 

-\proof Nejprve si doká¾eme jedno drobné
+\proof Nejprve si doká¾eme jedno drobné lemmátko:

 
 

-{\advance\leftskip by 2em
-\th{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e $r(x,z) \ge \min(r(x,y),r(y,z))$.
+{\advance\leftskip by 2em\advance\rightskip by 2em
+\s{Lemmátko:} Pro ka¾dou trojici vrcholù $x,y,z$ platí, ¾e:
+$$r(x,z) \ge \min(r(x,y),r(y,z)).$$

 
 \proof Buï $W$ minimální $xz$-øez.
 
 
 \proof Buï $W$ minimální $xz$-øez.
 

-\centerline{\epsfysize=1.5cm\epsfbox{4-ght-rez.eps}}
+\fig{4-ght-rez.eps}{\epsfxsize}

 
 

-\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
+\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

 }
 
 \noindent Zpìt k~dùkazu vìty:
 }
 
 \noindent Zpìt k~dùkazu vìty:


@@ -64,13 +62,14 @@ Chceme dok
 Minimalitu doká¾eme indukcí podle délky cesty $P$:
 \itemize\ibull
 \:$\vert\,P\,\vert = 1$: Hrana $e$ je v~tomto pøípadì pøímo $st$, tak¾e i minimalita plyne z~definice \GHT.
 Minimalitu doká¾eme indukcí podle délky cesty $P$:
 \itemize\ibull
 \:$\vert\,P\,\vert = 1$: Hrana $e$ je v~tomto pøípadì pøímo $st$, tak¾e i minimalita plyne z~definice \GHT.

-\:$\vert\,P\,\vert > 1$: Cesta $P$ spojuje vrcholy $s$ a $t$, její první hrana je $sx$.
+\:$\vert\,P\,\vert > 1$: Cesta $P$ spojuje vrcholy $s$ a $t$, její první hranu oznaème $sx$.

 Na¹e právì dokázané lemmátko øíká, ¾e $r(s,t) \ge \min (r(s,x),r(x,t))$.
 Urèitì je pravda, ¾e $r(s,x) \ge r(e)$, proto¾e $e$ byla hrana cesty $P$ s~nejmen¹ím $r(e)$.
 To, ¾e $r(x,t) \ge r(e)$, plyne z~indukèního pøedpokladu, proto¾e cesta mezi $x$ a $t$
 je krat¹í ne¾ cesta $P$. Dostáváme tak, ¾e $r(s,t) \ge \min(r(s,x),r(x,t)) \ge r(e)$.
 Na¹e právì dokázané lemmátko øíká, ¾e $r(s,t) \ge \min (r(s,x),r(x,t))$.
 Urèitì je pravda, ¾e $r(s,x) \ge r(e)$, proto¾e $e$ byla hrana cesty $P$ s~nejmen¹ím $r(e)$.
 To, ¾e $r(x,t) \ge r(e)$, plyne z~indukèního pøedpokladu, proto¾e cesta mezi $x$ a $t$
 je krat¹í ne¾ cesta $P$. Dostáváme tak, ¾e $r(s,t) \ge \min(r(s,x),r(x,t)) \ge r(e)$.

+\qeditem

 \endlist
 \endlist

-\qed
+

 Pokud doká¾eme \GHT{} sestrojit, nalézt minimální \st-øez pro libovolnou dvojici vrcholù
 doká¾eme stejnì rychle jako nalézt hranu s~nejmen¹í kapacitou na cestì mezi $s$ a $t$ v~\GHT.
 K~tomu mù¾eme pou¾ít napøíklad Sleator-Tarjanovy stromy, které tuto operaci
 Pokud doká¾eme \GHT{} sestrojit, nalézt minimální \st-øez pro libovolnou dvojici vrcholù
 doká¾eme stejnì rychle jako nalézt hranu s~nejmen¹í kapacitou na cestì mezi $s$ a $t$ v~\GHT.
 K~tomu mù¾eme pou¾ít napøíklad Sleator-Tarjanovy stromy, které tuto operaci


@@ -84,32 +83,31 @@ p
 Nyní se nauèíme \GHT{} konstruovat, èím¾ také rozptýlíme obavy o~jejich existenci.
 Nejprve v¹ak budeme potøebovat jedno u¾iteèné lemma s~hnusnì technickým dùkazem:
 
 Nyní se nauèíme \GHT{} konstruovat, èím¾ také rozptýlíme obavy o~jejich existenci.
 Nejprve v¹ak budeme potøebovat jedno u¾iteèné lemma s~hnusnì technickým dùkazem:
 

-\vbox to 0pt{\vskip-\baselineskip\rightline{\epsfysize=2cm\epsfbox{4-ght-htl.eps}}\vss}\vskip-\baselineskip
-{
-\advance\rightskip by 17em
-\th{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$.]
+\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.
+\foot{To dùle¾ité a netriviální je, ¾e celá $W$ le¾í v~$U$.}
+
+\fig{4-ght-htl.eps}{\epsfxsize}

 
 \proof Nech» je $\d(X)$ minimální $uv$-øez.
 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.
 
 
 \proof Nech» je $\d(X)$ minimální $uv$-øez.
 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{\vskip -1cm\rightline{\epsfysize=2.5cm\epsfbox{4-ght-htl-a.eps}}\vss}\vskip-\baselineskip
-{\advance\hsize by -14em
-\:$t\not\in X$.\par
-Doká¾eme dvì nerovnosti. Nerovnost $$\eqalignno{c(U \cup X) &\ge c(U)&(1)}$$
-platí proto, ¾e $U \cup X$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í
-$$\eqalignno{c(U \cap X) + c(U \cup X) &\le c(U) + c(X)&(2)}$$
-doká¾eme \uv{rozborem pøípadù}.
+\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í>$.
 
 Mno¾inu vrcholù si disjunktnì rozdìlíme na $X\setminus U$, $X \cap U$, $U \setminus X$ a $\<ostatní>$.

-Ka¾dý z~øezù v~nerovnosti $(2)$ se skládá z~hran mezi tìmito skupinami vrcholù.
+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ù.

 Vytvoøíme tedy tabulku hran mezi ètyømi oznaèenými skupinami vrcholù a ka¾dému
 øezu z~$(2)$ oznaèíme jemu odpovídající hrany. Proto¾e je graf neorientovaný,
 staèí nám jen horní trojúhelník tabulky.
 Vytvoøíme tedy tabulku hran mezi ètyømi oznaèenými skupinami vrcholù a ka¾dému
 øezu z~$(2)$ oznaèíme jemu odpovídající hrany. Proto¾e je graf neorientovaný,
 staèí nám jen horní trojúhelník tabulky.


@@ -125,18 +123,17 @@ 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.
 
 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$.\par
-Postupovat budeme obdobnì jako v~pøedchozím pøípadì. Nerovnost $$\eqalignno{c(X \setminus U) &\ge c(U)&(3)}$$
-platí proto, ¾e $X \setminus U$ je nìjaký \st-øez, zatímco $U$ je minimální \st-øez. Dal¹í
-$$\eqalignno{c(U \setminus X) + c(X \setminus U) &\le c(U) + c(X)&(4)}$$
-doká¾eme opìt \uv{rozborem pøípadù}.
-
-}
+\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}
 
 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}


@@ -146,84 +143,86 @@ U \setminus X&&&\hbox{---}&L_1,P_1\cr
 \<ostatní>&&&&\hbox{---}\cr
 }$$
 
 \<ostatní>&&&&\hbox{---}\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),$$
+Stejnì jako v~pøedchozím pøípadì nerovnost $(4)$ platí. Odeètením $(4)$ a $(3)$ získáme:
+$$d(U \setminus X) \le d(X),$$

 z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez.
 z~èeho¾ opìt dostaneme, ¾e $\d(U \setminus X)$ je také minimální $uv$-øez.

+\qeditem

 \endlist
 \endlist

-\qed

 
 \bigskip
 \>Nyní se koneènì dostáváme ke konstrukci \GHT{}. Abychom mohli pou¾ívat
 indukci, zavedeme si trochu obecnìj¹í \GHT{}.
 
 
 \bigskip
 \>Nyní se koneènì dostáváme ke konstrukci \GHT{}. Abychom mohli pou¾ívat
 indukci, zavedeme si trochu obecnìj¹í \GHT{}.
 

-\s{Definice:} Mìjme neorientovaný graf $(V,E)$. {\I Èásteèný Gomory-Hu Tree} (alias \PGHT{}) pro $R \subseteq V$ je $((R,F),C)$,
-kde $(R,F)$ je strom a mno¾ina $C=\{C(r) \;\vert\; r\in R\}$ je rozklad vrcholù $V$. Tento rozklad
+\s{Definice:} Mìjme neorientovaný graf $(V,E)$. {\I Èásteèný Gomory-Hu Tree} (alias \PGHT{}) pro podmno¾inu vrcholù $R \subseteq V$ je dvojice $((R,F),C)$,
+kde $(R,F)$ je strom a mno¾ina $C=\{C(r) \;\vert\; r\in R\}$ je rozklad mno¾iny vrcholù $V$. Tento rozklad

 nám øíká, k~jakým vrcholùm \PGHT{} máme pøilepit které vrcholy pùvodního grafu.
 Navíc musí platit, ¾e:\numlist\ndotted
 nám øíká, k~jakým vrcholùm \PGHT{} máme pøilepit které vrcholy pùvodního grafu.
 Navíc musí platit, ¾e:\numlist\ndotted

-\:$\forall r: r\in C(r)$, neboli ka¾dý vrchol \PGHT{} je pøilepen sám k~sobì,
-\:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right)
-\hbox{ je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$}.$
+\:$\forall r: r\in C(r)$, neboli ka¾dý vrchol \PGHT{} je pøilepen sám k~sobì, a
+\:$\forall st \in F: \d\left(\bigcup_{r\in K_1} C(r)\right)=\d\left(\bigcup_{r\in K_2} C(r)\right)$
+je minimální \st-øez, kde $K_1$ a $K_2$ jsou komponenty $(R,F) \setminus st$.

 \endlist
 
 
 \endlist
 
 

-\th{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
 \:$\vert R \vert = 1$: \PGHT{} má jediný vrchol $r\in R$ a $C(r)=V$.
 \:$\vert R \vert > 1$: Najdeme dvojici vrcholù $s,t\in R$ takovou, ¾e jejich minimální \st-øez $\d(W)$
 existuje \PGHT{}.
 
 \proof Doká¾eme indukcí podle velikosti mno¾iny $R$.\itemize\ibull
 \:$\vert R \vert = 1$: \PGHT{} má jediný vrchol $r\in R$ a $C(r)=V$.
 \:$\vert R \vert > 1$: Najdeme dvojici vrcholù $s,t\in R$ takovou, ¾e jejich minimální \st-øez $\d(W)$

-je nejmen¹í mo¾ný. Nyní vytvoøíme graf $G_1$ z~grafu $G$ zkontrahováním
-v¹ech vrcholù $w\in W$ do jednoho vrcholu, který oznaèíme $v_1$, a vytvoøíme graf $G_2$ z~$G$ zkontrahováním
-v¹ech vrcholù $w\in \overline W$ do jednoho vrcholu $v_2$.\foot{
+je nejmen¹í mo¾ný. Nyní vytvoøíme graf $G_1$ z~grafu $G$ kontrahováním
+v¹ech vrcholù mno¾iny~$W$ do~jednoho vrcholu, který oznaèíme~$v_1$, a vytvoøíme graf $G_2$ z~$G$ kontrahováním
+v¹ech vrcholù z~$\overline W$ do jednoho vrcholu $v_2$.\foot{

 Proè to dìláme \uv{tak slo¾itì} a pøidáváme do $G_1$ vrchol $v_1$? Na první pohled to pøeci vypadá zbyteènì.
 Problém je v~tom, ¾e i kdy¾ dle HTL le¾í v¹echny minimální øezy oddìlující vrcholy z~$W$ v~mno¾inì vrcholù
 $W$, \<hrany> tìchto øezù celé v~podgrafu indukovaném~$W$ le¾et nemusí. K~tìmto øezùm toti¾ patøí i hrany, které
 Proè to dìláme \uv{tak slo¾itì} a pøidáváme do $G_1$ vrchol $v_1$? Na první pohled to pøeci vypadá zbyteènì.
 Problém je v~tom, ¾e i kdy¾ dle HTL le¾í v¹echny minimální øezy oddìlující vrcholy z~$W$ v~mno¾inì vrcholù
 $W$, \<hrany> tìchto øezù celé v~podgrafu indukovaném~$W$ le¾et nemusí. K~tìmto øezùm toti¾ patøí i hrany, které

-mají ve $W$ jenom jeden konec. Proto jsme do $G_1$ pøidali $v_1$, vedou do nìj v¹echny zajímavé
+mají ve $W$ jenom jeden konec. Proto jsme do $G_1$ pøidali $v_1$ -- do~nìj vedou v¹echny zajímavé

 hrany, které mají ve $W$ jeden konec. Tím {\I zajímavé} myslíme to, ¾e z~ka¾dého vrcholu $w\in W$ vede
 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.}
 
 hrany, které mají ve $W$ jeden konec. Tím {\I zajímavé} myslíme to, ¾e z~ka¾dého vrcholu $w\in W$ vede
 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-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 \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$.
 
 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)$,
-obdobnì $r_2$. Oba \PGHT{} $T_1$ a $T_2$ spojíme hranou $r_1r_2$, tak¾e \PGHT{} pro $G$
-je $T=((R_1 \cup R_2,F_1 \cup F_2 \cup {r_1r_2}),C)$, pøièem¾ pro $r\in R_1$ je $C(r)=C_1(r)\setminus\{v_1\}$
-a pro $r\in R_2$ je $C(r)=C_2(r)\setminus\{v_2\}$ [odebrali jsme vrcholy $v_1$ a $v_2$ z~rozkladu $C$].
+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$].

 
 Chceme ukázat, ¾e tento $T$ je opravdu \PGHT. $C$ je urèitì rozklad v¹ech vrcholù a ka¾dé
 
 Chceme ukázat, ¾e tento $T$ je opravdu \PGHT. $C$ je urèitì rozklad v¹ech vrcholù a ka¾dé

-$r\in C(r)$ z~indukèního pøedpokladu, tak¾e podmínka $1.$ je splnìna. Co se týèe podmínky $2.$, tak\itemize\ibull
+$r\in C(r)$ z~indukèního pøedpokladu, tak¾e podmínka~1 je splnìna. Co se týèe podmínky~2, tak:
+\itemize\ibull

 \:pro hranu \rr\ je $\d(W)$ urèitì minimální \rr-øez, proto¾e øez mezi $s$ a $t$ je souèasnì
 i \rr-øezem a je ze v¹ech mo¾ných minimálních øezù na $R$ nejmen¹í,
 \:pro hranu $e\ne r_1r_2$ je $\d(e)$ z~indukce minimální øez na jednom z~grafù $G_1$, $G_2$.
 \:pro hranu \rr\ je $\d(W)$ urèitì minimální \rr-øez, proto¾e øez mezi $s$ a $t$ je souèasnì
 i \rr-øezem a je ze v¹ech mo¾ných minimálních øezù na $R$ nejmen¹í,
 \:pro hranu $e\ne r_1r_2$ je $\d(e)$ z~indukce minimální øez na jednom z~grafù $G_1$, $G_2$.

-Tento øez také pøesnì odpovídá øezu v~grafu $G$, proto¾e v~$G_1$ i v~$G_2$ jsme poèítali
-s~hranami vedoucími do $v_1$, $v_2$ a proto¾e jsme \PGHT{} napojili pøes vrcholy,
+Tento øez také pøesnì odpovídá øezu v~grafu~$G$, proto¾e v~$G_1$ i v~$G_2$ jsme poèítali
+s~hranami vedoucími do~$v_1$, $v_2$ a proto¾e jsme \PGHT{} napojili pøes vrcholy,

 k~nim¾ byly $v_1$ a $v_2$ pøilepeny.
 
 HTL nám navíc øíká, ¾e existuje minimální øez, který ¾ije pouze v~pøíslu¹ném z~grafù $G_1$, $G_2$,
 tak¾e nalezený øez je minimální pro celý graf $G$.
 k~nim¾ byly $v_1$ a $v_2$ pøilepeny.
 
 HTL nám navíc øíká, ¾e existuje minimální øez, který ¾ije pouze v~pøíslu¹ném z~grafù $G_1$, $G_2$,
 tak¾e nalezený øez je minimální pro celý graf $G$.

+\qeditem

 \endlist
 \endlist
 \endlist
 \endlist

-\qed

 
 Nyní víme, ¾e \GHT{} existují, a také víme, jak by se daly konstruovat. Nicménì nalezení
 vrcholù $s,t$ tak, aby byl minimální \st-øez nejmen¹í mo¾ný, je èasovì nároèné.
 Proto si poslední vìtu je¹tì o~nìco vylep¹íme.
 
 
 Nyní víme, ¾e \GHT{} existují, a také víme, jak by se daly konstruovat. Nicménì nalezení
 vrcholù $s,t$ tak, aby byl minimální \st-øez nejmen¹í mo¾ný, je èasovì nároèné.
 Proto si poslední vìtu je¹tì o~nìco vylep¹íme.
 

-\th{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$ a $t$
+\s{Vylep¹ení vìty o~existenci \PGHT{}:} Na zaèátku dùkazu není nutné hledat vrcholy $s$~a~$t$

 takové, aby byl minimální \st-øez nejmen¹í mo¾ný. Staèí zvolit \<libovolné> vrcholy $s,t\in R$
 takové, aby byl minimální \st-øez nejmen¹í mo¾ný. Staèí zvolit \<libovolné> vrcholy $s,t\in R$

-a nalézt minimální øez $\d(W)$.
+a zvolit $\d(W)$ jako minimální \st-øez.

 
 \proof Nejprve si uvìdomme, proè jsme v~pøedchozím dùkazu potøebovali, aby byl $\d(W)$ nejmen¹í ze v¹ech
 mo¾ných \st-øezù. Bylo to jenom proto, ¾e jsme jím v~\PGHT{} nakonec separovali vrcholy $r_1$ a $r_2$
 a potøebovali jsme záruku, aby byl $\d(W)$ opravdu minimální \rr-øez. Nyní musíme ukázat,
 ¾e námi nalezený \st-øez $\d(W)$ je také minimálním \rr-øezem.
 
 
 \proof Nejprve si uvìdomme, proè jsme v~pøedchozím dùkazu potøebovali, aby byl $\d(W)$ nejmen¹í ze v¹ech
 mo¾ných \st-øezù. Bylo to jenom proto, ¾e jsme jím v~\PGHT{} nakonec separovali vrcholy $r_1$ a $r_2$
 a potøebovali jsme záruku, aby byl $\d(W)$ opravdu minimální \rr-øez. Nyní musíme ukázat,
 ¾e námi nalezený \st-øez $\d(W)$ je také minimálním \rr-øezem.
 

-Pro spor tedy pøedpokládejme, ¾e minimální \rr-øez $\d(X)$ má men¹í kapacitu ne¾ $\d(W)$.
+Pro spor tedy pøedpokládejme, ¾e nìjaký \rr-øez $\d(X)$ má men¹í kapacitu ne¾ $\d(W)$.

 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).
 
 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).
 


@@ -231,15 +230,13 @@ 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$.
 
 $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,
 
 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$,


@@ -247,7 +244,5 @@ nalezneme v~
 zpracujeme rekurzivnì. Celou výstavbu tedy zvládneme v~èase $\O(n\tau)$, èili $\O(n^{5/3}m)$
 pro neohodnocené grafy.
 
 zpracujeme rekurzivnì. Celou výstavbu tedy zvládneme v~èase $\O(n\tau)$, èili $\O(n^{5/3}m)$
 pro neohodnocené grafy.
 

-\todo{Odkazy na rychlej¹í algoritmy}
-

 \references
 \bye
 \references
 \bye