-\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ì souvilosti
-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
+\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Ä\8ditÄ\9b sudý poÄ\8det 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