3-bipcon/3-bipcon.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{3}{Bipartitní párování a globální k-souvislost}{}
   4
   5 V~pøede¹lých kapitolách jsme se zabývali aplikacemi tokù na~hledání maximálního párování
   6 a minimálního $st$-øezu. Nyní si pøedvedeme dva algoritmy pro podobné problémy,
   7 které se obejdou bez tokù.
   8
   9 \h{Maximální párování v regulárním bipartitním grafu \cite{alon:matching}}
  10
  11 Nejprve si nadefinujme operaci {\I ¹tìpení grafu,} která zadaný graf $G=(V,E)$
  12 se v¹emi vrcholy sudého stupnì a sudým poètem hran v~ka¾dé komponentì souvislosti
  13 rozlo¾í na~disjunktní podgrafy $G_1=(V,E_1)$ a $G_2=(V,E_2)$,
  14 v~nich¾ bude pro ka¾dý vrchol~$v$ platit ${\rm deg}_{G_1}(v) = {\rm
  15 deg}_{G_2}(v) = {\rm deg}_G(v)/2$. Tuto operaci mù¾eme snadno
  16 provést v~lineárním èase tak, ¾e si graf rozdìlíme na~komponenty, v~ka¾dé
  17 nalezneme eulerovský tah a jeho hrany budeme pøidávat støídavì do~$G_1$ a do~$G_2$.
  18
  19 ©tìpení nám pomù¾e ke~snadnému algoritmu pro nalezení maximálního párování ve~$2^t$-regulárním
  20 bipartitním grafu.\foot{V¹imnìte si, ¾e takové párování bude v¾dy perfektní (viz Hallova vìta).}
  21 Komponenty takového grafu mají urèitì sudý poèet hran, tak¾e jej mù¾eme
  22 roz¹tìpit na~dva $2^{t-1}$-regulární grafy. Libovolný jeden z~nich pak opìt roz¹tìpíme
  23 atd., a¾ dostaneme $1$-regulární graf, který je perfektním párováním v~$G$.
  24 To v¹e jsme schopni stihnout v~lineárním èase, jeliko¾ velikosti grafù, které
  25 ¹tìpíme, exponenciálnì klesají. Také bychom mohli rekurzivnì zpracovávat obì
  26 èásti a tak se v~èase $\O(m\log n)$ dobrat ke~kompletní 1-faktorizaci
  27 zadaného grafu.\foot{To je rozklad hran grafu na~disjunktní perfektní párování
  28 a má ho ka¾dý regulární bipartitní graf.}
  29
  30 Pokud zadaný graf nebude $2^t$-regulární, pomù¾eme si tím, ¾e ho novými hranami
  31 doplníme na $2^t$-regulární a pak si pøi ¹tìpeních budeme vybírat ten podgraf,
  32 do~kterého padlo ménì nových hran, a uká¾eme, ¾e nakonec v¹echny zmizí.
  33 Abychom graf pøíli¹ nezvìt¹ili, budeme se sna¾it místo pøidávání úplnì nových
  34 hran pouze zvy¹ovat násobnost hran existujících. Pro ka¾dou hranu $e$ si tedy
  35 budeme pamatovat její násobnost $n(e)$.
  36
  37 {\I ©tìpení grafu s~násobnostmi} pak budeme provádìt následovnì: hranu~$e$
  38 s~násobností $n(e)$ umístíme do~$G_1$ i~do~$G_2$ s~násobností $\lfloor n(e)/2
  39 \rfloor$ a pokud bylo $n(e)$ liché, pøidáme hranu do~pomocného grafu
  40 $G^\prime$. V¹imnìte si, ¾e $G^\prime$ bude graf bez násobností, v~nìm¾ mají
  41 v¹echny vrcholy sudý stupeò, tak¾e na~nìj mù¾eme aplikovat pùvodní ¹tìpící algoritmus
  42 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. Obì jeho partity jsou stejnì velké,
  45 oznaème si poèet vrcholù v~ka¾dé z~nich~$n$. Zvolme $t$ tak aby $2^t\geq kn$.
  46 Zvolme dále parametry
  47 $\alpha := \lfloor 2^t/k \rfloor$ a
  48 $\beta := 2^t \bmod k$.
  49 Ka¾dé pùvodní hranì nastavíme násobnost~$\alpha$ a pøidáme triviální párování~$F$
  50 ($i$-tý vrchol vlevo se spojí s~$i$-tým vrcholem vpravo) s~násobností~$\beta$.
  51 V¹imnìte si, ¾e $\beta<k$, a~proto hran v~$F$ (vèetnì násobností) bude ménì ne¾ $2^t$.
  52
  53 Takto získáme $2^t$-regulární graf, jeho¾ reprezentace bude lineárnì velká. Na tento graf budeme aplikovat operaci
  54 ¹tìpení 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í
  55 a jeliko¾ se~v~ka¾dém kroku zbavíme alespoò poloviny hran z~$F$, nebude toto párování obsahovat ¾ádnou takovou hranu
  56 a navíc nebude obsahovat ani násobné hrany, tak¾e bude podgrafem zadaného grafu, jak potøebujeme.
  57
  58 Èasová slo¾itost algoritmu je $\O(m \log n)$, jeliko¾ provádíme inicializaci v~èase
  59 $\O(m)$ a celkem $\log_2 kn=\O(\log n)$ iterací po~$\O(m)$.
  60
  61 \h{Stupeò souvislosti grafu}
  62
  63 Problém zji¹tìní {\I stupnì hranové souvislosti} grafu lze pøevést na problém hledání minimálního øezu,
  64 který ji¾ pro zadanou dvojici vrcholù umíme øe¹it pomocí Dinicova algoritmu v~èase $\O(n^{2/3}m)$.
  65 Pokud chceme najít minimum ze~v¹ech øezù v~grafu, mù¾eme vyzkou¹et v¹echny dvojice $(s,t)$.
  66 To v¹ak lze snadno zrychlit, pokud si uvìdomíme, ¾e jeden z~vrcholù (tøeba $s$) mù¾eme zvolit
  67 pevnì: vezmeme-li libovolný øez $C$, pak jistì najdeme alespoò jedno~$t$, které padne
  68 do~jiné komponenty ne¾ pevnì zvolené~$s$, tak¾e minimální $st$-øez bude nejvý¹e tak velký jako~$C$.
  69 V~orientovaném grafu musíme projít jak øezy pro $s \rightarrow t$, tak i $t \rightarrow s$.
  70 Algoritmus bude mít slo¾itost $\O(n^{{5/3}}m)$.
  71
  72 U~{\I vrcholové $k$-souvislosti} to ov¹em tak snadno nepùjde. Pokud by toti¾ fixovaný vrchol byl souèástí nìjakého
  73 minimálního separátoru, algoritmus mù¾e selhat. Pøesto ale nemusíme procházet v¹echny dvojice vrcholù. Staèí jako
  74 $s$ postupnì zvolit více vrcholù, ne¾ je velikost minimálního separátoru. Algoritmus si tedy bude pamatovat, kolik
  75 vrcholù u¾ pro¹el a nejmen¹í zatím nalezený $st$-separátor, a jakmile poèet vrcholù pøekroèí velikost separátoru,
  76 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$.
  77
  78 Pro minimální øezy v~neorientovaných grafech ov¹em existuje následující rychlej¹í algoritmus:
  79
  80 \h{Globálnì minimální øez (Nagamochi, Ibaraki \cite{nagaiba:conn})}
  81
  82 Buï $G$ neorientovaný multigraf s~nezáporným ohodnocením hran. Oznaèíme si:
  83
  84 \s{Znaèení:}
  85
  86 \itemize\ibull
  87 \:$r(u,v)$ buï kapacita minimálního $uv$-øezu,
  88 \:$d(P,Q)$ buï kapacita hran vedoucích mezi mno¾inami $P,Q \subseteq V$,
  89 \:$d(P) = d(P,\overline P)$ buï kapacita hran vedoucích mezi $P\subseteq V$ a zbytkem grafu,
  90 \:$d(v) = d(\{v\})$ buï kapacita hran vedoucích z~$v$ (tedy pro neohodnocené grafy stupeò~$v$),
  91 \:analogicky zavedeme $d(v,w)$ a $d(v,P)$.
  92 \endlist
  93
  94 \s{Definice:}
  95 {\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í
  96 $d(\{v_1 \ldots v_{i-1}\},v_i) \geq d(\{v_1 \ldots v_{i-1}\},v_j)$ pro ka¾dé $1 \leq i<j\leq n$.
  97
  98 \s{Lemma:} Je-li $v_1 \ldots v_n$ LU na $G$, pak $r(v_{n-1},v_n)=d(v_n)$.
  99
 100 \proof Buï $C$ libovolný øez oddìlující $v_{n-1}$ a $v_n$.
 101 Doká¾eme, ¾e jeho velikost je alespoò~$d(v_n)$.
 102 Utvoøme posloupnost vrcholù $u_i$ takto:
 103
 104 \algo
 105 \:$u_0 := v_1$
 106 \:$u_i := v_j$ tak, ¾e $j>i$, $v_i$ a $v_j$ jsou oddìleny øezem $C$ a $j$ je minimální takové.
 107 [Tedy $v_j$ je nejbli¾¹í vrchol na~druhé stranì øezu.]
 108 \endalgo
 109
 110 Ka¾dé $u_{i-1}$ je tedy buï rovno $u_i$, pokud jsou $v_i$ a $v_{i-1}$ na stejné stranì øezu, nebo rovno $v_i$, pokud
 111 jsou $v_i$ a $v_{i-1}$ na~stranách opaèných. Z~toho dostáváme, ¾e $d(\{v_1\ldots v_{i-1}\},u_i)\leq d(\{v_1\ldots
 112 v_{i-1}\},u_{i-1})$, proto¾e buïto $u_{i-1}=u_i$, a pak je nerovnost splnìna jako rovnost, nebo je $u_{i-1}=v_i$ a
 113 nerovnost plyne z~legálnosti uspoøádání.
 114
 115 Chceme ukázat, ¾e velikost na¹eho øezu~$C$ je alespoò taková, jako velikost øezu kolem vrcholu $v_n$.
 116 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
 117 rùzné a ka¾dá z~nich je souèástí øezu~$C$. Uká¾eme, ¾e pravá strana je alespoò $d(v_n)$:
 118 $$\eqalign{
 119 \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
 120 &\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
 121 &= d(\{v_1 \ldots v_{n-1}\},u_{n-1}) - d(\{v_1 \ldots v_0\},u_0) = \cr
 122 &=d(\{v_1 \ldots v_{n-1}\},v_n) - 0 = d(v_n).\cr
 123 }$$
 124 \qed
 125
 126 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
 127 kolem~$v_n$. Kdy¾ tedy sestavíme nìjakou LU posloupnost vrcholù, budeme mít k dispozici jednoduchý minimální øez
 128 $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í
 129 ø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
 130 kolem vrcholu $v_n$ minimální, nebo vrcholy $v_n$ a $v_{n-1}$ neoddìluje, a v takovém pøípadì jej najdeme
 131 rekurzivnì. Hledaný øez je tedy men¹í z rekurzivnì nalezeného øezu a øezu kolem $v_n$.
 132
 133 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$, prohlásíme ho za $v_i$ a pøepoèítáme~$z_v$.
 134
 135 Zde se hodí datová struktura, která doká¾e rychle hledat maxima a zvy¹ovat hodnoty prvkù,
 136 napøíklad Fibonacciho halda. Ta zvládne \<DeleteMax> v~èase $\O(\log n)$ a \<Increase> v~$\O(1)$
 137 amortizovanì. Celkem pak ná¹ algoritmus bude mít slo¾itost $\O(n(m+n\log n))$ pro obecné kapacity.
 138
 139 Pokud jsou kapacity malá celá èísla, mù¾eme vyu¾ít pøihrádkové struktury. Budeme
 140 si udr¾ovat obousmìrný seznam zatím pou¾itých hodnot $z_v$, ka¾dý prvek takového
 141 seznamu bude obsahovat v¹echny vrcholy se spoleènou hodnotou $z_v$. Kdy¾ budeme
 142 mít seznam seøazený, vybrání minimálního prvku bude znamenat pouze podívat se na
 143 první prvek seznamu a z nìj odebrat jeden vrchol, pøípadnì celý prvek ze seznamu
 144 odstranit. Operace \<Increase> poté bude reprezentovat pouze pøesunutí vrcholu o
 145 malý poèet pøihrádek, pøípadnì zalo¾ení nové pøihrádky na správném místì.
 146 \<DeleteMax> proto bude mít slo¾itost $\O(1)$, v¹echny \<Increase> dohromady $\O(m)$,
 147 jeliko¾ za~ka¾dou hranu pøeskakujeme maximálnì jednu pøihrádku, a celý algoritmus $\O(mn)$.
 148
 149 \references
 150 \bye