Graph Vocabulary

In this article, we are going to define important words used to describe graphs.

When we want to move through out a graph we do so by traveling from one vertex, across an edge, to another vertex.

There are six basic terms we should feel comfortable with before moving forward.

1. Walk
2. Trail
3. Path
4. Closed Walk
5. Circuit
6. Simple Circuit

Let's begin.

1. Walk

A walk is a finite (there is an ending vertex) sequence of neighboring vertices and edges from some start vertex to some end vertex.

To simplify this, a walk is simple saying; we start at vertex $v_{0}$ and travel along some neighboring edges and vertices until we make it to $v_{n}$, our target vertex.

It does not matter what path we take, if we go in circular loops, stop at the same vertex several times or go straight to the vertex, it is considered a walk.

The 'walk' will be the basis definition for the remainder of our terms. In some form or another our other terms are a specific style of a walk.

Below we have a simple example of a walk. Starting at $v_{0}$ and traveling to $v_{6}$

Our walk is equal to the following sequence,

If we walk through this sequence (see what I did there?) we see that we make some redundant choices. In other words, we take a very inefficient set of steps to get to our final vertex.

This is true, however, this stresses that a walk is a very broad term. As we proceed, we define new terms that allow us to set specific rules our walk must follow.

Our first example of this is a trail.

2. Trail

A trail is a walk that does not have repeated edges.

A trail is still a walk, but it specifically tells us that we should not traverse an edge more than one time. With this simple rule our graph already improves.

We have traversed one less edge, awesome. Our new traversal looks like the following,

This is great but we still hit $v_{2}$ twice and we know that we can do better. So what is next?

Next lets add to our trail term. Trails tell us we cannot repeat edges, what about not repeating vertices?

Introducing paths.

3. Paths

A path is a walk that does not have any repeated edges or repeated vertices.

We can also say that a path is a trail without repeated vertices.

So again starting at v_0 we get the following sequence.

Now the path we take looks pretty dang good to me. No repeated edges (trail) and now no repeated edges (path). Life is good and we reduced the amount of steps necessary drastically.

Now we move away from the sort of linear paths and look at circular traversals.

Our first term is the circular walk.

4. Closed Walk

A closed walk is a walk that starts and ends at the same vertex.

Same as before, a closed walk is a very loose rule. We can repeat edges and vertices as long as we end at the same vertex that we started at.

Lets look at a simple example.

Yes this works, but notice that we repeat the Edge($v_{0}$, $v_{2}$) twice and we also visit $v_{2}$ twice. Can we do better?

Let's start by removing the repeated edge.

5. Circuit

A circuit is a closed walk that has at least one edge and no repeated edges. Exactly the same concept as a trail to a walk.

Now our traversal should go like this.

While this graph does not have a repeated edge it did not improve the number of steps required. However, it does stress the difference between a closed walk and a circuit. NO REPEATED EDGES.

Finally, let's remove the repeated vertex.

6. Simple Circuit

A simple circuit is a closed walk that does not contain any repeated edges or vertices.

The only vertex that may be visited twice is the first and last.

Our final graph traversal looks like the following,

Remember, these are just examples to demonstrate the terms. We could have definitely done somethings better. All that matters is we understand the important terminology.

Summary

In summary, we discussed 6 important terms used to define the traversal of graphs.

We defined and saw examples for the following terms: Walk, Trail, Path, Closed Walk, Circuit, Simple Circuit

I hope this article was helpful and until next time, happy coding!