kawahara20110331

組合せ最適化輪講
2.3 連結性
川原純
2.3 連結性
• 内容
– グラフ上の節点をすべてたどるアルゴリズム
• 計算機上でのグラフの表現
– 強連結成分を求めるアルゴリズム
• トポロジカル順序を求める方法も
– k-連結、k-辺連結について
– 2-連結グラフの耳分解について
計算機上でのグラフの表現(1)
• 接続行列
1
2
3
4
1
-1
1
0
0
2
1
0
-1
0
1
3
0
1
-1
0
4
0
1
0
-1
5
0
0
1
-1
6
0
1
0
-1
2
1
3
3
2
4
6
5
4
無向グラフの場合は始点、終点ともに 1
各列が2個だけ非0、他は0
必要な領域は O(nm)
計算機上でのグラフの表現(2)
•
隣接行列
1
2
3
4
1
0
0
1
0
2
1
0
1
2
3
0
0
0
1
1
4
0
0
0
0
2
1
3
3
2
4
5
4
6
グラフがデンス（Θ(n2) 本の辺をもつ）のときは効率が良い
必要な領域は O(n2 log m)
スパース（Θ(n) 本の辺をもつ）のときは以下の方法が有効
1
2 3 4
5 6
必要な領域は O(m log n)
1 2 3 1 3 2 4 2 4 3 4 2
計算機上でのグラフの表現(3)
本書では、グラフは常に隣接リストで与えられるものとする
• 隣接リスト
出ていく辺
1
入ってくる辺
1
2
3
4
4 5 6
1
2 3
4 5 6
1
1
2
2
1 3 4 6
3
5
4
6
4
5
6
必要な領域は O(n log m +
3
3
2
4
はリスト
2
5
4
NIL
m log n + m log m)
グラフ走査アルゴリズム
• ある節点 s から到達できるすべての節点を求める
s
2.1 グラフ走査アルゴリズム
• 入力：有効グラフ G と 1点 s
• 出力：s から到達可能なすべての点集合 R, 木 T
(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) へ行く
s
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)
への最短パスの長さ distG(s,v) は線形時間で求めら
れる。
s
1
3
1
2
2
3
ダイクストラアルゴリズムの
特殊な場合（すべての
重みが1）に相当
強連結成分を求めるアルゴリズム
強連結成分を求めるアルゴリズム
5
アイデア
7
6
2回の深さ優先探索を行う
→線形時間
4
2
3
1回目：通常の深さ優先探索
各節点の探索から抜け出す時に
番号をつける (post-order)
10
9
7
8
6
2
1
1
5
3
4
強連結成分を求めるアルゴリズム
アイデア
2回の深さ優先探索を行う
→線形時間
3
5
7
2
6
4
2
3
1回目：通常の深さ優先探索
各節点の探索から抜け出す時に
番号をつける (post-order)
2回目：逆向きの深さ優先探索
番号の大きい節点から探索を始める
1
10
9
1
8
観察
5
x < y ならば、いずれかが成り立つ
(1) v_y から v_x へ到達可能
(2) v_x と v_y は相互に到達不可
7
6
4
2
3
v_x から v_y へ到達可能、かつ、
v_y から v_x へ到達不可、ということは起こり得ない
9
最も大きな番号の節点 r を選ぶと…
r
1
10
8
r
r に到達可能な節点
→ r から到達可能
強連結
アルゴリズム 2.2 強連結成分を求めるアルゴリズム
5
7
6
4
2
3
正確な定義は教科書参照
1
10
9
8
アルゴリズムの正しさ
• 定理2.19 強連結成分アルゴリズムはすべての強連
結成分を線形時間で正しく求める
証明
（同一の強連結成分に含まれる2点 ⇒ comp-値が同じ）
2点は深さ優先探索森の同一の木に含まれるので成り立つ
（ comp-値が同じ2点 ⇒ 同一の強連結成分に含まれる）
comp(u) = comp(v) とする。u, v が同一の強連結成分に
含まれることを示す
定理2.19 強連結成分アルゴリズムはすべての強連結成分を線形時間で正しく求める
（ comp-値が同じ2点 ⇒ 同一の強連結成分に含まれる）の証明
comp(u) = comp(v) とする。u, v が同一の強連結成分に
含まれることを示す
r(x) : x から到達可能な点で最大のΨ-値（番号）をとる点
u と v の comp 値が同じなので…
2回目の深さ優先探索で得られる反有向木
r(u) = r(v)
r(u) と r(v) は一致、これを r とする。
r は反有向木の根となる
u
v
r は u と v の両方から到達可能
u から r が到達可能、かつ、Ψ(r) ≧ Ψ(u) なので、r は r = u あるいは
最初の深さ優先探索で u より前に R に加えられたことになり、
最初の深さ優先探索森は r-u-パスを含む → r から u に到達可能
同様に r から v に到達可能
トポロジカル順序を求める
3
2
各強連結成分を1点に縮約する
3
2
1
強連結成分を求めるアルゴリズムで
付けた番号がトポロジカル順序に
なっている
1
定理 2.20 強連結成分アルゴリズムは有向グラフGの
各強連結成分を1点に縮約して得られる有向グラフの
トポロジカル順序を正しく求める
高次の連結性
無向グラフ
• k-連結：任意に k – 1 点を除去しても連結
• k-辺連結：任意に k – 1 本の辺を除去しても連結
• 点連結度、辺連結度
– 上記の最大のk
• ブロック：関節点をもたないような極大な連結部分
グラフ
耳分解
無向グラフの場合
耳分解
無向グラフの場合
逆にグラフ G が以下のように与えられたとき、
耳分解
無向グラフの場合
逆にグラフ G が以下のように与えられたとき、
r
P_1
P_3
P_2
P_5
P_4
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 の耳
分解という。
r
P_1
P_2
P_3
P_4
P_5
耳分解
無向グラフの場合
• 定義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 の耳
分解という。
r
P_1
P_5
P_1 が3点以上の点からなる閉路、
P_3
P_4
P_2,…,P_k がすべて
P_2
r
P_1
パスならば耳分解は
P_5
P_2
プロパーであるという
P_4
P_3
2-連結と耳分解
• 定理 2.22 無向グラフが2-連結であるための必要十
分条件は、プロパーな耳分解をもつことである。

Download Report