8.05 Hamiltonian networks and paths

When we looked at Euler paths (trails) and Euler circuits, we were focused on using each of the edges just once. Another way to look at networks is to consider visiting each of the vertices just once. When we do this we leave the world of Euler and enter the world of Hamilton. Sir William Hamilton actually. He was an Irish mathematician, physicist and astronomer.

Named after Sir Hamilton, we now look at Hamiltonian paths and Hamiltonian cycles.

A Hamiltonian cycle is a path that visits each of the vertices once and only once and ends on the same vertex as it began. For example, in this network the Hamiltonian cycle is marked in red. We do not need to use all the edges, just visit each vertex once.

Other Hamiltonian cycles here include ABDCA, DBACD and many others.

A Hamiltonian path is a path that visits each of the vertices once and only once but can begin and end on different vertices. For example, the Hamiltonian path in the network here could be ABCDE. In a Hamiltonian path we do not need to use all the edges, we just have to visit all the vertices once.

If a graph has a Hamiltonian cycle then it automatically has a Hamiltonian path. (By just dropping off the last vertex in the circuit we create a path, for example, ABDC and DBAC from above.)

A semi-Hamilton graph is a graph that contains a Hamilton path but not a Hamilton cycle.

Unlike with the Euler paths and Euler circuits, there is no single rule or theorem to help us identify if a Hamiltonian path or Hamiltonian cycle exists. The only thing we can do is look for them.

The following network has both Hamiltonian path and Hamiltonian cycle - can you find them both?

Remember, the Hamiltonian path is a path where we visit each of the vertices only once. There are many Hamiltonian paths here:

ABCD, ABDC, ADCB, ADBC, ACBD, ACDB, BACD,\\ BADC, BCDA, BCAD, BDAC, BDCA, CABD, CADB, CBDA,\\ CBAD, CDBA, CDAB, DABC, DACB, DBAC, DBCA, DCAB \text{ and } DCBA.

In fact, because each vertex here is connected to every other, then this list is actually all combinations of the four vertices A, B, C, an D.

The Hamiltonian cycle is a walk where we visit each of the vertices once but return to the beginning node. All the above paths can, in this case, be turned into a cycle by returning to the original node.

Here are three networks: the first has a Hamiltonian path highlighted, the second is Hamiltonian and has a Hamiltonian cycle highlighted, and the third does not have a Hamiltonian path.

There is no good way to figure out whether a Hamiltonian path exists or not - we just have to go in and look for them. This is exemplified in the famous "travelling salesman problem", which asks if a salesperson can visit every city in a random network without having to visit the same one twice. This classic problem in network theory and an efficient way to find a solution when there are a large amount of cities in unknown.

A small part of a city, containing seven blocks, needs to be serviced by a garbage collector. The garbage truck needs to travel along each side of each block.

If we replace every intersection with a vertex, we can use directed edges to represent the roads. The garbage truck then needs to travel along every edge to complete the route:

Or, we could replace each side of every road with a vertex, and connect the vertices with directed edges if we can travel from one to the other without making a right turn. The garbage truck then needs to travel to each vertex to complete the route:

Can we visit every vertex (collect all the garbage) without repeating a vertex (driving down the same street the same way twice)? This would show the driver the most efficient route to take to collect the rubbish.

It may take some time to find the correct order but YES, we can. This graph has a Hamiltonian cycle, so it is a Hamiltonian network:

Examples

Example 1

Is it possible to draw a semi-Hamiltonian path on the following diagram?

Worked Solution

Create a strategy

Find a path that passes over each vertex of the graph exactly once and starts and finishes at different vertices.

Apply the idea

Let's try and start our path at A, and go to B, then to C, then to D, and then to E.

So the path ABCDE is a semi-Hamiltonian path since it visits every vertex once and starts and ends at different vertices.

So, yes it is possible to draw a semi-Hamiltonian path on the given graph.

Example 2

Which of the following graphs are semi-Hamiltonian?

A

B

C

D

Worked Solution

Create a strategy

Check each graph to see if a semi-Hamiltonian path is possible.

Apply the idea

For option A, we can start with A, \, E, \,D. But to get to B we need to come back through D. So we cannot create a semi-Hamiltonian path.

For option B, a semi-Hamiltonian path is C, \,A, \,D, \,B , \,E. We cannot create a Hamiltonian circuit without repeating some vertices. So the graph is semi-Hamiltonian but not Hamiltonian.

For option C, a Hamiltonian circuit is B, \,A, \,C, \,D, \,E, \,B. So it is a Hamiltonian network.

For option D, a semi-Hamiltonian path is A, \,B, \,C, \,D , \,E. We cannot create a Hamiltonian circuit without repeating some vertices. So the graph is semi-Hamiltonian but not Hamiltonian.

So the correct answers are option B and D.

Watch question walkthrough