next up previous
Next: 6.1 グラフの記述 Up: ソフトウェア第三 講義資料 行列,リスト操作,グラフ,探索表現 Previous: 5.4 状態表現の一般化


6 グラフ

グラフ(graph)$G=(V,E)$は,頂点(vertex)が空でない有限集合$V$と辺(edge)の 集合$E$からなるものととらえることができる. 辺が頂点の順序対$(v,w)$で与えられる場合は,そのグラフは 有向(directed)グラフと呼ばれる.$v$$(v,w)$の始点(head),$w$を終点(tail)と呼ぶ. 辺が互いに異なる頂点である非順序対$(v,w)$のグラ フは無向(undirected)グラフと呼ばれる. 辺が互いに異なるということから$(a,a)$は有向グラフの辺であるが,無向グラフ の辺ではない. グラフ$G=(V,E)$において$(v,w)$$E$に含まれるならば,頂点$w$は頂点 $v$隣接(adjacent)するといいます.頂点$v$に隣接する頂点の個数を $v$次数(degree)という.



generated through LaTeX2HTML. M.Inaba 平成18年5月7日