Next: 6.1 グラフの記述
Up: ソフトウェア第三 講義資料 行列,リスト操作,グラフ,探索表現
Previous: 5.4 状態表現の一般化
6 グラフ
グラフ(graph)は,頂点(vertex)が空でない有限集合と辺(edge)の
集合からなるものととらえることができる.
辺が頂点の順序対で与えられる場合は,そのグラフは
有向(directed)グラフと呼ばれる.をの始点(head),を終点(tail)と呼ぶ.
辺が互いに異なる頂点である非順序対のグラ
フは無向(undirected)グラフと呼ばれる.
辺が互いに異なるということからは有向グラフの辺であるが,無向グラフ
の辺ではない.
グラフにおいてがに含まれるならば,頂点は頂点
に隣接(adjacent)するといいます.頂点に隣接する頂点の個数を
の次数(degree)という.
- 道(path)
道(パス)とは
という形をした
辺の列のことである.この場合,からまでの道といい,その長
さがであるという.1個の頂点は長さ0の道である.単純(simple)
な道とは,その辺と頂点がすべて異なる道のことである.閉路(cycle)
とは,ある頂点から始まりその頂点で終るような長さ1以上の単純な道のこと
である.無向グラフでは閉路の長さは3以上である.
グラフのどの2点,に対してもからへパスがあるとき,そのグラ
フは連結(connected)であると呼ばれる.
- 隣接行列(adjacency matrix)
グラフの表現方法の一つ.グラフの隣接行列は,集合の要素
の個数次の正方行列であり,要素が0または1のものである.に辺
が存在する時のみ,をもつ.辺が存在するかどうかを頻繁
に判定する場合には有効だが,記憶場所が必要となり隣接行列の
初期値を与えるだけでも時間がかかってしまう.行または列をビットベクトル
で表現する方法もある.
- 隣接点リスト(adjacency list)
頂点の隣接点リストとは,に隣接するすべての頂点のリストのことである.
記憶領域はに比例する.
の時によく使われる.
generated through LaTeX2HTML. M.Inaba 平成18年5月7日