Hamiltonian paths
Sometimes when finding the shortest path we have additional restrictions such as we require the path to pass through each vertex. For example, if we were planning a delivery route between several different houses, we would be looking for a path that went to each house (vertex) on the delivery route and did so in the shortest time. These types of problems are the basis of the famous travelling salesman problem, defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman.
To find solutions to such problems we look for special paths named after the mathematician W. R. Hamilton. A path that visits each vertex exactly once is called a Hamiltonian path, if the path forms a cycle then it is called a Hamiltonian cycle (or Hamiltonian circuit). A network which contains a Hamiltonian path is known as traceable.
Here are three networks: the first has a Hamiltonian path highlighted, the second has a Hamiltonian cycle highlighted, and the third does not have a Hamiltonian path.
To solve these types of problems we will use trial and error, together with some logic.
Practice questions
Question 1
Is it possible to draw a Hamiltonian path on the following diagram?
Yes
ANo
B
Question 2
A private school bus is to pick up students from a certain area. The following map shows the routes connecting the students' houses.
The bus driver wants to save as much time as possible on his route. If he starts his route at vertex $D$D, what is the shortest path that visits each house exactly once?
Represent the path by listing the vertices in order, separated by commas.
Question 3
A rock band is planning a tour across several cities. The following table represents the routes and distance between the cities at which they will be performing.
| Starting City | Ending City | Distance |
|---|---|---|
| $A$A | $C$C | $9$9 |
| $A$A | $F$F | $6$6 |
| $B$B | $E$E | $11$11 |
| $B$B | $F$F | $5$5 |
| $C$C | $D$D | $3$3 |
| $C$C | $F$F | $7$7 |
| $E$E | $D$D | $5$5 |
| $E$E | $F$F | $8$8 |
Which of the following graphs does the table represent?
A
B
C
DUsing either the correct graph or table given, find the shortest route for the rock band to cross starting at city $A$A and passing by each city only once.
List the vertices in order, separated by commas.