Graph Theory

Walks Paths And Circuits

WALKS, PATHS AND CIRCUITS

Walk: A walk is defined as a finite alternative sequence of vertices and edges, of the form viej, vi 1 ej 1, vi 2, ......., ekvm which begins and ends with vertices, such that
(i) each edge in the sequence is incident on the vertices preceding and following it in the sequence.
(ii) no edge appears more than once in the sequence, such a sequence is called a walk or a trial in G.

For example, in the graph shown in Figure 34, the sequences v2e4v6e5v4e3v3 and v1e8v2e4v6e6v5e7v5 are walks.

Note that in the first of these, each vertex and each edge appears only once whereas in the second each edge appears only once but the vertex v5 appears twice.
These walks may be denoted simply as v2v6v4v3 and v7v2v6v5v5 respectively.

The vertex with which a walk begins is called the initial vertex and the vertex with which a walk ends is called the final vertex of the walk. The initial vertex and the final vertex are together called terminal vertices. Non-terminal vertices of a walk are called its internal vertices.

  1. A walk having u as the initial vertex and v as the final vertex is called a walk from u to v or briefly a u – v walk.
  2. A walk that begins and ends at the same vertex is called a closed walk. In other words, a closed walk is a walk in which the terminal vertices are coincident.
  3. A walk that is not closed is called an open walk.

In other words, an open walk is a walk that begins and ends at two different vertices.

For example, in the graph shown in Figure 34.

  1. v1e9v7e8v2e1v1 is a closed walk and v5e7v5e6v6e5v4 is an open walk.

Path: In a walk, a vertex can appear more than once. An open walk in which no vertex appears more than once is called a simple path or a path. For example, in the graph shown in Figure 34.

v6e5v4e3v3e2v2 is a path whereas v5e7v5e6v6 is an open walk but not a path.

Circuit: A closed walk with atleast one edge in which no vertex except the terminal vertices appears more than once is called a circuit or a cycle. For example, in the graph shown in Figure 34, v1e1v2e8v7e9v1 and v2e4v6e5v4e3v3e2v2 are circuits. But v1e9v7e8v2e4v6e5v4e3v3e2v2e1v1 is a closed walk but not a circuit.

Note :

(i) In walks, path and circuit, no edge can appears more than once.
(ii) A vertex can appear more than once in a walk but not in a path.
(iii) A path is an open walk, but an open walk need not be a path.
(iv) A circuit is a closed walk, but a closed walk need not be a circuit.

Length: The number of edges in a walk is called its length. Since paths and circuits are walks, it follows that the length of a path is the number of edges in the path and the length of a circuit is the number of edges in the circuit. A circuit or cycle of length k, (with k edges) is called a k-circuit or a k-cycle. A k-circuit is called odd or even according as k is odd or even. A 3-cycle is called a triangle.

For example, in the graph shown in Figure 34,

  1. The length of the open walk v6e6v5e7v5 is 2
  2. The length of the closed walk v1e9v7e8v2e1v1 is 3
  3. The length of the circuit v2e4v6e5v4e3v3e2v2 is 4
  4. The length of the path v6e5v4e3v3e2v2e1v1 is 4
  5. The circuit v1e1v2e8v7e10v1 is a triangle.

Note :

(i) A self-loop is a 1-cycle.
(ii) A pair of parallel edges form a cycle of length 2.
(iii) The edges in a 2-cycle are parallel edges.