Hamiltonian Paths and Cycles

We learned about paths in an earlier chapter, but some networks have some very special paths. If a path through a network uses every vertex, we call it a Hamiltonian path, and call the network traceable (sometimes semi-Hamiltonian). This is named after the Irish mathematician William Rowan Hamilton, an early developer of network theory. If the network has a cycle that uses every vertex, we call the cycle a Hamiltonian cycle and call the network simply Hamiltonian.

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 salesman (or woman!) can visit every city in a random network without having to visit the same one twice. Finding time efficient solution methods to this classic question in network theory remains unsolved to this day.

We can still talk about Hamiltonian networks even when the edges are directed. Let’s return to the network representing a garbage collection route:

Can we visit every vertex (collect all the garbage) without repeating a vertex (driving down the same street the same way twice)? Yes, we can! This graph has a Hamiltonian cycle, so it is a Hamiltonian network:

One example of a Hamiltonian cycle. Are there others?