## 木/グリッドグラフのdecremental connectivity atcoder:hotman78 codeforces:hotman78 twitter:@hotmanww --- ### incremental connectivityとは N頂点の空グラフが与えられて、 1. 頂点sと頂点tの間に辺を張る 2. 頂点sと頂点tの間にpathが存在するか判定 をする問題 **要するにUnion-Findで処理できるクエリの事** --- ### decremental connectivityとは N頂点のグラフが与えられて、 1. 頂点sと頂点tを結ぶ辺を消去する 2. 頂点sと頂点tの間にpathが存在するか判定 をする問題 **要するにincremental connectivityの逆** --- ### dynamic connectivityとは N頂点の空グラフが与えられて、 1. 頂点sと頂点tの間に辺を張る 2. 頂点sと頂点tを結ぶ辺を消去する 3. 頂点sと頂点tの間にpathが存在するか判定 をする問題 **要するにincremental connectivityとdecremental connectivityのあわせ技** --- ### 今回やること dynamic connectivityのアルゴリズムは難しいので、 今回は比較的簡単な、木/グリッドグラフのdecremental connectivityについて話します --- ## 木のdecremental connectivity N頂点の~~グラフ~~木が与えられて、 1. 頂点sと頂点tを結ぶ辺を消去する 2. 頂点sと頂点tの間にpathが存在するか判定 をする問題 --- ## アプローチ 1. 同じ頂点に同じラベルを張る 2. 辺が消去された時、連結成分の数は**必ず**増えるので貼り直す 3. 実は貼り直す操作がクエリ回数$Q=\Theta(N)$とした時、償却計算量$\mathcal{O}(\log N)$で出来る！！ --- ## アルゴリズム --- ### 初期化 - label[i]=0 (for i in V) - cnt=1 --- ### 頂点sと頂点tを結ぶ辺を消去する - sとtの内、連結成分が少ない方をsとする - label[i]=cnt (for i in (sの連結成分)) - cnt++ --- ### 頂点sと頂点tの間にpathが存在するか判定 - sとtのラベルが同じなら true 違うなら false を返す --- ## 計算量削減と解析 --- ### 計算量削減のPoint - sとtの内、連結成分が少ない方を調べる - 少ない方を塗り替える この両方が、xの連結成分の数を$size(x)$として、 $\Theta(min(size(s),size(t)))$で行える --- ### どうやって sとt、交互にdfsをして、最初に全て見終わった方が小さい --- ### 計算量解析 - ある頂点kが何回見られるかに注目 - 最初 $size(k)=N$ - 一回見られた時(２つに別れた連結成分の内、小さい方に属していた時、$size(k) \leq N/2$) - ２つに別れた時に小さい方なのでその後も半分以下に減っていく - $size(k) \geq 1$ (それはそう) **よって頂点kは$\mathcal{O}(\log N)$回しか見られない** **故に頂点全体も$\mathcal{O}(N\log N)$回しか見られない** --- ## 出来た！！ **マージテクの逆versionと考えるとわかりやすい** --- ## グリッドグラフのdecremental connectivity N頂点のグリッドグラフが与えられて、 1. 頂点sと頂点tを結ぶ辺を消去する 2. 頂点sと頂点tの間にpathが存在するか判定 をする問題 --- ## アプローチ 1. 同じ頂点に同じラベルを張る 2. 辺が消去された時、連結成分の数が変化するなら木の場合と同様に貼り直す 3. 連結成分が変化するかどうかの判定は実は**Union Find**で出来る --- ### オイラーの多面体定理の拡張 >平面グラフ G には, $n$ 個の点, $m$ 本の辺, $f$ 個の面, $k$ 個の連結成分があるとき $n−m+f=k+1$である。 点の数は固定で、辺の数は $1$ 個ずつ減って行くので面の数が変わらなければ、連結成分の数が $1$ つ増えたことになる $\rightarrow$**Union Find**で面の数を数えれば出来る！！ --- 最初  --- 辺の数は減ったけど、面の数も減ったので連結成分は増えていない  $\downarrow$  --- 辺の数は減り、面の数は増えなかったので連結成分が増えた！！  $\downarrow$  --- ## 出来た！！ **双対グラフ(面と面を結ぶグラフ)を作れば一般の平面的グラフでも出来るが、いい感じの面の検出アルゴリズムは引っかからなかった** --- ### 参考文献 [Optimal decremental connectivity in planar graphs](https://arxiv.org/abs/1409.7240) Jakub Łącki, Piotr Sankowski [グラフ理論 講義ノート #8](https://ocw.hokudai.ac.jp/wp-content/uploads/2016/01/GraphTheory-2007-Note-08.pdf) 井上 純一 北海道大学 大学院情報科学研究科 平成 19 年 6 月 11 日