next up previous
Next: 7.2 隣接行列(adjacency matrix) Up: 7 グラフ Previous: 7 グラフ


7.1 道(path)

道（パス）とは $(v_1,v_2),(v_2,v_3),...,(v_{n-1},v_{n})$という形をした 辺の列のことである．この場合，$v_{1}$から$v_{n}$までの道といい，その長 さが$n-1$であるという．１個の頂点は長さ０の道である．単純(simple) な道とは，その辺と頂点がすべて異なる道のことである．閉路(cycle) とは，ある頂点から始まりその頂点で終るような長さ１以上の単純な道のこと である．無向グラフでは閉路の長さは３以上である． グラフのどの２点$u$,$v$に対しても$u$から$v$へパスがあるとき，そのグラ フは連結(connected)であると呼ばれる．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日