-%%%%%%%%%%%%
-% Zápisek tøetího semináre z grafových agoritmù - ze dne 20.3.2006
-% Zapsal Jiøí Peinlich - peinlich@seznam.cz a Michal Kùrka - michal.kurka@gmail.com
-%%%%%%%%%%%
-
\input ../sgr.tex
-\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.
+\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 Degree Split,} která dostane jako vstup libovolný
+$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),
+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,
+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 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 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
-$\alpha := \lfloor {2^t \over k} \rfloor$ a
+Zvolme dále parametry
+$\alpha := \lfloor 2^t/k \rfloor$ a
$\beta := 2^t \bmod k$.
-Do grafu pøidáme hrany a upravíme násobnosti hran tak, aby byl $2^t$ regulární. Dále pøidáme triviální párování ($i$-tý vrchol vlevo se spojí s $i$-tým vrcholem vpravo) s násobností $\beta$. Tuto mno¾inu hran oznaème $F$. Platí $\beta < k \Rightarrow \vert F \vert < 2^t$.
+Ka¾dé pùvodní hranì nastavíme násobnost~$\alpha$ a pøidáme triviální párování~$F$
+($i$-tý vrchol vlevo se spojí s~$i$-tým vrcholem vpravo) s~násobností~$\beta$.
+V¹imnìte si, ¾e $\beta<k$, a~proto hran v~$F$ (vèetnì násobností) bude ménì ne¾ $2^t$.
-Takto získáme $2^t$-regulární graf. Na tento graf budeme aplikovat operaci Degree Split a vybereme si v¾dy tu polovinu, kde bude ménì hran z $F$. Tímto zpùsobem budem graf dìlit dokud budou stupnì vrcholù vìt¹í ne¾ jedna. Tedy $t$-krát. Poslední takto získaný graf bude 1-regulární (párování). V ka¾dém kroku se zbavíme alespoò poloviny hran z $F$. Provedeme to ceklem $t$-krát a tedy výsledné párování bude perfektní párování zadaného grafu.
+Takto získáme $2^t$-regulární graf, jeho¾ reprezentace bude lineárnì velká. Na tento graf budeme aplikovat operaci
+Degree Split a budeme si vybírat v¾dy tu polovinu, kde bude ménì hran z~$F$. Po~$t$ iteracích dospìjeme k~párování
+a jeliko¾ se~v~ka¾dém kroku zbavíme alespoò poloviny hran z~$F$, nebude toto párování obsahovat ¾ádnou takovou hranu
+a navíc nebude ani obsahovat násobné hrany, a~tedy bude podgrafem zadaného grafu, jak potøebujeme.
-Slo¾itost algoritmu je $\O(kn \log n)$, proto¾e inicializace algoritmu se dá provést v lineárním èase, provede se $\log (kn)$ iterací po $\O(m)$.
+Èasová slo¾itost algoritmu je $\O(m \log n)$, jeliko¾ provádíme inicializaci v~$\O(m)$ a celkem $\log_2 kn=\O(\log n)$ iterací po~$\O(m)$.
-\h{Algoritmy na hledání globální k-souvislosti}
+\h{Stupeò souvislosti grafu}
-\>Problém zji¹tìní {\I stupnì hranové souvislosti} grafu lze pøevést na problém hledání minimálního øezu,
+Problém zji¹tìní {\I stupnì hranové souvislosti} grafu lze pøevést na problém hledání minimálního øezu,
který ji¾ pro zadanou dvojici vrcholù umíme øe¹it pomocí Dinicova algoritmu v~èase $\O(n^{2/3}m)$.
-Pokud chceme najít minimum pøes v¹echny dvojice, mù¾eme vyzkou¹et v¹echny dvojice $(s,t)$.
-To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z vrcholù $s$ nebo $t$ lze zvolit
-pevnì. Pokud pracujeme s orientovanými grafy, musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$.
+Pokud chceme najít minimum ze~v¹ech øezù v~grafu, mù¾eme vyzkou¹et v¹echny dvojice $(s,t)$.
+To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z~vrcholù (tøeba $s$) mù¾eme zvolit
+pevnì: vezmeme-li libovolný øez $C$, pak jistì najdeme alespoò jedno~$t$, které padne
+do~jiné komponenty ne¾ pevnì zvolené~$s$, tak¾e minimální $st$-øez bude nejvý¹e tak velký jako~$C$.
+V~orientovaném grafu musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$.
Algoritmus bude mít slo¾itost $\O(n^{{5/3}}m)$.
U~{\I vrcholové $k$-souvislosti} to ov¹em tak snadno nepùjde. Pokud by toti¾ fixovaný vrchol byl souèástí nìjakého
-minimálního separátoru, algoritmus mù¾e selhat. Pøesto ale nemusíme procházet v¹echny dvojice vrcholù. Staèí si
-pamatovat, kolik vrcholù $s$ jsme u¾ pro v¹echny $t$ zkontrolovali a nejmen¹í zatím nalezený separátor. Kdy¾ bude poèet
-vrcholù vìt¹í ne¾ nejmen¹í separátor, tak u¾ jsme jistì na¹li jeden z minimálních øezù. Slo¾itost takového algoritmu pak
-bude $\O(\kappa (G) n^{3/2} m)$, kde $\kappa(G)$ je stupeò souvislosti $G$, který hledáme.
+minimálního separátoru, algoritmus mù¾e selhat. Pøesto ale nemusíme procházet v¹echny dvojice vrcholù. Staèí jako
+$s$ postupnì zvolit více vrcholù, ne¾ je velikost minimálního separátoru. Algoritmus si tedy bude pamatovat, kolik
+vrcholù u¾ pro¹el a nejmen¹í zatím nalezený $st$-separátor a jakmile poèet vrcholù pøekroèí velikost separátoru,
+prohlásí separátor za~minimální. To zvládne v~èase $\O(\kappa (G) n^{3/2} m)$, kde $\kappa(G)$ je nalezený stupeò souvislosti~$G$.
-Pro minimální øezy v~neorientovaných grafech ov¹em existuje rychlej¹í algoritmus, který toky nepou¾ívá.
+Pro minimální øezy v~neorientovaných grafech ov¹em existuje následující rychlej¹í algoritmus:
-\h{Algoritmus Namagochiho a Ibarakiho}
+\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í:}
\s{Definice:}
{\it Legálním uspoøádáním vrcholù} (LU) budeme nazývat lineární uspoøádání vrcholù $v_1 \ldots v_n$ takové, ¾e platí
-$d(\{v_1 \ldots v_{i-1}\},v_i) \geq d(\{v_1 \ldots v_{i-1}\},v_j)$ pro $1 \leq i<j\leq n$.
+$d(\{v_1 \ldots v_{i-1}\},v_i) \geq d(\{v_1 \ldots v_{i-1}\},v_j)$ pro ka¾dé $1 \leq i<j\leq n$.
\s{Lemma:} Je-li $v_1 \ldots v_n$ LU na $G$, pak $r(v_{n-1},v_n)=d(v_n)$.
-\s{Dùkaz:} Buï $C$ nìjaký øez oddìlující $v_{n-1}$ a $v_n$. Utvoøme posloupnost vrcholù $u_i$ takto:
+\proof Buï $C$ nìjaký øez oddìlující $v_{n-1}$ a $v_n$. Utvoøme posloupnost vrcholù $u_i$ takto:
\algo
\:$u_0 := v_1$
\:$u_i := v_j$ tak, ¾e $j>i$, $v_i$ a $v_j$ jsou oddìleny øezem $C$ a $j$ je minimální takové.
+[Tedy $v_j$ je nejbli¾¹í vrchol na~druhé stranì øezu.]
\endalgo
-Ka¾dé $u_{i-1}$ je tedy buï $u_i$, pokud jsou $v_i$ a $v_{i-1}$ na stejné stranì øezu, nebo $u_{i-1}$ je $v_i$ pokud
-jsou $v_i$ a $v_{i-1}$ na opaèné stranì øezu. Dostáváme tedy, ¾e $d(\{v_1\ldots v_{i-1}\},u_i)\leq d(\{v_1\ldots
+Ka¾dé $u_{i-1}$ je tedy buï rovno $u_i$, pokud jsou $v_i$ a $v_{i-1}$ na stejné stranì øezu, nebo rovno $v_i$, pokud
+jsou $v_i$ a $v_{i-1}$ na~stranách opaèných. Z~toho dostáváme, ¾e $d(\{v_1\ldots v_{i-1}\},u_i)\leq d(\{v_1\ldots
v_{i-1}\},u_{i-1})$, proto¾e buïto $u_i=u_{i-1}$, a pak je nerovnost splnìna jako rovnost, nebo je $u_i=v_j$, $j>i$ a
-nerovnost plyne z LU vrcholù $v_i$.
-
-Chceme ukázat, ¾e velikost libovolného øezu je alespoò taková, jako velikost øezu kolem vrcholu $v_n$.
-Platí, ¾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)$:
+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)$. 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 \sum_{i=1}^{n-1} d(\{v_1 \ldots v_i\},u_i) - d(\{v_1 \ldots v_{i-1}\},u_{i-1}) = \cr
-&= d(\{v_1 \ldots v_{n-1}\},u_{n-1}) - d(\{v_1 \ldots v_0\},u_0) = d(\{v_1 \ldots v_{n-1}\},v_n) - 0 = d(v_n).\cr
+\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
+&= d(\{v_1 \ldots v_{n-1}\},u_{n-1}) - d(\{v_1 \ldots v_0\},u_0) = \cr
+&=d(\{v_1 \ldots v_{n-1}\},v_n) - 0 = d(v_n).\cr
}$$
\qed
-Dokázali jsme, ¾e libovolný øez separující $v_{n-1}$ a $v_n$ je vìt¹í ne¾ jednoduchý øez skládající se jen z hran kolem~$v_n$. Kdy¾ tedy sestavíme nìjakou LU posloupnost vrcholù, budeme mít k dispozici jednoduchý minimální øez $v_{n-1}$ a~$v_n$. Následnì vytvoøíme graf $G'$, v nìm¾ $v_{n-1}$ a $v_n$ skontrahujeme. Rekurzivnì najdeme minimální øez v $G'$. Hledaný minimální øez poté buïto oddìluje vrcholy $v_n$ a $v_{n-1}$ a potom je øez kolem vrcholu $v_n$ minimální, nebo vrcholy $v_n$ a $v_{n-1}$ neoddìluje, a v takovém pøípadì jej najdeme rekurzivnì. Hledaný øez je tedy men¹í z rekurzivnì nalezeného øezu a øezu kolem $v_n$.
+Dokázali jsme, ¾e libovolný øez separující $v_{n-1}$ a $v_n$ je alespoò tak velký jako jednoduchý øez skládající se jen z hran
+kolem~$v_n$. Kdy¾ tedy sestavíme nìjakou LU posloupnost vrcholù, budeme mít k dispozici jednoduchý minimální øez
+$v_{n-1}$ a~$v_n$. Následnì vytvoøíme graf $G'$, v nìm¾ $v_{n-1}$ a $v_n$ kontrahujeme. Rekurzivnì najdeme minimální
+øez v $G'$ (sestrojíme nové LU atd.). Hledaný minimální øez poté buïto oddìluje vrcholy $v_n$ a $v_{n-1}$ a potom je øez
+kolem vrcholu $v_n$ minimální, nebo vrcholy $v_n$ a $v_{n-1}$ neoddìluje, a v takovém pøípadì jej najdeme
+rekurzivnì. Hledaný øez je tedy men¹í z rekurzivnì nalezeného øezu a øezu kolem $v_n$.
-Zbývá ukázat, jak konstruovat LU. Postaèí hladovì: Pamatujeme si $\forall v\neq v_1 \ldots v_{i-1}$ hodnotu $d(\{v_1 \ldots v_{i-1},v)$, oznaème ji $z_v$. V ka¾dém kroku vybereme vrchol $v$ s maximální hodnotou $z_v$ a prohlásíme ho za $v_i$ a pøepoèítáme~$z_v$.
+Zbývá ukázat, jak konstruovat LU. Postaèí hladovì: Pamatujeme si $\forall v\neq v_1 \ldots v_{i-1}$ hodnotu $d(\{v_1 \ldots v_{i-1}\},v)$, oznaème ji $z_v$. V ka¾dém kroku vybereme vrchol $v$ s maximální hodnotou $z_v$, prohlásíme ho za $v_i$ a pøepoèítáme~$z_v$.
Zde se hodí datová struktura, která doká¾e rychle hledat maxima a zvy¹ovat hodnoty prvkù,
napøíklad Fibonacciho halda. Ta zvládne \<DeleteMax> v~èase $\O(\log n)$ a \<Increase> v~$\O(1)$
amortizovanì. Celkem pak ná¹ algoritmus bude mít slo¾itost $\O(n(m+n\log n))$ pro obecné kapacity.
-Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøíhrádkové struktury. Budeme
+Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøihrádkové struktury. Budeme
si udr¾ovat obousmìrný seznam zatím pou¾itých hodnot $z_v$, ka¾dý prvek takového
seznamu bude obsahovat v¹echny vrcholy se spoleènou hodnotou $z_v$. Kdy¾ budeme
-mít seznam seøazený, vybrání minimálního prvku znamená pouze podívat se na
+mít seznam seøazený, vybrání minimálního prvku bude znamenat pouze podívat se na
první prvek seznamu a z nìj odebrat jeden vrchol, pøípadnì celý prvek ze seznamu
odstranit. Operace \<Increase> poté bude reprezentovat pouze pøesunutí vrcholu o
malý poèet pøihrádek, pøípadnì zalo¾ení nové pøihrádky na správném místì.
-\<DeleteMax> i \<Increase> pak budou mít slo¾itost $\O(1)$ a celý algoritmus $\O(mn)$.
+\<DeleteMax> proto bude mít slo¾itost $\O(1)$, v¹echny \<Increase> dohromady $\O(m)$,
+jeliko¾ za~ka¾dou hranu pøeskakujeme maximálnì jednu pøihrádku, a celý algoritmus $\O(mn)$.
+\references
\bye