3-bipcon/3-bipcon.tex

   1 %%%%%%%%%%%%
   2 % Zápisek tøetího semináre z grafových agoritmù - ze dne 20.3.2006
   3 % Zapsal Jiøí Peinlich - peinlich@seznam.cz a Michal Kùrka - michal.kurka@gmail.com
   4 %%%%%%%%%%%
   5
   6 \input ../sgr.tex
   7
   8 \prednaska{3}{Bipartitní párování a globální k-souvislost}{zapsali Jiøí Peinlich, Michal Kùrka}
   9
  10 V~minulé kapitole jsme se zabývali aplikacemi tokù na~hledání maximálního párování
  11 a minimálního øezu. V~této si pøedvedeme dva algoritmy pro podobné problémy,
  12 které se obejdou bez tokù.
  13
  14 \h{Maximální párování v regulárním bipartitním grafu}
  15
  16 Nejprve si nadefinujme operaci {\I Degree Split,} která dostane jako vstup libovolný
  17 $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
  18 oba $k$-regulární. Tuto operaci mù¾eme snadno provést v~lineárním èase tak, ¾e si graf
  19 rozdìlíme na~komponenty, v~ka¾dé nalezneme eulerovský tah a jeho sudé hrany dáme do~$G_1$
  20 a liché do~$G_2$.
  21
  22 To nám pomù¾e ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^d$-regulárním
  23 bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta).}
  24 Staèí provést Degree Split na~dva $2^{d-1}$-regulární grafy, na~libovolný jeden z~nich
  25 aplikovat dal¹í Degree Split atd., a¾ se dostaneme k~$1$-regulárnímu grafu, který
  26 je perfektním párováním v~$G$. To v¹e jsme schopni stihnout v~lineárním èase,
  27 jeliko¾ velikosti grafù, které splitujeme, exponenciálnì klesají. Také bychom
  28 mohli rekurzivnì zpracovávat obì komponenty a tak se v~èase $\O(m\log n)$ dobrat
  29 ke~kompletní 1-faktorizaci zadaného grafu.\foot{To je rozklad hran grafu na~disjunktní
  30 perfektní párování a má ho ka¾dý regulární bipartitní graf.}
  31
  32 Pokud zadaný graf nebude $2^d$-regulární, pomù¾eme si tím, ¾e ho novými hranami
  33 doplníme na $2^d$-regulární a pak si pøi splitech budeme vybírat ten podgraf,
  34 do~kterého padlo ménì nových hran, a uká¾eme, ¾e nakonec v¹echny zmizí.
  35 Abychom graf pøíli¹ nezvìt¹ili, budeme sna¾it místo pøidávání úplnì nových
  36 hran pouze zvy¹ovat násobnost hran existujících. Pro ka¾dou hranu $e$ si tedy
  37 budeme pamatovat její násobnost $n(e)$.
  38
  39 {\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$
  40 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
  41 $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í
  42 Degree Split a $G^\prime_i$ pøiøadit ke~$G_i$. To~v¹e zvládneme v~èase $\O(m)$.
  43
  44 Mìjme nyní $k$-regulární bipartitní graf. Zvolme $t$ tak aby $2^t\geq kn$.
  45 Zvolme dále parametry
  46 $\alpha := \lfloor 2^t/k \rfloor$ a
  47 $\beta := 2^t \bmod k$.
  48 Ka¾dé pùvodní hranì nastavíme násobnost~$\alpha$ a pøidáme triviální párování~$F$
  49 ($i$-tý vrchol vlevo se spojí s~$i$-tým vrcholem vpravo) s~násobností~$\beta$.
  50 V¹imnìte si, ¾e $\beta<k$, a~proto hran v~$F$ (vèetnì násobností) bude ménì ne¾ $2^t$.
  51
  52 Takto získáme $2^t$-regulární graf, jeho¾ reprezentace bude lineárnì velká. Na tento graf budeme aplikovat operaci
  53 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í
  54 a jeliko¾ se~v~ka¾dém kroku zbavíme alespoò poloviny hran z~$F$, nebude toto párování obsahovat ¾ádnou a navíc
  55 nebude ani obsahovat násobné hrany, tak¾e opravdu bude podgrafem zadaného grafu.
  56
  57 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)$.
  58
  59 \h{Algoritmy na zji¹tìní stupnì globální k-souvislosti}
  60
  61 Problém zji¹tìní {\I stupnì hranové souvislosti} grafu lze pøevést na problém hledání minimálního øezu,
  62 který ji¾ pro zadanou dvojici vrcholù umíme øe¹it pomocí Dinicova algoritmu v~èase $\O(n^{2/3}m)$.
  63 Pokud chceme najít minimum pøes v¹echny dvojice, mù¾eme vyzkou¹et v¹echny dvojice $(s,t)$.
  64 To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z vrcholù (tøeba $s$) lze zvolit
  65 pevnì: pokud vezmeme libovolný øez $C$, pak jistì najdeme alespoò jedno~$t$, které padne
  66 do~jiné komponenty ne¾ pevnì zvolené~$s$, tak¾e minimální $st$-øez bude nejvý¹e tak velký jako~$C$.
  67 Pokud pracujeme s orientovanými grafy, musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$.
  68 Algoritmus bude mít slo¾itost $\O(n^{{5/3}}m)$.
  69
  70 U~{\I vrcholové $k$-souvislosti} to ov¹em tak snadno nepùjde. Pokud by toti¾ fixovaný vrchol byl souèástí nìjakého
  71 minimálního separátoru, algoritmus mù¾e selhat. Pøesto ale nemusíme procházet v¹echny dvojice vrcholù. Staèí si
  72 pamatovat, kolik vrcholù $s$ jsme u¾ pro v¹echny $t$ zkontrolovali a nejmen¹í zatím nalezený separátor. Kdy¾ bude poèet
  73 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
  74 bude $\O(\kappa (G) n^{3/2} m)$, kde $\kappa(G)$ je stupeò souvislosti $G$, který hledáme.
  75
  76 Pro minimální øezy v~neorientovaných grafech ov¹em existuje rychlej¹í algoritmus, který toky nepou¾ívá.
  77
  78 \h{Algoritmus Namagochiho a Ibarakiho}
  79
  80 Buï $G$ neorientovaný graf s~ohodnocením na~hranách. Oznaèíme si:
  81
  82 \s{Znaèení:}
  83
  84 \itemize\ibull
  85 \:$r(u,v)$ buï kapacita minimálního $uv$-øezu,
  86 \:$d(P,Q)$ buï kapacita hran vedoucích mezi mno¾inami $P,Q \subseteq V$,
  87 \:$d(P) = d(P,\overline P)$ buï kapacita hran vedoucích mezi $P\subseteq V$ a zbytkem grafu,
  88 \:$d(v) = d(\{v\})$ buï kapacita hran vedoucích z~$v$ (tedy pro neohodnocené grafy stupeò~$v$),
  89 \:analogicky zavedeme $d(v,w)$ a $d(v,P)$.
  90 \endlist
  91
  92 \s{Definice:}
  93 {\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í
  94 $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$.
  95
  96 \s{Lemma:} Je-li $v_1 \ldots v_n$ LU na $G$, pak $r(v_{n-1},v_n)=d(v_n)$.
  97
  98 \s{Dùkaz:} Buï $C$ nìjaký øez oddìlující $v_{n-1}$ a $v_n$. Utvoøme posloupnost vrcholù $u_i$ takto:
  99
 100 \algo
 101 \:$u_0 := v_1$
 102 \:$u_i := v_j$ tak, ¾e $j>i$, $v_i$ a $v_j$ jsou oddìleny øezem $C$ a $j$ je minimální takové.
 103 \endalgo
 104
 105 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
 106 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
 107 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
 108 nerovnost plyne z LU vrcholù $v_i$.
 109
 110 Chceme ukázat, ¾e velikost libovolného øezu je alespoò taková, jako velikost øezu kolem vrcholu $v_n$.
 111 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)$:
 112
 113 $$\eqalign{
 114 \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
 115 &= 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
 116 }$$
 117 \qed
 118
 119 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$.
 120
 121 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$.
 122
 123 Zde se hodí datová struktura, která doká¾e rychle hledat maxima a zvy¹ovat hodnoty prvkù,
 124 napøíklad Fibonacciho halda. Ta zvládne \<DeleteMax> v~èase $\O(\log n)$ a \<Increase> v~$\O(1)$
 125 amortizovanì. Celkem pak ná¹ algoritmus bude mít slo¾itost $\O(n(m+n\log n))$ pro obecné kapacity.
 126
 127 Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøíhrádkové struktury. Budeme
 128 si udr¾ovat obousmìrný seznam zatím pou¾itých hodnot $z_v$, ka¾dý prvek takového
 129 seznamu bude obsahovat v¹echny vrcholy se spoleènou hodnotou $z_v$. Kdy¾ budeme
 130 mít seznam seøazený, vybrání minimálního prvku znamená pouze podívat se na
 131 první prvek seznamu a z nìj odebrat jeden vrchol, pøípadnì celý prvek ze seznamu
 132 odstranit. Operace \<Increase> poté bude reprezentovat pouze pøesunutí vrcholu o
 133 malý poèet pøihrádek, pøípadnì zalo¾ení nové pøihrádky na správném místì.
 134 \<DeleteMax> i \<Increase> pak budou mít slo¾itost $\O(1)$ a celý algoritmus $\O(mn)$.
 135
 136 \bye