4.04 Walks, trails and paths

Walks

A walk is the most general definition of how we can move around a graph. If we start at a vertex and then move along an edge to a new vertex, we are starting a walk. If we have a directed graph, we move in the direction of the arrows.

We can continue the walk by selecting another edge coming out of the second vertex, then a third edge coming out of the third vertex, and so on.

In a simple graph, we can represent a walk by a sequence of vertices. Here is a simple, undirected graph, with the arrows representing a walk around the graph:

If a walk starts and ends at the same vertex then it is closed, and if it starts and ends at different vertices then it is open.

The walk marked on the diagram above is an open walk.

The diagram below shows a different walk on the same graph; this time a closed walk.

The walk shown above is a closed walk because it starts and ends at the same vertex.

We can also tell that it is a closed walk by looking at the sequence (without seeing the diagram) that the walk is closed because the sequence starts and ends with the same letter.

 

Practice questions

Question 1

Question 2

 

Trails and circuits

If a walk does not use the same edge more than once, then it is a trail - it is an open trail if it’s open and a closed trail (also called a circuit) if it is closed. Here is one of each on the same graph:

 

Practice questions

Question 3

Question 4

 

Paths and cycles

If a walk does not use the same vertex more than once (other than at the start and end) we call it a path. When a path begins and ends at the same vertex it is a closed path, which is usually called a cycle.

Here are two different paths on the same graph:

 

Practice questions

Question 5

Question 6

 

Summary

 

 

Practice question

Question 7

 

Shortest path by inspection

A common problem posed in networks is to find the path of lowest weight between two vertices. For example, finding the best (fastest, shortest, cheapest) route between two destinations.

Let’s take a look at this network of towns:

The weights represent travel time in minutes, and we want to get from $A$A to $B$B via the optimal (fastest) path. Here are three paths we could take:

• The red path $AB$AB will take $9$9 minutes.
• The blue path $ACEB$ACEB $2+3+4=9$2+3+4=9 minutes.
• The green path $ADB$ADB will take $4+4=8$4+4=8 minutes.

This last path is close to the answer, but we can get from $A$A to $D$D even faster if we take a shortcut through $C$C:

This path does not look like the fastest but takes $2+1+4=7$2+1+4=7 minutes, and is the quickest way to get from $A$A to $B$B.

Can you see a path that has not been listed? Can you justify not checking this path?

In theory, when trying to find the shortest path by observation we should check every path and its length. However, we can eliminate some options as possibilities by looking at the structure of the network carefully first. Firstly, recall no path will pass through the same vertex or use the same edge more than once. Also, the shortest path will not take "the long way around". For our example above the shortest path would never use the section $C,E,D$C,E,D (which take $6$6 minutes) when the path could flow directly from $C$C to $D$D in just $1$1 minute. 

We can perform the same sort of analysis on directed graphs as well, just be careful to follow the direction on the arrows when forming paths. For example:

This time, the streets are all one-way! Let’s try a few paths out:

The blue path $AFG$AFG takes $10+11=21$10+11=21 minutes.

The green path $ADG$ADG takes $4+12=16$4+12=16 minutes.

The purple path $ABCEG$ABCEG takes $6+1+5+5=17$6+1+5+5=17 minutes.

We can now check more paths, thinking about taking detours on paths we already know about. Starting from the path $ADG$ADG, the best one we have found so far, we can improve the trip from $D$D to $G$G by going through $E$E:

Going along the path $ADEG$ADEG only takes $4+6+5=15$4+6+5=15 minutes, and this is the fastest route.

Reflect: For directed networks you can use a systematic approach by branching out from the start node and finding the shortest way to get to each node by progressively labelling the network until you reach the destination node.

In general, when solving shortest path problems, using trial and error is an appropriate method. However, we need to be careful as it can sometimes be difficult to ensure all paths are checked. Systematically recording the paths and eliminating paths that contain extended detours from the shortest path found so far can help avoid missing possible solutions and is effective for finding the shortest path on networks that are relatively small or not overly complex.

For larger, more complex networks, and when using technology to solve such problems a fully systematic approach is required. One such approach called Dijkstra's algorithm is explored in the investigation for this chapter. After examining this algorithm it is worth revisiting the shortest path problems from this exercise with a different approach.

 

Practice question

Question 8

Question 9