After watching this video lesson, you will be able to determine how many Hamilton circuits a particular graph has, as well as find Hamilton circuits and paths in these graphs. Then, check out our quiz questions to test your new knowledge!
Meet Larry. He is on a mission to visit every single house in a neighborhood. Why does he want to visit every single house in a neighborhood? He wants to let people know about a special program that he is part of that gives all the children in the neighborhood free breakfast and free shoes. In order for this program to be a success, Larry needs donations. So, his purpose in visiting everybody is twofold. For one, he wants to let people know about the program so they can take advantage of it, and second, he wants to see if some of them are willing to give donations to benefit this special program. Larry has drawn a diagram of the neighborhood using dots for houses and lines for the roads connecting the houses. We see that there are ten houses in this neighborhood, and we see the lines that connect the houses to each other.
To make good use of his time, Larry wants to find a route where he visits each house just once and ends up where he began. In graph theory, such a path is called a Hamilton circuit, a circuit that goes to each vertex just once and ends up at the start point. A vertex is where two straight lines meet to form an angle.
Looking at his diagram, Larry sees that if he visits all the houses on the outer edge first and then visits each house on the inside of the neighborhood, then he can visit each house just once and end up where he began. For example, if he starts with house A, he can then go to houses B, C, D and E. Then he can go to houses F, J, I, H and then G. Finally, going back to house A gets him back to where he started. He has made a Hamilton circuit.
If Larry didn’t care where he ended up, he can choose to walk a Hamilton path, a path that goes to each vertex just once but ends up in a different spot. Looking at this graph, Larry sees that he can walk this kind of path in a similar way to the Hamilton circuit. He can start at house A, then go to houses B, C, D and E. Then he can cut into the inner houses and visit houses F, G, H, I and finally J. He walked a Hamilton path and visited each house just once, ending up somewhere other than where he started.
More Circuits and Paths
You might have noticed that the way Larry took for both the Hamilton circuit and path is just one way he could have gone. There are other routes he could have taken. For example, another Hamilton circuit would be visiting the houses starting with E, then going to J, D, I, C, H, B, G, A, F and back to E. Another Hamilton path could be C, H, I, D, J, E, F, G, B and then A. There are even more routes that Larry could have taken. See if you can spot them.
Now, let’s review what we’ve learned. We’ve learned that a Hamilton circuit is a circuit that goes to each vertex just once and ends up at the start point, and a Hamilton path is a path that goes to each vertex just once but ends up in a different spot. It is possible for graphs to have more than one such circuit or path. As you can see, these problems apply in the real world to people that need to visit several locations and want to find the best route to take.
As you complete the video lesson, test your ability to:
- Provide definitions for Hamilton circuit and Hamilton path
- Work through a real-world example of Hamilton circuit and Hamilton path