S3.5. グラフの強連結成分分解

グラフの強連結成分分解 1
基礎数理
簡単な例題
1
図 1 のグラフが何らかのシステムの状態推移を表していると考えよう．システムには六
つの状態 {v1 , v2 , v3 , v4 , v5 , v6 } があり，辺 (vi , vj ) があるときには状態 vi から状態 vj に変
化する可能性がある．このグラフから次のようなことがわかる．
• システムが状態 v6 にあるならば，他の任意の状態に (いつかの時点で) 到達する可能
性がある．
• システムが状態 v3 にあるならば，将来の時点で可能な状態は v3 だけである．
• システムが状態 v1 にあるならば，状態 v6 に到達する可能性はない．
到達可能性によって状態を分類すると，図 2 のように，グラフの点集合 V が
V1 = {v4 , v6 },
V2 = {v1 , v2 , v5 },
V3 = {v3 }
の三つのブロックに分けられる．ここで，辺の向きは
V1 → V2 ,
V2 → V3 ,
V1 → V3
(1)
に限られており，
k > l のとき Vk から Vl に向かう辺は存在しない．
(2)
とくに，V1 = {v4 , v6 }, V2 = {v1 , v2 , v5 }, V3 = {v3 } のブロックに合わせて
v4 , v6 | v1 , v2 , v5 | v3
(3)
という順番に点を並べると，異なるブロックの 2 点を結ぶ任意の辺 (vi , vj ) について，始
点 vi は終点 vj より前にある．
このようなグラフの分解は，強連結成分分解とよばれるものであり，一般の有向グラフ
に対して，以下のように定義される．
図 1: グラフによる行列の表現
1
本資料は，室田一雄，杉原正顯: 工学教程線形代数 II, 丸善出版, 2013 の 1.1.2 節による．
1
2
一般の場合
有向グラフ G = (V, E) を考える．まず，互いに有向道 (順につながった辺の集まりで，
辺の向きがそろっているもの) で到達できる点どうしを仲間にして，点集合 V をいくつか
の部分に分割する．これを V1 , . . . , Vp (p ≥ 1) とすると，
p
∪
Vk = V ;
Vk ̸= ∅ (k = 1, . . . , p)
(4)
k=1
となる．これを強連結成分分解といい，一つの Vk を強連結成分とよぶ．さらに，強連結
成分の間には，
Vk ⪰ Vl ⇐⇒ ある u ∈ Vk からある v ∈ Vl への有向道が存在する
(5)
によって，上下関係 (順序関係) を表す 2 項関係 Vk ⪰ Vl が定義される 2 ．とくに，
u ∈ Vk , v ∈ Vl に対して辺 (u, v) ∈ E が存在 =⇒ Vk ⪰ Vl
(6)
が成り立つ．なお，全体が一つの強連結成分 (すなわち，p = 1) になる場合もあるが，そ
のようなグラフを強連結なグラフという．
図 2 の例では，式 (1) により
V1 ⪰ V2 ⪰ V3
(7)
である．この例ではすべての Vk が一列に並んでいるが，一般には，そうとは限らない．た
とえば，図 3 (左側) のグラフ G には四つの強連結成分 V1 , V2 , V3 , V4 があるが，
V1 ⪰ V3 ,
V1 ⪰ V4 ,
V2 ⪰ V4
(8)
となっていて，V1 と V2 は順序関係をもたない (V1 ⪰ V2 も V2 ⪰ V1 も不成立である)．こ
のように，式 (5) で定義される関係 ⪰ は半順序となる 3 ．
図 2: 図 1 のグラフの強連結成分分解
2
任意の点 v について，v から v へは長さ 0 の有向道が存在すると約束する．このとき，Vk が 1 点だけか
ら成る場合も含めて，Vk ⪰ Vk が成り立つ．
3
「半順序」は「反射律，反対称律，推移律を満たす 2 項関係」として定義される．
2
図 3: グラフ G の強連結成分分解と簡約グラフ G
強連結成分分解における半順序構造を表現するには，強連結成分 V1 , . . . , Vp をそれぞれ
1 点に縮約した簡約グラフ G をつくるとよい (図 3 参照)．各強連結成分 Vk に対応する点
を v k とするとき，簡約グラフ G の点集合は
V = {v 1 , . . . , v p }
であり，辺集合 E は
(v k , v l ) ∈ E ⇐⇒ ある u ∈ Vk , v ∈ Vl に対して (u, v) ∈ E; k ̸= l
と定義される．簡約グラフ G = (V , E) は有向閉路をもたないので，点の間の関係 ⪰ を
v k ⪰ v l ⇐⇒ v k から v l への有向道が存在する
(9)
によって定義すると，これは半順序になる．簡約グラフ G の点 v k と元のグラフ G の強連
結成分 Vk との対応の下で，この半順序 (9) は強連結成分間の半順序 (5) に一致する．逆に
いえば，強連結成分間の半順序 (5) は簡約グラフ G によって表現される．
強連結成分分解における半順序は，グラフが表現している工学システムに内在する階層
構造を表現しており，応用上の意味を有していることが多い．たとえば，辺が情報の伝達
経路を表しているときには，情報共有の構造は強連結成分間の半順序によって表現される
ことになる．強連結成分分解は, O(|V | + |E|) 時間で高速に求めることができるので，大
規模なシステムに対しても適用可能である 4 ．
3
数学的に厳密な定義
グラフ G = (V, E) の強連結成分分解を数学的に厳密に定義すると以下のようになる 5 ．
まず，点集合 V 上の 2 項関係 ≥ を
u ≥ v ⇐⇒ u から v への有向道が存在する
と定義すると，
4
|V |, |E| は，それぞれ，集合 V , E の大きさ (要素の個数) を表す．また，O(|V | + |E|) は，ある定数 c に
よって c(|V | + |E|) で抑えられる大きさであることを表す．
5
ここの議論は，むしろ，2 項関係の諸概念を習得するために有用であろう．
3
反射律：任意の v ∈ V に対して v ≥ v ，
推移律：任意の u, v, w ∈ V に対して [ u ≥ v, v ≥ w ⇒ u ≥ w ]
が成り立つ．すなわち，2 項関係 ≥ は擬順序である (一般に，反射律と推移律を満たす 2
項関係を擬順序とよぶ)．
次に，擬順序 ≥ を用いて，点集合 V 上の 2 項関係 ∼ を
u ∼ v ⇐⇒ u ≥ v かつ v ≥ u
と定義すると，
反射律：任意の v ∈ V に対して v ∼ v ，
対称律：任意の u, v ∈ V に対して [ u ∼ v ⇒ v ∼ u ]，
推移律：任意の u, v, w ∈ V に対して [ u ∼ v, v ∼ w ⇒ u ∼ w ]
が成り立つ．すなわち，2 項関係 ∼ は同値関係である (一般に，反射律，対称律，推移律
を満たす 2 項関係を同値関係とよぶ)．
この同値関係 ∼ から V の分割が定まる．すなわち，各 v ∈ V に対して，その同値類
[v] = {u ∈ V | u ∼ v}
を定義すると，
・任意の v ∈ V に対して v ∈ [v]，
・任意の u, v ∈ V に対して [ u ∈ [v] ⇒ [u] = [v] ]，
・任意の u, v ∈ V に対して [ [u] ∩ [v] ̸= ∅ ⇒ [u] = [v] ]
が成り立つ．一つの同値類 [v] を強連結成分とよび，同値類の全体の定める V の分割 (商
集合) を強連結成分分解という．一般に，同値類の全体を商集合とよび，V / ∼ という記号
で表すことが多い．式で書けば
V / ∼ = { [v] | v ∈ V }
である．
最後に，商集合 V / ∼ 上の 2 項関係 ⪰ を
[u] ⪰ [v] ⇐⇒ u ≥ v
(10)
によって定義できる．ここで「定義できる」理由は，[u] = [u′ ], [v] = [v ′ ] ならば「u ≥
v ⇐⇒ u′ ≥ v ′ 」であるから，式 (10) の右辺が同値類の代表元 (u や v) のとり方に依らず
に確定するからである．このとき，
反射律：任意の [v] ∈ V / ∼ に対して [v] ⪰ [v]，
反対称律：任意の [u], [v] ∈ V / ∼ に対して
[ [u] ⪰ [v], [v] ⪰ [u] ⇒ [u] = [v] ]，
推移律：任意の [u], [v], [w] ∈ V / ∼ に対して
[ [u] ⪰ [v], [v] ⪰ [w] ⇒ [u] ⪰ [w] ]
が成り立つ．すなわち，2 項関係 ⪰ は半順序である (一般に，反射律，反対称律，推移律
を満たす 2 項関係を半順序とよび，半順序の定義された集合を半順序集合という)．この
ようにして，強連結成分の間に半順序 ⪰ が定義される．
以上 (2014-10-15)
4

Download Report