\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
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$ skontrahujeme. Rekurzivnì najdeme minimální
+$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$.
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 bude znamenat pouze podívat se na
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> 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øíhrádku, a celý algoritmus $\O(mn)$.
+jeliko¾ za~ka¾dou hranu pøeskakujeme maximálnì jednu pøihrádku, a celý algoritmus $\O(mn)$.
\references
\bye
projects / ga.git / blobdiff