From 4e3fc0c9de845de3694346723796e540b5320f72 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 29 Oct 2007 20:50:52 +0100 Subject: [PATCH] Opravena formulace algoritmu pro maximalni parovani v regularnich bipartitnich grafech. Degree Split je nyni definovan nejen pro regularni grafy, ale obecne pro grafy se vsemi stupni sudymi, predtim se nedal primo pouzit ve splitu s nasobnostmi. Sudost poctu hran, ktera je pro split potreba, nyni rozebirame dukladneji, a $n$ definujeme jako velikost partity, nikoliv celeho grafu, cimz se zbavime +/-1 problemu v odhadech. U Nagamochiho-Ibarakiho uvadime, ze funguje pro multigrafy. Mimo to par drobnych typografickych vylepseni a carek ve vetach. --- 3-bipcon/3-bipcon.tex | 51 +++++++++++++++++++++++++------------------ 1 file changed, 30 insertions(+), 21 deletions(-) diff --git a/3-bipcon/3-bipcon.tex b/3-bipcon/3-bipcon.tex index f5cf697..3a31393 100644 --- a/3-bipcon/3-bipcon.tex +++ b/3-bipcon/3-bipcon.tex @@ -9,35 +9,43 @@ 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ý -$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$ +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^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 +To 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$. To v¹e jsme schopni stihnout v~lineárním èase, +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.} -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, +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, 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)$. +{\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 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 +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$. +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 $\beta := 2^t \bmod k$. @@ -48,9 +56,10 @@ V 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. +a navíc nebude obsahovat ani násobné hrany, tak¾e bude podgrafem zadaného grafu, jak potøebujeme. -È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)$. +Èasová slo¾itost algoritmu je $\O(m \log n)$, jeliko¾ provádíme inicializaci v~èase +$\O(m)$ a celkem $\log_2 kn=\O(\log n)$ iterací po~$\O(m)$. \h{Stupeò souvislosti grafu} @@ -66,14 +75,14 @@ Algoritmus bude 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èí 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$. +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) \cdot n^{3/2} m)$, kde $\kappa(G)$ je nalezený stupeò souvislosti~$G$. Pro minimální øezy v~neorientovaných grafech ov¹em existuje následující rychlej¹í algoritmus: \h{Globálnì minimální øez (Nagamochi, Ibaraki \cite{nagaiba:conn})} -Buï $G$ neorientovaný graf s~nezáporným ohodnocením hran. Oznaèíme si: +Buï $G$ neorientovaný multigraf s~nezáporným ohodnocením hran. Oznaèíme si: \s{Znaèení:} @@ -118,7 +127,7 @@ $$\eqalign{ 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 +ø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$. -- 2.39.2