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 v_{i}e_{j}, v_{i} 1 e_{j} 1, v_{i} 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 v_{2}e_{4}v_{6}e_{5}v_{4}e_{3}v_{3} and v_{1}e_{8}v_{2}e_{4}v_{6}e_{6}v_{5}e_{7}v_{5} 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 v_{2}v_{6}v_{4}v_{3} and v_{7}v_{2}v_{6}v_{5}v_{5} 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.
- 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.
- 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.
- 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.
- v_{1}e_{9}v_{7}e_{8}v_{2}e_{1}v_{1} is a closed walk and v_{5}e_{7}v_{5}e_{6}v_{6}e_{5}v_{4} 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.
v_{6}e_{5}v_{4}e_{3}v_{3}e_{2}v_{2} is a path whereas v_{5}e_{7}v_{5}e_{6}v6 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, v_{1}e_{1}v_{2}e_{8}v_{7}e_{9}v_{1} and v_{2}e_{4}v_{6}e_{5}v_{4}e_{3}v_{3}e_{2}v_{2} are circuits. But v_{1}e_{9}v_{7}e_{8}v_{2}e_{4}v_{6}e_{5}v_{4}e_{3}v_{3}e_{2}v_{2}e_{1}v_{1} 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,
- The length of the open walk v6e6v5e7v5 is 2
- The length of the closed walk v1e9v7e8v2e1v1 is 3
- The length of the circuit v2e4v6e5v4e3v3e2v2 is 4
- The length of the path v6e5v4e3v3e2v2e1v1 is 4
- 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.