Graphs and Automata p

I118 グラフとオートマトン理論 I118 グラフとオ トマトン理論

Graphs and Automata p

担当

:

(Ryuhei UEHARA)

:

(Ryuhei UEHARA)

[email protected]

http://www.jaist.ac.jp/~uehara/

6. グラフ

Graphs

6.1 グラフの基本概念

•

(

)

を結ぶ線分（辺あるいは枝）からなる図形．

•

… …

•

G = (V, E)

頂点 集合

辺または無向辺 ((undirected) edge)

– V …

– E …

頂点 (vertex)

•

… V, E

•

…

•

…

6 2 グラフにおける辺 6.2 グラフにおける辺

•

(self-loop)

両端点が同一の辺．

•

(

) (multiple edge)

両端点を共有する複数の辺 両端点を共有する複数の辺．

•

(multiple graph)

自 閉路または多重辺を持 グ

self-loop

自己閉路または多重辺を持つグラフ．

•

(simple graph) (s p e g ap )

自己閉路も多重辺も持たないグラフ．

6 3 辺の接続 6.3 辺の接続

グ が

•

G = (V, E)

e ∈ E

a, b ∈ V

e

a, b ,

(incident)

a, b

(endpoint)

(endpoint)

–

a, b

(adjacent)

いう．

e a b

•

e e = (a b) (a, b)

–

辺 ( b) から b への方向を持つ辺 辺 ( b) は

• 辺 (a, b) … a から b への方向を持つ辺．辺 (a, b) は，

頂点 a, b に，それぞれ正，負の向きに接続していると いう

いう．

• a … 始点，b … 終点．

無向グラフの場合

(a,b), ab と書く人もいる

–

• {a, b}, {b, a} は同一の辺を意味する（順序対ではな

い）

い）．

a b

– グラフに多重辺がない場合，E ⊆ V × V とできる．

6.4 次数 (degree) ( g )

• (

)

(degree)  : V  N

–

a

… a

–

• 正の次数(出次数):



• 正の次数(出次数):

ある頂点に正の向きに接続している辺の数．（出て行 く辺の数）



• 負の次数（入次数）:

ある頂点に負の向きに接続している辺の数．（入ってく



る辺の数）

• 有向グラフにおける次数

 ( a )  

( a )  

( a )

無向グラフにおける次数の例 無向グラ おける次数 例

b

aa

c δ(b) 2

δ(c) = 1 δ(b) = 2

δ(a) = 3 ←注意！自己閉路の場合は，二重にカウントする

有向グラフにおける次数の例 有向グラ おける次数 例

b

aa

c δ⁺(b) 1 δ (b) 1

δ⁺(c) = 0, δ^-(c) = 1 δ⁺(b) = 1, δ^-(b) = 1

δ⁺(a) = 2, δ^-(a) = 1 ←注意！

•

 ^{v E}

V v

2 )

( 





–

E v

v   

 ^

^{( ) }

^{( )}

V v V

v 

6 5

(Graph Isomorphism) 6.5

(Graph Isomorphism)

•

…

G, G’

G

G’

•

G G = (V E) (V, E), G G’ = (V’ (V , E E’) )

(isomorphic)



V V  

 :

  ^b  ^{( ) ( ) b}  ^

す とを言う

  ^{a b ,   E}  ^{ ( ), ( ) a  b}  ^{ E }

同型グラフの例

1 2

グラフG φ(1) = u

φ(2) = v φ(3) = w

6 3

φ(3) = w φ(4) = x φ(5) = y φ(6) = z

5 4 グラフG'

φ(6) = z

u v w x yy z

6 6 いろいろなグラフ 6.6 いろいろなグラフ

•

(Complete graph)

異なるどの二つの頂点の間にもただ

1

1

•

(subgraph)

グラフ

G' = (V' E')

G = (V E)

G' = (V', E')

G = (V, E)

V' ⊆ V, E' ⊆ E

いくつかの完全グラフ

K₂ K₃ K₄ K₅

導され グ

•

(

)

単純グラフ

G = (V, E)

V' ⊆ V

V'

G

G' (V'

V'

G

G' = (V', E')

部グ

 

 ^{V E V V} 

G    ,    

• 2

(bipartite graph)

グラフ

G = (V, E)

2

V

, V

 V

が存在して，以下の二つの条件を満たす．

–

V

 V

 V , V

 V

 

– 任意の辺は，一方の端点を に持ち，他方の端 点を に持つ．

V

V

2 部グラフの例 2 部グラフの例

V₁ V₂

6.7 経路 (path)

•

G = (V, E), v, v' ∈ V

v

’

k ( ≧ 1)

( th)

v’

k ( ≧ 1)

(path)

頂点の列

 ^{v v v} 

で，

 ^v

^{, v}

^{,  , v}



で，

を満たすものを言う

 ^{v v}  ^E  ^{i k} 

v v

v

v

 ,

  ,

,

  1 ,...,

を満たすものを言う．

v

v₀  v₁ v₂ v_k  v

経路の例 経路の例

v4

v5

v1₁ v v v

v v₂ v₃ v₆

 ^v

^{, v}

^{, v}

^{, v}

^{, v}

^{, v}

^{, v}

^{, v}



•

(simple path) …

がすべて異なる

v

v

v

,

,  ,

•

(cycle) … v = v'

(

)

も一つの辺を持つ

)

•

(simple cycle) …

がすべ 異なる ^k

v v

v

,

,  ,

• v = v'

v

v'

v'

v

(reachable)

•

…

(acyclic) ( y )

•

DAG (directed acyclic graph)

acyclic graph)

6 8 連結性 (connectivity) 6.8 連結性 (connectivity)

•

u, v

u = v

v

v

v

,

,  ,

すとき，

u, v

k 1

0

–

–

v v

v

u 

, 

       



^{i }  ^k    ^v

^v

 ^{ E }  ^v

^v

 ^{ E} 



1

1

, ,

,..., 1

どの

2

6 9 連結成分 ( connected component ) 6.9 連結成分 ( connected component )

• u

v … 2

u, v

•

•

–

V

V

, V

,  , V

–

k 2



^{i k} 

V

1  

る辺の集合を

E

• …

E

 ^{V E} 

G  ,

連結グラフの例 連結グラフの例

すべての頂点の間に経路があるわけではないが，

6.10 有向グラフにおける強連結性 (strong connectivity)

• …

u, v

v u 

•

における

V



 ^{V V V}

–

V

–

 ^V

^{, V}

^{,  , V}

 ^{i k} 

V

1  

れる辺の集合を

• …

 

i

E

 ^{V E} 

G

  ^V

^E

 ^…

G ,

強連結成分の例

強連結成分