-\prednaska{3}{Bipartitní párování a globální k-souvislost}{zapsali Jiøí Peinlich, Michal Kùrka}
-
-\>V~minulé kapitole jsme se zabývali aplikacemi tokù na~hledání maximálního párování
-a minimálního øezu. V~této si pøedvedeme dva algoritmy pro podobné problémy,
-které se obejdou bez tokù.
-
-\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
-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).}
-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,
-jeliko¾ velikosti grafù, které splitujeme, exponenciálnì klesají. Také bychom
-mohli rekurzivnì zpracovávat obì komponenty a tak se v~èase $\O(m\log n)$ dobrat
-ke~kompletní 1-faktorizaci zadaného grafu.\foot{To je rozklad hran grafu na~disjunktní
-perfektní párování a má ho ka¾dý regulární bipartitní graf.}
-
-Pokud zadaný graf nebude $2^d$-regulární, pomù¾eme si tím, ¾e ho novými hranami
-doplníme na $2^d$-regulární a pak si pøi splitech budeme vybírat ten podgraf,
-do~kterého padlo ménì nových hran, a uká¾eme, ¾e nakonec v¹echny zmizí.
-Abychom graf pøíli¹ nezvìt¹ili, budeme sna¾it místo pøidávání úplnì nových
-hran pouze zvy¹ovat násobnost hran existujících. Pro ka¾dou hranu $e$ si tedy
-budeme pamatovat její násobnost $n(e)$.
-
-{\I Degree Split grafu s~násobnostmi} pak budeme provádìt následovnì: hranu~$e$ s~násobností $n(e)$ umístíme do~$G_1$
-i~do~$G_2$ s~násobností $\lfloor n(e)/2 \rfloor$ a pokud bylo $n(e)$ liché, pøidáme hranu do~pomocného grafu
-$G^\prime$. V¹imnìte si, ¾e $G^\prime$ bude sudì-regulární graf bez násobností, tak¾e na~nìj mù¾eme aplikovat pùvodní
-Degree Split a $G^\prime_i$ pøiøadit ke~$G_i$. To~v¹e zvládneme v~èase $\O(m)$.
-
-Mìjme nyní $k$-regulární bipartitní graf. Zvolme $t$ tak aby $2^t\geq kn$.
-Zvolme dále parametry
+\prednaska{3}{Bipartitní párování a globální k-souvislost}{}
+
+V~předešlých kapitolách jsme se zabývali aplikacemi toků na~hledání maximálního párování
+a minimálního $st$-řezu. Nyní si předvedeme dva algoritmy pro podobné problémy,
+které se obejdou bez toků.
+
+\h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}}
+
+Nejprve si nadefinujme operaci {\I štěpení grafu,} která zadaný graf $G=(V,E)$
+se všemi vrcholy sudého stupně a sudým počtem hran v~každé komponentě souvislosti
+rozloží na~disjunktní podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$,
+v~nichž bude pro každý vrchol~$v$ platit ${\rm deg}_{G_1}(v) = {\rm
+deg}_{G_2}(v) = {\rm deg}_G(v)/2$. 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 hrany budeme přidávat střídavě do~$G_1$ a do~$G_2$.
+
+Štěpení nám pomůže ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^t$-regulárním
+bipartitním grafu.\foot{Všimněte si, že takové párování bude vždy perfektní (viz Hallova věta).}
+Komponenty takového grafu mají určitě sudý počet hran, takže jej můžeme
+rozštěpit na~dva $2^{t-1}$-regulární grafy. Libovolný jeden z~nich pak opět rozštěpíme
+atd., až dostaneme $1$-regulární graf, který je perfektním párováním v~$G$.
+To vše jsme schopni stihnout v~lineárním čase, jelikož velikosti grafů, které
+štěpíme, exponenciálně klesají. Také bychom mohli rekurzivně zpracovávat obě
+části a tak se v~čase $\O(m\log n)$ dobrat ke~kompletní 1-faktorizaci
+zadaného grafu.\foot{To je rozklad hran grafu na~disjunktní perfektní párování
+a má ho každý regulární bipartitní graf.}
+
+Pokud zadaný graf nebude $2^t$-regulární, pomůžeme si tím, že ho novými hranami
+doplníme na $2^t$-regulární a pak si při štěpeních budeme vybírat ten podgraf,
+do~kterého padlo méně nových hran, a ukážeme, že nakonec všechny zmizí.
+Abychom graf příliš nezvětšili, budeme se snažit místo přidávání úplně nových
+hran pouze zvyšovat násobnost hran existujících. Pro každou hranu $e$ si tedy
+budeme pamatovat její násobnost $n(e)$.
+
+{\I Štěpení grafu s~násobnostmi} pak budeme provádět následovně: hranu~$e$
+s~násobností $n(e)$ umístíme do~$G_1$ i~do~$G_2$ s~násobností $\lfloor n(e)/2
+\rfloor$ a pokud bylo $n(e)$ liché, přidáme hranu do~pomocného grafu
+$G^\prime$. Všimněte si, že $G^\prime$ bude graf bez násobností, v~němž mají
+všechny vrcholy sudý stupeň, takže na~něj můžeme aplikovat původní štěpící algoritmus
+a $G^\prime_i$ přiřadit ke~$G_i$. To~vše zvládneme v~čase $\O(m)$.
+
+Mějme nyní $k$-regulární bipartitní graf. Obě jeho partity jsou stejně velké,
+označme si počet vrcholů v~každé z~nich~$n$. Zvolme $t$ tak aby $2^t\geq kn$.
+Zvolme dále parametry