I realize that mathematics and graph theory enter my everyday life. In particular, it seems that I love to try to find Euler circuits when travelling. I’ll try to make this a simple explanation.
(Well, actually I won’t explain it. I’ll leave this post as EXTRA CREDIT for my Applied Math students… since I’m not teaching graph theory this semester.
Suppose that you have a set of roads and corresponding destinations that make up a route you might take. The idea of an Euler circuit is to use each of the roads exactly once, with no repeats.
Although I don’t completely subscribe to that theory, my goal is to avoid reusing road segments on any path that I do take in a single day. I like variety of routes! For example, consider the following graph which shows roads involving my most common cycling destinations in Kenosha (notice: neither is to scale nor is topographically accurate):
Today, I just used the square “Home-Apt. Office-Straz-Trail-Home.” But tomorrow, I plan on going to Pick ‘n’ Save, and also must stop at the apartment office to pay my rent. And of course I’m going to Straz to work.
This does not include all of the possible roads, but just the ones that I am most likely to cycle down.
The bonus questions for the Applied Math students:
- Consider the whole graph as given here. Is it possible to find an Euler circuit? Explain why or why not.
- Is it possible if we only consider the nodes “Trail, Straz, Home, Apt. Office, and Pick’n’Save?” Once again, explain. If it is not, suggest how I might construct a sub-graph that contains an Euler circuit AND these nodes.
HINT: You might get the theory by reading Chapter 1 of “For All Practical Purposes.”
Nebraska Road Trip: 18 days
פסח: מ”א ימים (Passover: 41 days)
ארץ ישראל: צ”ה ימים (Israel: 95 days)