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