Ohodnoceni hran by pri hledani rezu mela byt nezaporna.

[ga.git] / 3-bipcon / 3-bipcon.tex

diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex
index eb96fa352b14a44dcac60c0b5fd9b78f7ae6e484..2393c5f089d53e08c9f0d8f7e6a695df9c11792b 100644 (file)
--- a/3-bipcon/3-bipcon.tex
+++ b/3-bipcon/3-bipcon.tex
@@ -9,13 +9,14 @@ kter
 \h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}}
 
 Nejprve si nadefinujme operaci {\I Degree Split,} která dostane jako vstup libovolný
-$2k$-regulární graf $G=(V,E)$ a rozdìlí ho na~podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$, které budou
+$2k$-regulární graf $G=(V,E)$ se sudým poètem hran a rozdìlí ho na~podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$, které budou
 oba $k$-regulární. Tuto operaci mù¾eme snadno provést v~lineárním èase tak, ¾e si graf
 rozdìlíme na~komponenty, v~ka¾dé nalezneme eulerovský tah a jeho sudé hrany dáme do~$G_1$
 a liché do~$G_2$.
 
 To nám pomù¾e ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^d$-regulárním
-bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta).}
+bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta),
+a ¾e takový graf má v¾dy sudý poèet hran.}
 Staèí provést Degree Split na~dva $2^{d-1}$-regulární grafy, na~libovolný jeden z~nich
 aplikovat dal¹í Degree Split atd., a¾ se dostaneme k~$1$-regulárnímu grafu, který
 je perfektním párováním v~$G$. To v¹e jsme schopni stihnout v~lineárním èase,
@@ -72,7 +73,7 @@ Pro minim
 
 \h{Globálnì minimální øez (Nagamochi, Ibaraki \cite{nagaiba:conn})}
 
-Buï $G$ neorientovaný graf s~ohodnocením na~hranách. Oznaèíme si:
+Buï $G$ neorientovaný graf s~nezáporným ohodnocením na~hranách. Oznaèíme si:
 
 \s{Znaèení:}