Walk, trail, and path • A
walk is a finite or infinite
sequence of
edges which joins a sequence of
vertices. : Let be a graph. A finite walk is a sequence of edges for which there is a sequence of vertices such that
Φ(
ei) = {
vi,
vi + 1} for . is the
vertex sequence of the walk. The walk is
closed if
v1 =
vn, and it is
open otherwise. An infinite walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite walk (or
ray) has a first vertex but no last vertex. • A
trail is a walk in which all edges are distinct. • A
path is a trail in which all vertices (and therefore also all edges) are distinct. If is a finite walk with vertex sequence then
w is said to be a
walk from v1
to vn. Similarly for a trail or a path. If there is a finite walk between two
distinct vertices then there is also a finite trail and a finite path between them. Some authors do not require that all vertices of a path be distinct and instead use the term
simple path to refer to such a path where all vertices are distinct. A
weighted graph associates a value (
weight) with every edge in the graph. The
weight of a walk (or trail or path) in a weighted graph is the sum of the weights of the traversed edges. Sometimes the words
cost or
length are used instead of weight.
Directed walk, directed trail, and directed path • A
directed walk is a finite or infinite
sequence of
edges directed in the same direction which joins a sequence of
vertices. : Let be a directed graph. A finite directed walk is a sequence of edges for which there is a sequence of vertices such that for . is the
vertex sequence of the directed walk. The directed walk is
closed if
v1 =
vn, and it is
open otherwise. An infinite directed walk is a sequence of edges of the same type described here, but with no first or last vertex, and a semi-infinite directed walk (or
ray) has a first vertex but no last vertex. • A
directed trail is a directed walk in which all edges are distinct. • A
directed path is a directed trail in which all vertices are distinct. If is a finite directed walk with vertex sequence then
w is said to be a
walk from v1
to vn. Similarly for a directed trail or a path. If there is a finite directed walk between two
distinct vertices then there is also a finite directed trail and a finite directed path between them. A "simple directed path" is a path where all vertices are distinct. A
weighted directed graph associates a value (
weight) with every edge in the directed graph. The
weight of a directed walk (or trail or path) in a weighted directed graph is the sum of the weights of the traversed edges. Sometimes the words
cost or
length are used instead of weight. == Examples ==