組合せ最適化輪講 2.3 連結性 川原 純

2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について

計算機上でのグラフの表現 (1) 接続行列 無向グラフの場合は始点、終点ともに 1 各列が 2 個だけ非 0 、他は 0 必要な領域は O(nm)

計算機上でのグラフの表現 (2) 隣接行列 グラフがデンス （ Θ(n 2 ) 本の辺をもつ） のときは効率が良い スパース（ Θ(n) 本の辺をもつ） のときは以下の方法が有効 必要な領域は O(m log n) 必要な領域は O(n 2 log m)

計算機上でのグラフの表現 (3) 隣接リスト 出ていく辺 入ってくる辺 はリスト NIL 必要な領域は O(n log m + m log n + m log m) 本書では、グラフは常に隣接リストで与えられるものとする

グラフ走査アルゴリズム ある節点 s から到達できるすべての節点を求め る s

2.1 グラフ走査アルゴリズム 入力：有効グラフ G と 1 点 s 出力： s から到達可能なすべての点集合 R, 木 T s (1) R:= {s}, Q := {s}, T:= φ (2) If Q = φ then 終了 else v ∈ Q を選ぶ (3) e = (v, w) ∈ E(G) となる w ∈ V(G) R を選ぶ If そのような w が存在しない then Q := Q {v}, (2) へ行く (4) R := R ∪ {w}, Q := Q ∪ {w}, T := T ∪ {e}, (2) へ行く

2.1 グラフ走査アルゴリズム 命題 2.16 グラフ走査アルゴリズムは正しく動作 する

2.1 グラフ走査アルゴリズム 命題 2.17 グラフ走査アルゴリズムは O(m + n) 時間で走るように実装できる

深さ優先探索と幅優先探索 (1) R:= {s}, Q := {s}, T:= φ (2) If Q = φ then 終了 else v ∈ Q を選ぶ (3) e = (v, w) ∈ E(G) となる w ∈ V(G) R を選ぶ If そのような w が存在しない then Q := Q {v}, (2) へ行く (4) R := R ∪ {w}, Q := Q ∪ {w}, T := T ∪ {e}, (2) へ行く v の選び方によって探索順が変わる Q に最後に入れられた v ∈ Q を選ぶ → 深さ優先探索 Q に最初に入れられた v ∈ Q を選ぶ → 幅優先探索

幅優先探索木と最短パス 命題 2.18 幅優先探索木は s から到達可能なすべ ての点への最短パスを含む。 s からすべての点 v ∈ V(G) への最短パスの長さ dist G (s,v) は線形時間で求 められる。 s ダイクストラアルゴリズムの 特殊な場合（すべての 重みが 1 ）に相当

強連結成分を求めるアルゴリズ ム

アイデア 2 回の深さ優先探索を行う → 線形時間 1 回目： 通常の深さ優先探索 各節点の探索から抜け出す時に 番号をつける (post-order)

強連結成分を求めるアルゴリズ ム アイデア 2 回の深さ優先探索を行う → 線形時間 回目： 通常の深さ優先探索 各節点の探索から抜け出す時に 番号をつける (post-order) 2 回目： 逆向きの深さ優先探索 番号の大きい節点から探索を始める 1 2 3

観察 x < y ならば、いずれかが成り立つ (1) v_y から v_x へ到達可能 (2) v_x と v_y は相互に到達不可 v_x から v_y へ到達可能、かつ、 v_y から v_x へ到達不可、ということは起こり得ない 最も大きな番号の節点 r を選ぶと … r r に到達可能な節点 → r から到達可能 r 強連結

アルゴリズム 2.2 強連結成分を求めるアルゴリズム 正確な定義は教科書参照

