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$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 below 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$A,B,A,D,F,C,G,D,E,A.
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.
Select the valid walk in this network:
$E,D,C,B,A$E,D,C,B,A
$A,B,E,C,D$A,B,E,C,D
$C,D,A,E,D$C,D,A,E,D
$B,C,D,B,A$B,C,D,B,A
$E,D,C,B,A$E,D,C,B,A
$A,B,E,C,D$A,B,E,C,D
$C,D,A,E,D$C,D,A,E,D
$B,C,D,B,A$B,C,D,B,A
State a closed walk for the graph, starting from $H$H with $3$3 edges.
Enter each vertex as a capital letter, separated by commas.
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$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$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.
Which of the following is a circuit in the network shown? Select all the correct options.
$C,B,A,E,D,C$C,B,A,E,D,C
$B,A,E,C,D,B$B,A,E,C,D,B
$B,C,A,E,D,C$B,C,A,E,D,C
$D,C,B,A,E,D$D,C,B,A,E,D
$C,B,A,E,D,C$C,B,A,E,D,C
$B,A,E,C,D,B$B,A,E,C,D,B
$B,C,A,E,D,C$B,C,A,E,D,C
$D,C,B,A,E,D$D,C,B,A,E,D
State the shortest possible closed trail that starts at $H$H.
Enter each vertex as a capital letter, separated by commas.
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$D,G,C,F,E,A, and the closed path (called a cycle) on the right is $B,C,F,D,E,A,B$B,C,F,D,E,A,B.
In this question we will find two different paths from $H$H to $B$B in the network below:
Find a path that starts at $H$H, visits two other vertices, and then reaches $B$B.
Enter each vertex as a capital letter, separated by commas.
Now find a path that starts at $H$H, visits four other vertices, and then reaches $B$B.
Enter each vertex as a capital letter, separated by commas.
Starting with vertices $P,R,T$P,R,T, state the longest possible closed trail for the graph.
Enter each vertex as a capital letter, separated by commas.
Every sequence of edges is a walk. A walk can be open (start/end vertices different) or closed (start/end vertices same).
If edges can’t repeat, the walk is a trail. A closed trail is a circuit.
If vertices can’t repeat, the walk is a path. A closed path is a cycle.
Walks, paths, trails, circuits and cycles do not need to use every edge or every vertex in the graph.
A path is:
A sequence of edges joined by vertices where no vertex is repeated (excluding the possibility of the start and end vertex).
An edge that connects a vertex to itself.
A sequence of edges that start and end at the same vertex.
A sequence of edges joined by vertices where no edge is repeated.
A sequence of edges joined by vertices where no vertex is repeated (excluding the possibility of the start and end vertex).
An edge that connects a vertex to itself.
A sequence of edges that start and end at the same vertex.
A sequence of edges joined by vertices where no edge is repeated.
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:
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.
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$C, and his friend's house is vertex $I$I, what would be the shortest path between the two places? List the vertices separated by a comma (e.g. $A,B,C,D$A,B,C,D)
The graph below shows the time in hours taken to travel between various country towns.
Determine the least amount of time needed to travel between towns $P$P and $X$X.
State the route that would achieve this by listing the vertices in order, separated by commas.
explain the meaning of the terms: walk, trail, path, closed walk, closed trail, cycle, connected graph, and bridge
investigate and solve practical problems to determine the shortest path between two vertices in a weighted graph (by trial-and-error methods only)