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.

We can perform the same sort of analysis on directed graphs as well:

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.

Using trial and error is an appropriate method however we need to be careful and sometimes it is difficult to ensure all paths are checked. Note that it's important that the paths are listed as part of your working for this type of question.

 

Practice question

Question 8

 

Shortest path algorithm

In the previous section, we found the shortest path by trial and error, however, it can often be difficult to find the shortest path this way, even for small networks.

The worked example below, demonstrates a method to find the shortest path between two vertices in a systematic way.

We find the shortest path to each vertex, from the starting vertex, writing the cumulative distance on the vertices as we work through the network from start point to finish point.

The best way to learn this method is through an example.

 

Worked example

This network represents the travel times for an ambulance to get between the seven townships it services:

The ambulance is parked at the hospital in Arda when it receives a call for help from Gilgandra. This is an emergency, and the ambulance needs to get there as fast as possible - what route should it take?

First of all, we are going to get rid of the information we won’t be using. We will replace each of the towns with their first letter, move the vertices around a bit, remove the mountains, lakes, and forest, and straighten out the edges:

Take a moment to see how the two networks match up - they are two equivalent representations of the same network.

To find the shortest path from $A$A to $G$G follow the steps below:

Step 1:

• Start at $A$A and write $0$0 in the vertex to indicate this is the start.
• Calculate the distance from $A$A to $B$B is $0+4=4$0+4=4 and write $4$4 on edge $AB$AB (near the vertex $B$B).
• Calculate the distance from $A$A to $D$D is $0+6=6$0+6=6, and write $6$6 on edge $AD$AD (near the vertex$D$D).
• A quick check tells us the shortest path to $D$D is from $A$A therefore we can write $6$6 in the vertex for $D$D. Another quick check tells us path $ADCB$ADCB is more than $4$4, therefore we can write $4$4 in the vertex for $B$B.
• Important! Only write a number in the vertex when you have checked every edge leading into the vertex. Also, if it's not possible to write in the vertex circle then you can put a box around the lowest number instead.

Step 2:

• From $B$B add $4$4 and $4$4 to calculate path $ABC$ABC is $8$8, and write $8$8 on edge $BC$BC near to vertex $C$C.
• From $D$D add $6$6 and $3$3 to make $9$9 and write $9$9 on edge $DC$DC near to vertex $C$C.
• Now vertex $C$C has all edges complete with a number. We see all edges into $C$C are complete and that $8$8 is the lowest number therefore $8$8 is written in vertex $C$C. This means the shortest path from $A$A to $C$C is length $8$8.

Step 3

• From $B$B add $4$4 and $12$12 to make $16$16; a quick check confirms that this is clearly the shortest path so we can write $16$16 in vertex $F$F.
• From $B$B add $4$4 and $22$22 to make $26$26, and write $26$26 on edge $BG$BG near vertex $G$G.
• From $C$C add $8$8 and $16$16 to make $24$24, and write $24$24 on edge $CG$CG near vertex $G$G.
• From $C$C add $8$8 and $14$14 to make $22$22, and write $22$22 on edge $CE$CE near vertex $E$E.

Step 4

• From $F$F add $16$16 and $8$8 to make $24$24 and write $24$24 on edge $FE$FE near vertex $E$E.
• We can see that $22$22 is smaller than $24$24 so $22$22 is written in vertex $E$E.

Step 5

• From $F$F add $16$16 and $12$12 to make $28$28 and write $28$28 on edge $FG$FG near vertex $G$G.
• From $E$E add $22$22 and $6$6 to make $28$28 and write $28$28 on edge $EG$EG near vertex $G$G.
• We can now see that all four edges leading into $G$G have a number written on them. The smallest number going into vertex $G$G is $24$24 so we write $24$24 in vertex $G$G.

Step 6

• Follow the numbers written in the vertices backwards through the network to find the shortest path.
• Start at $G$G. The vertex contains the number $24$24 so we follow and highlight the path labelled $24$24 (edge $GC$GC) to $C$C.
• From $C$C, which contains the number $8$8, we follow and highlight the path labelled $8$8 (edge $CB$CB) to $B$B.
• From $B$B, which contains the number $4$4, we follow and highlight the path labelled $4$4 (edge $BA$BA) to $A$A.

Solution: The shortest path for the ambulance is $A$A, $B$B, $C$C, $G$G and the time taken is $24$24 minutes.

 

Practice question

Question 9