Walks, Paths & Circuits
Walks, Paths & Circuits
·
A walk is defined as a finite alternating
sequence of vertices and edges, beginning and ending with vertices, such that
each edge is incident with the vertices preceding and following it.
o
No edge appears (is covered or traversed) more
than once in a walk.
o
A vertex, however, may appear more than once.
·
In Figure for instance, v1 a v2 b v3 c v3 d v4 e
v2 f v5 is a walk shown with heavy lines.
o
A walk is also referred to as an edge train or a
chain.
o
The set of vertices and edges constituting a
given walk in a graph G is clearly a subgraph of G.
·
o
Vertices with which a walk begins and ends are
called its terminal vertices.
o
Vertices v1 and v5 are the terminal vertices of
the walk shown in Figure.
·
It is possible for a walk to begin and end at
the same vertex.
o
Such a walk is called a closed walk.
o
Closed walk is also called a Path.
·
A walk that is not closed is called an open
walk.
o
An open walk in which no vertex appears more
than once is called a path (or a simple path or an elementary path).
·
A path does not intersect itself.
o
The number of edges in a path is called the
length of a path.
o
The terminal vertices of a path are of degree
one,
§
and the rest of the vertices (called
intermediate vertices) are of degree two.
·
A closed walk in which no vertex (except the
initial and the final vertex) appears more than once is called a circuit.
·
·
A circuit is also called a cycle, elementary
cycle, circular path, and polygon.