Definition:Walk
Contents |
Definition
A walk on a graph is an alternating series of vertices and edges, beginning and ending with a vertex, in which each edge is incident with the vertex immediately preceding it and the vertex immediately following it.
A walk between two vertices $u$ and $v$ is called a $u$-$v$ walk.
A walk is closed if the first vertex is the same as the last. Otherwise it is open.
Length
The length of a walk is the number of edges it has, counting repeated edges as many times as they appear.
Trails and Paths
A trail is a walk in which all edges are distinct.
A path is a walk in which all vertices are distinct.
Circuits and Cycles
A closed trail is called a circuit.
A closed path is called a cycle.
Differences in Terminology
Some sources refer to a walk as a path, and use the term simple path to define what we have here as a path.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 2.3$
