80

Walks, Trails, Path, Circuit and Cycle in Discrete mathematics

Walk:

A walk can be defined as a sequence of edges and vertices of a graph. When we have a graph and traverse it, then that traverse will be known as a walk. In a walk, there can be repeated edges and vertices. The number of edges which is covered in a walk will be known as the Length of the walk. In a graph, there can be more than one walk.

So for a walk, the following two points are important, which are described as follows:

• Edges can be repeated
• Vertex can be repeated

For example: In this example, we have a graph, which is described as follows:

In the above graph, there can be many walks, but some of them are described as follows:

Types of Walks

There are two types of the walk, which are described as follows:

1. Open walk
2. Closed walk

Open Walk:

A walk will be known as an open walk in the graph theory if the vertices at which the walk starts and ends are different. That means for an open walk, the starting vertex and ending vertex must be different. In an open walk, the length of the walk must be more than 0.

Closed Walk:

A walk will be known as a closed walk in the graph theory if the vertices at which the walk starts and ends are identical. That means for a closed walk, the starting vertex and ending vertex must be the same. In a closed walk, the length of the walk must be more than 0.

Note: There are some important points which we should learn:

• The walk will be known as the Trivial walk if length of the walk = 0.
• In case of the open walk and closed walk, the edges and vertices can be repeated.

Suppose there is a graph, which is described as follows:

In this graph, there is also a closed walk and an open walk, which are described as follows:

Trails

A trail can be described as an open walk where no edge is allowed to repeat. In the trails, the vertex can be repeated.

So for a trail, the following point is important, which is described as follows:

• Vertex can be repeated

In the above graph, there is a tail and closed tail, which is described as follows:

Circuit

A circuit can be described as a closed walk where no edge is allowed to repeat. In the circuit, the vertex can be repeated. A closed trail in the graph theory is also known as a circuit.

So for a circuit, the following two points are important, which are described as follows:

• Edges cannot be repeated
• Vertex can be repeated

In the above graph, there is a circuit, which is described as follows:

Cycle:

A closed path in the graph theory is also known as a Cycle. A cycle is a type of closed walk where neither edges nor vertices are allowed to repeat. There is a possibility that only the starting vertex and ending vertex are the same in a cycle.

So for a cycle, the following two points are important, which are described as follows:

• Edges cannot be repeated
• Vertex cannot be repeated

In the above graph, there is a cycle, which is described as follows:

Path:

A path is a type of open walk where neither edges nor vertices are allowed to repeat. There is a possibility that only the starting vertex and ending vertex are the same in a path. In an open walk, the length of the walk must be more than 0.

So for a path, the following two points are important, which are described as follows:

• Edges cannot be repeated
• Vertex cannot be repeated

In the above graph, there is a path, which is described as follows:

Note: There are some important points which we should learn:

• In discrete mathematics, every path can be a trail, but it is not possible that every trail is a path.
• In discrete mathematics, every cycle can be a circuit, but it is not important that every circuit is a cycle.
• If there is a directed graph, we have to add the term “directed” in front of all the definitions defined above.
• In both the walks and paths, all sorts of graphical theoretical concepts are considered. For example, suppose we have a graph and want to determine the distance between two vertices. In this case, it will be considered the shortest path, which begins at one and ends at the other. Here the length of the path will be equal to the number of edges in the graph.

Important Chart:

The above definitions can be easily remembered with the help of following chart:

Examples of Walks:

There are various examples of the walk, which are described as follows:

Example 1: In this example, we will consider a graph.

Now we have to find out which sequence of the vertices determines walks. The sequence is described below:

1. A, B, G, F, C, D
2. B, G, F, C, B, G, A
3. C, E, F, C
4. C, E, F, C, E
5. A, B, F, A
6. F, D, E, C, B

For those sequences which are walk, we have to also determine whether it is a cycle, path, circuit, or trail.

Solution: In the above graph, A, B, C, D, E, F, and G are the vertices, and the line between two vertices is the edges, i.e., the line between A and B is an edge. To solve this, we will first determine sequence no 1. After that, we will proceed to the next.

