Next Sec.: パスの数え上げ Upper Sec.: グラフに関するアルゴリズム Prev. Sec.: グラフに関するアルゴリズム

グラフとその表現

(V,E):グラフ(graph)

V={V_i|i=1...r}:頂点(vertex)の有限集合

E={(V_i,V_j)}:辺(edge)の有限集合

グラフの図形表現

グラフにおける基本概念

1. パス（path）
   

   

   x₁からx_kへのパス

2. サイクル（cycle）
   x₁=x_kとなるパス
3. 木（tree）
   サイクルを含まない（部分）グラフ
4. 展張木（spanning tree） 与えられたグラフのサイクルを含まない部分グラフで極大なもの．
   グラフを張る木ともいう．

以下の仮定

1. 無向グラフのみを扱う
2. 次のような辺は含まない
   • 自分自身でサイクルとなる辺
   • 重複する辺
   

計算機におけるグラフの表現

1. 隣接行列（adjacency matrix）
   

   A = (a_ij)
   

          1   (i,j) in E
   aij = 
          0   otherwise
   

   	1	2	3	4	5
   1	0	1	1	0	0
   2	1	0	1	1	0
   3	1	1	0	1	1
   4	0	1	1	0	1
   5	0	0	1	1	0

2. 結合行列（incidence matrix）

   B = (b_ij)
   

          1   i in ej
   bij = 
          0   otherwise
   

   	e1	e2	e3	e4	e5	e6	e7
   1	1	0	1	0	0	0	0
   2	1	1	0	1	0	0	0
   3	0	0	1	1	1	1	0
   4	0	1	0	0	1	0	1
   5	0	0	0	0	0	1	1

3. 隣接リスト（adjacency list）
   

   
   

   参考：隣接リストの配列表現
   

   1	2	3	0	0	0
   2	1	3	4	0	0
   3	1	2	4	5	0
   4	2	3	5	0	0
   5	3	4	0	0	0