From a0d744a0b787d8f7fd6fbc6b5a951aeaaf6dc599 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 10 Nov 2006 12:27:20 +0100 Subject: [PATCH] Prepsan algoritmus na bipartitni parovani. --- 3-bipcon/3-bipcon.tex | 91 ++++++++++++++++++++++--------------------- 1 file changed, 46 insertions(+), 45 deletions(-) diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 7415877..3dba149 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -7,59 +7,60 @@ \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. +\h{Maximální párování v regulárním bipartitním grafu} + +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 -$\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 $\betaProblé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$. +To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z vrcholù (tøeba $s$) lze zvolit +pevnì: pokud vezmeme 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$. +Pokud pracujeme s orientovanými grafy, 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 @@ -72,7 +73,7 @@ Pro minim \h{Algoritmus Namagochiho a Ibarakiho} -\>Buï $G$ neorientovaný graf s~ohodnocením na~hranách. Oznaèíme si: +Buï $G$ neorientovaný graf s~ohodnocením na~hranách. Oznaèíme si: \s{Znaèení:} -- 2.39.2