-\prednaska{3}{Bipartitní párování a globální k-souvislost}{zapsali Jiøí Peinlich, Michal Kùrka}
-
-\h{Maximální párování v $k$-regulárním bipartitním grafu}
-
-\s{Operace Degree Split} provádí rozdìlení sudì-regulárního grafu na dva
-podgrafy s polovièní regularitou. Operaci Degree Split definujme na
-sudì-regulárním grafu takto: V grafu najdeme eulerovský tah. Sestrojíme dva
-grafy, které budou mít oba stejnou mno¾inu vrcholù jako graf pùvodní a ka¾dý
-bude mít polovinu jeho hran. Mno¾inu hran prvního grafu budou tvoøit sudé hrany
-z nalezeného eulerovského tahu, mno¾inu hran druhého grafu pak hrany liché. Tuto
-operaci lze jistì provést v lineárním èase (v lineárním èase najdeme eulerovský
-tah i rozklad na sudé a liché hrany).
-
-Dále budeme pracovat s $2^d$-regulárními grafy. Operací Degree Split tedy získáme dva grafy, které budou $2^{d-1}$-regulární.
-
-Provedeme-li operaci Degree Split $\log k = d$ krát (polovinu hran v¾dy
-zahodíme), získáme 1-regulární podgraf a tedy párování pro zadaný graf (ve
-skuteènosti mù¾eme graf rozkládat na párování a vyrobit si 1-faktorizaci
-grafu). Slo¾itost nalezení párování bude tedy pro $2^d$ regulární grafy $\O(2^d n
-d)$.
-
-Pokud zadaný graf nebude $2^d$-regulární budeme muset pøidat hrany tak, aby nový
-graf tuto vlastnost mìl. Operaci Degree Split pak budeme provádìt tak, abychom
-se k párování blí¾ili.
-
-Místo toho, abychom do grafu hrany jen pøidávali, budeme v pøípadech, kdy je to
-mo¾né, pouze zvìt¹ovat násobnost hrany. U ka¾dé hrany si tedy budeme pamatovat
-její násobnost.
-
-\s{Degree Split s~násobnostmi:} Pro sudì-regulární grafy s násobnostmi zavedeme operaci Degree Split takto:
-Graf $G=(V,E)$ rozdìlíme na dva grafy $G_1$ a $G_2$, bude platit $V(G_1) = V(G_2) = V$. Hrany nyní pøidìlíme následujícím zpùsobem:
-\algo
-\:Pokud $e\in E$ v $G$ má sudou násobnost (znaèíme $n(e)$), umístíme ji do $E_1$ i do $E_2$ s násobností ${n(e) \over 2}$, v opaèném pøípadì pøidáme do obou grafù hranu s násobností $\lfloor {n(e) \over 2} \rfloor$.
-\:Graf se zbylých hran má v¹echny stupnì sudé a je bez multiplicit. Provedeme na nìj pùvodní operaci Degree Split a rozdìlené mno¾iny hran pøidáme do $G_1$ a $G_2$.
-\endalgo
-
-Celý proces lze stihnout v èase $\O(m)$ ($m$ je poèet hran $G$), nebo» v první èásti u ka¾dé hrany pouze zjistíme, zda má sudou násobnost, pøidáme nové hrany v konstantním èase (upravíme násobnosti), a v druhé èásti se provede Split, který má té¾ lineární slo¾itost. Operace Degree Split má tedy slo¾itost $\O(m)$ i v grafu s násobnostmi.
-
-Mìjme nyní $k$-regulární bipartitní graf. Zvolme $t$ tak aby $2^t\geq kn$.
-Zvolme dále
-$\alpha := \lfloor {2^t \over k} \rfloor$ a
+\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
+$\alpha := \lfloor 2^t/k \rfloor$ a