1. Sequence no 1 is a Trail because there is no repeated edge in the sequence ABGFCB.
2. Sequence no 2 is a Walk because the sequence BGFCBGA contains the repeated edges and vertices.
3. Sequence 3 is a Cycle because the sequence CEFC does not contain any repeated vertex or edge except the starting vertex C.
4. Sequence no 4 is a Walk because the sequence CEFCE contains the repeated edges and vertices.
5. Sequence no 5 is Not a Walk because there is no direct path to go from B to F. That’s why we can say that the sequence ABFA is not a Walk.
6. Sequence no 6 is a Path because the sequence FDECB does not contain any repeated edges and vertices.

Example 2: In this example, we will consider a graph.

With the help of below sequences, we have to determine the nature of walk in each case:

1. v1, e1, v2, e2, v3, e2, v2
2. v4, e7, v1, e1, v2, e2, v3, e3, v4, e4, v5
3. v1, e1, v2, e2, v3, e3, v4, e4, v5
4. v1, e1, v2, e2, v3, e3, v4, e7, v1
5. v6, e5, v5, e4, v4, e3, v3, e2, v2, e1, v1, e7, v4, e6, v6

Solution: In the above graph, v1, v2, v3, v4, v5, v6 are the vertices and e1, e2, e3, e4, e5, e6, e7 are the edges. To solve this, we will first determine sequence no 1. After that, we will proceed to the next.

1. Sequence no 1 is an Open Walk because the starting vertex and the last vertex are not the same. The starting vertex is v1, and the last vertex is v2.
2. Sequence no 2 does not have a path. It is a trail because the trail can contain the repeated edges and vertices, and the sequence v4v1v2v3v4v5 contains the repeated vertex v4.
3. Sequence no 3 is a Path because the sequence v1e1, v2e2, v3e3, v4e4, and v5 does not contain any repeated edges and vertices.
4. Sequence no 4 is a Cycle because the sequence v1e1, v2e2, v3e3, v4e7, v1 does not contain any repeated vertex or edge except the starting vertex v1.
5. Sequence no 5 does not have a cycle. It is a Circuit because a circuit can contain the repeated vertex, but it cannot contain repeated edges except the starting vertex. The sequence v6e5, v5e4, v4e3, v3e2, v2e1, v1e7, v4e6, v6 contains the repeated vertex v4.

Example 3: In this example, we will consider a graph.

The sequence related to the above graph is described as follows:

1. D, B, E, C, B
2. D, A, D, A, D
3. D, A, B, E, D
4. D, B, E, C, B, A, D

Now we have to determine various the answers to various questions, which are described as follows:

1. We have to determine the sequences which are the directed walks from the above given sequences.
2. We have to determine the lengths of the directed walks.
3. We have to determine the directed walks, which are also directed paths.
4. We have to also determine the directed walks, which are also directed cycles.

Solution:

Here we will solve the first question and find out which sequences are directed walks. After that, we will proceed to the next one.

Part 1:

Here sequences no 1 and 2 are the directed walks because the directed walk can contain repeated vertices and edges.

Sequence no 2 is not a directed walk because the sequence DABED does not contain any edge between A and B.

Sequence no 3 is also not a directed walk because the sequence DBECBAD does not contain any edge between B and A.

Part 2:

With the help of above part, we can say that sequences no 1 and 2 are the directed graph. So we can only find the length of sequences 1 and 2. The length of the directed walks 1 and 2 are 4.

Part 3:

Sequences no 3 and 4 are not the directed walk, so we will only find whether sequences 1 and 2 are the directed path.

Sequences no 1 and 2 are not the directed paths because both sequences contain the repeated vertex. Sequence no 1 contains the repeated vertex B, and sequence no 2 contains the repeated vertex A.

Part 4:

Sequences no 1 and 2 do not contain the directed cycle because the cycle does not contain repeated vertices and edges. Sequence no 1 contains the repeated vertex B, and sequence no 2 contains the repeated vertex A.

---