4.04 Walks, trails and paths

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.

We can record this walk as the sequence A, \, B, \, A, \, E, \, F, \, D, \, E.

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 here shows a different walk on the same graph; this time a closed walk.

This walk has sequence A, \, B, \, A, \, D, \, F, \, C, \, G, \, D, \, E, \, A.

The walk 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.

Examples

Example 1

Select the valid walk in this network:

A

E, \, D, \, C, \, B, \, A

B

A, \, B, \, E, \, C, \, D

C

C, \, D, \, A, \, E, \, D

D

B, \, C, \, D, \, B, \, A

Worked Solution

Create a strategy

Choose the sequence where the network always has edges connecting one vertex to the next.

Apply the idea

The sequence E, \, D, \, C, \, B, \, A in option A is a valid walk because there are edges from each vertex to the next in the sequence.

In option B, E comes after B, but the vertices B and E are not connected, so it is not a valid walk.

In option C, E comes after A, but the vertices A and E are not connected, so it is not a valid walk.

In option D, B comes after D, but the vertices B and D are not connected, so it is not a valid walk.

So the correct answer is option A.

Example 2

State a closed walk for the graph, starting from H with 3 edges.

Worked Solution

Create a strategy

Find a walk that starts and finishes at H with 3 edges.

Apply the idea

A closed walk for the graph, starting from H with 3 edges is: H, \, X, \, Y, \, H

Another closed walk is the same path but in the other direction: H, \, Y, \, X, \, H

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:

The blue walk A,\,D,\,F,\,E,\,D,\,G,\,C,\,F on the left is an open trail, since no edge is used more than once, and it is open. The red walk G,\,C,\,F,\,E,\,D,\,F,\,A,\,D,\,G on the right is a closed trail (circuit), since no edge is used more than once, and it is closed.

• A trail is a walk where no edge is repeated.

• An open trail starts and ends on different vertices.

• A closed trail (circuit) starts and ends on the same vertex.

• All trails are walks and all circuits are closed walks.

Examples

Example 3

Which of the following is a circuit in the network shown?

A

C,\,B,\,A,\,E,\,D,\,C

B

B,\,A,\,E,\,C,\,D,\,B

C

B,\,C,\,A,\,E,\,D,\,C

D

D,\,C,\,B,\,A,\,E,\,D

Worked Solution

Create a strategy

Choose the trail that starts and ends on the same vertex and has no repeat edges.

Apply the idea

Option A starts and ends on C. The edges covered are CB, BA, AE, ED, and DC. So no edges are repeated. So it is a circuit.

Option B starts and ends on B. The edges covered are BA, AE, EC, CD, and DB. So no edges are repeated. So it is a circuit.

Option C is not a circuit because it does not start and end on the same vertex.

Option D starts and ends on D. The edges covered are DC, CB, BA, AE, and ED. So no edges are repeated. So it is a circuit.

So the correct answers are options A, B, and D.

Watch question walkthrough

Example 4

State the shortest possible closed trail that starts at H.

Worked Solution

Create a strategy

Find the shortest walk that starts and finishes at H and passes each edge only once.

Apply the idea

The shortest possible closed trail that starts at H has 4 edges: H, \, D, \, F, \, G, \, H

We could also go in the other direction: H, \, G, \, F, \, D, \, H

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:

The open path on the left is D,\,G,\,C,\,F,\,E,\,A, and the closed path (called a cycle) on the right is B,\,C,\,F,\,D,\,E,\,A,\,B.

• A path is a walk where no vertex is repeated (which also means that no edges can be repeated).

• An open path starts and ends on different vertices.

• A closed path (cycle) starts and ends on the same vertex.

• All paths are walks (and trails) and all cycles are closed walks (and closed trails).

Examples

Example 5

Consider the network below:

a

Find a path that starts at H, visits two other vertices, and then reaches B.

Worked Solution

Create a strategy

Start at vertex H and choose an edge where the next vertex can make two more moves to reach vertex B.

Apply the idea

If we start at H and move to X, we can't make it to B with only two more moves.

If we start at H and go to Y, then go to Q, then go to B, we achieve our goal. So the path is:\text{Path} = H,\,Y,\,Q,\,B

b

Now find a path that starts at H, visits four other vertices, and then reaches B.

Worked Solution

Create a strategy

Start at vertex H and choose an edge where the next vertex can make four more moves without reapeating a vertex to reach vertex B.

Apply the idea

The following path starts at H, visits four vertices, X,\,Y,\,Q,\,W, to reach B:\text{Path} = H,\,X,\,Y,\,Q,\,W,\,B

Example 6

Starting with vertices P,\,R,\,T, state the longest possible closed trail for the graph.

Worked Solution

Create a strategy

Find the longest train that starts at P, goes to R, then to T, and finishes at P, without repeating any edges.

Apply the idea

Using trial and error we can find the following path:\text{Closed trail} = P,\,R,\,T,\,S,\,Q,\,U,\,P

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 to B via the optimal (fastest) path. Here are three paths we could take:

• The red path AB will take 9 minutes.

• The blue path ACEB will take 2+3+4=9 minutes.

• The green path ADB will take 4+4=8 minutes.

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

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

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 (which take 6 minutes) when the path could flow directly from C to D in just 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.

Here is a directed graph. This time, the streets are all one-way.

Let’s try a few paths out:

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

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

• The purple path ABCEG takes6+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, the shortest one so far, we can shorten the trip from D to G by going through E.

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

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.

Examples

Example 7

The following map shows all possible routes in Mohamad's town. Mohamad travels from his home to his friend's house on a daily basis.

If Mohamad's house is vertex C, and his friend's house is vertex I, what would be the shortest path between the two places?

Worked Solution

Create a strategy

To find the shortest path, start at vertex C, and choose the shortest edge connected to it. Then repeat the same process on the next vertex until you reach vertex I.

Apply the idea

From C, 12 \lt 21 so we move to A.

From A, 16 \lt 23 so we move to B.

From B, 11 \lt 15 \lt 24 but if we move to E we will be moving back towards C and further away from I. So we use the edge with 15 and move to F.

From F, even though 22 \gt 20, we choose the direct path to I, because overall it is the shortest.

The shortest path is:\text{Shortest path} = C,\,A,\,B,\,F,\,I