From 9caf01a8298a65d9ff4e7e40c9dd61cb6fb60c1d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 23 Oct 2008 13:08:33 +0200 Subject: [PATCH] Prepsan popis algoritmu pro maximalni parovani v regularnich bip. grafech. Ted by mel byt srozumitelnejsi; navic jsem prejmenoval Degree Split na lepe znejici stepeni grafu. --- 3-bipcon/3-bipcon.tex | 45 ++++++++++++++++++++----------------------- 1 file changed, 21 insertions(+), 24 deletions(-) diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index 3a31393..2b41a54 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -8,40 +8,37 @@ kter \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ý -graf $G=(V,E)$ se v¹emi vrcholy sudého stupnì a sudým poètem hran, a~rozdìlí -ho 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$. -Speciálnì $2k$-regulární graf o~sudém poètu vrcholù tedy rozdìlí na~dva $k$-regulární -grafy. 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^t$-regulárním +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).} -Staèí provést Degree Split na~dva $2^{t-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$.\foot{Grafy, které budeme splitovat, mají v¾dy sudý -poèet hran, jeliko¾ buïto jsou alespoò 4-regulární, nebo jsou to disjunktní sjednocení -sudých kru¾nic.} -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.} +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 splitech budeme vybírat ten podgraf, +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 Degree Split grafu s~násobnostmi} pak budeme provádìt následovnì: hranu~$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í Degree Split +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é, @@ -54,7 +51,7 @@ Ka V¹imnìte si, ¾e $\beta