Open Graph Walk

From GM-RKB
Jump to navigation Jump to search

An Open Graph Walk is a graph walk with its first vertex and last vertex are not the same.



References

2013

  • http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Walks
    • A walk is an alternating sequence of vertices and edges, beginning and ending with a vertex, where each vertex is incident to both the edge that precedes it and the edge that follows it in the sequence, and where the vertices that precede and follow an edge are the end vertices of that edge. A walk is closed if its first and last vertices are the same, and open if they are different.

      The length l of a walk is the number of edges that it uses. For an open walk, l = n–1, where n is the number of vertices visited (a vertex is counted each time it is visited). For a closed walk, l = n (the start/end vertex is listed twice, but is not counted twice). In the example graph, (1, 2, 5, 1, 2, 3) is an open walk with length 5, and (4, 5, 2, 1, 5, 4) is a closed walk of length 5.

      A trail is a walk in which all the edges are distinct. A closed trail has been called a tour or circuit, but these are not universal, and the latter is often reserved for a regular subgraph of degree two.