アルゴリズムの正しさ 定理 2.19 強連結成分アルゴリズムはすべての強 連結成分を線形時間で正しく求める 証明 （同一の強連結成分に含まれる 2 点 ⇒ comp- 値が同じ） （ comp- 値が同じ 2 点 ⇒ 同一の強連結成分に含まれる） 2 点は深さ優先探索森の同一の木に含まれるので成り立つ comp(u) = comp(v) とする。 u, v が同一の強連結成分に 含まれることを示す

（ comp- 値が同じ 2 点 ⇒ 同一の強連結成分に含まれる） の証明 comp(u) = comp(v) とする。 u, v が同一の強連結成分に 含まれることを示す 定理 2.19 強連結成分アルゴリズムはすべての強連結成分を線形時間で正しく求める r(x) : x から到達可能な点で最大の Ψ- 値（番号）をとる点 2 回目の深さ優先探索で得られる反有向木 u と v の comp 値が同じなので … u v r(u) = r(v) r(u) と r(v) は一致、これを r とする。 r は反有向木の根となる r は u と v の両方から到達可能 u から r が到達可能、かつ、 Ψ(r) ≧ Ψ(u) なので、 r は r = u あるいは 最初の深さ優先探索で u より前に R に加えられたことになり、 最初の深さ優先探索森は r-u- パスを含む → r から u に到達可能 同様に r から v に到達可能

トポロジカル順序を求める 各強連結成分を 1 点に縮約する 強連結成分を求めるアルゴリズムで 付けた番号がトポロジカル順序に なっている 定理 2.20 強連結成分アルゴリズムは有向グラフ G の 各強連結成分を 1 点に縮約して得られる有向グラフの トポロジカル順序を正しく求める 1 2 3

高次の連結性 k- 連結： 任意に k – 1 点を除去しても連結 k- 辺連結： 任意に k – 1 本の辺を除去しても連結 点連結度、辺連結度 – 上記の最大の k ブロック： 関節点をもたないような極大な連結 部分グラフ 無向グラフ

耳分解 無向グラフの場合

耳分解 無向グラフの場合 逆にグラフ G が以下のように与えられたとき、

耳分解 無向グラフの場合 逆にグラフ G が以下のように与えられたとき、 P_1 P_2 P_3 P_4 P_5 r r, P_1, P_2, P_3, P_4, P_5 を G の耳分解という 正式な定義は次ページ

耳分解 定義 2.21 G を無向グラフとする。各 P_i (i = 1,…,k) に対し て、 P_i はパスであり、 P_i の両端点のちょうど 2 点のみ が {r} ∪ V(P_1) ∪ … ∪ V(P_{i-1}) に属するか、あるいは P_i は閉路であり P_i のちょうど一点のみが {r} ∪ V(P_1) ∪ … ∪ V(P_{i-1}) に属するような系列 r, P_1,…,P_k を用いて、 G が G = ({r}, φ) + P_1 + … + P_k とかけるとき、この系列 r, P_1,…,P_k を G の耳分解という。 無向グラフの場合 P_1 P_2 P_3 P_4 P_5 r

耳分解 定義 2.21 G を無向グラフとする。各 P_i (i = 1,…,k) に対し て、 P_i はパスであり、 P_i の両端点のちょうど 2 点のみ が {r} ∪ V(P_1) ∪ … ∪ V(P_{i-1}) に属するか、あるいは P_i は閉路であり P_i のちょうど一点のみが {r} ∪ V(P_1) ∪ … ∪ V(P_{i-1}) に属するような系列 r, P_1,…,P_k を用いて、 G が G = ({r}, φ) + P_1 + … + P_k とかけるとき、この系列 r, P_1,…,P_k を G の耳分解という。 無向グラフの場合 P_1 P_2 P_3 P_4 P_5 r P_1 が 3 点以上の点からなる閉 路、 P_2,…,P_k がすべて パスならば耳分解は プロパーであるという P_1 P_3 P_2 P_4 P_5 r

2- 連結と耳分解 定理 2.22 無向グラフが 2- 連結であるための必要 十分条件は、プロパーな耳分解をもつことであ る。