Brogramo
Guest
Guest

What is a Closed Walk in a Directed Graph?

To understand what a closed walk is, we need to understand walks and edges.

A walk is going from one vertex to the next in a directed graph. A line connected two vertices is known as an edge, so we walk from one vertex to the next by following an edge. In other words, a walk is a sequence of edges joining a sequence of vertices.

There are different names for different types of walks. A closed walk in a directed graph starts and ends at the same vertex. For example, going from vertex 1 to vertex 2 and back to vertex 1 is a closed walk because the walk started at vertex 1 and ended at vertex 1.

Example: Closed walk

Let’s say that W is a walk.

W = (a, b, c, b, d)

Each letter in W is a vertex on the graph, a is a vertex, b is a vertex…, etc.

We can traverse the vertices if they are related (connected).

If we walk from a -> b -> c -> a -> d -> a, we would say that the walk is a closed walk because we started at vertex a and stopped at vertex a.

Example: Length of a closed walk

The length of a closed walk is the number of edges in the walk.

If we walk from a -> b -> c -> a -> d -> a, we would have 5-edges. Since the length of a walk is the number of edges , the walk a -> b -> c -> a -> d -> a is of length 5.