\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,
\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í:}
nerovnost plyne z~legálnosti uspoøádání.
Chceme ukázat, ¾e velikost na¹eho øezu~$C$ je alespoò taková, jako velikost øezu kolem vrcholu $v_n$.
-V¹imneme si, ¾e $ \vert C \vert \geq \sum_{i=1}^{n-1} d(v_i,u_i)$. Uká¾eme, ¾e pravá strana je alespoò $d(v_n)$:
+V¹imneme si, ¾e $\vert C \vert \geq \sum_{i=1}^{n-1} d(v_i,u_i)$. Hrany mezi $v_i$ a $u_i$ jsou toti¾ navzájem
+rùzné a ka¾dá z~nich je souèástí øezu~$C$. Uká¾eme, ¾e pravá strana je alespoò $d(v_n)$:
$$\eqalign{
\sum_{i=1}^{n-1} d(v_i,u_i) &= \sum_{i=1}^{n-1} d(\{v_1\ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_i) \geq \cr
&\geq \sum_{i=1}^{n-1} d(\{v_1 \ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_{i-1}) = \cr