A student in my Graduate studies Discrete Mathematics class made great comment last week that it is very satisfying when there is opportunity to apply what we learn in our everyday lives. To that end, I will share a personal obsessive compulsive issue I have that I am now free of thanks to this weeks coursework.
I really enjoy doing long trail runs on Sundays. There is a state park very near me where you can run about a half marathon's distance seldom seeing the same tree twice. The issue is, as hard as I try, sooner or later I end up looping up on a path I have already done. My obsessive goal is to run the entire park, running each trail only once. As of yet, this is a goal unfulfilled!
I studied Euler, and Hamilton graphs and circuits among other things this week. Where as Leohnard Euler was concerned with traversing the edges of a connected multigraph, William Hamilton was concerned with traversing the vertices.
The trail running issue is more of an edges objective. Fortunately if you are concerned with edge paths, there are some handy formulas to help you classify paths (Hamilton, not so much). We learned that a Euler circuit is classified as path which travels all edges and returns to the point of origin. Also there is a Euler path, this is a path which travels all edges but in so doing does not return to the point of origin. I've also seen authors call these paths "Eulerian Walks" and "nearly-Eulerian"[2] Walks, as well as "open" and "closed" Euler paths.
Euler proved a convenient theorem which states that all Euler circuits must contain vertices of even degrees. The degree of a vertex is simply the number of edges connected to the vertex. Euler's theorem makes sense upon reflection because in a circuit a line never dead-ends, it goes through points and keeps on going. So, every time we traverse through a point we use two edges. One going in, and one going out. These increments of two yield all the even degreed vertices.
Alas, I look at my
Calvert Cliffs trail map (Links to an external site.)[3] and I see right away places where paths intersect in three or five ways. Oh no! Is there any hope for my OCD? I had to take pause in hopes that perhaps all is not lost. Then, I looked instead for a Euler
path.
Euler says that we can have a Euler path, but only if our graph contains exactly two vertices of odd degrees. This also makes sense if you buy the Euler circuit explanation above. Simply imagine that you have two separate Euler Circuits and then you bridge them with one single line. Now observe, where you have added that edge. By joining the vertices in the previously separate graphs you have a incremented the degree of each by one. They were even, so now, they are both odd. So, in the resulting Euler path every line is traced in the first subgraph. We then trace across the bridge we added to the next subpath. Finally every line is traced in the second Euler circuit subgraph. We cannot cross the bridge again to get back to the origin, however, as a small concession at-least every edge has been traversed. Viola! Euler path.
Now I turn back to my running graph and look, there are actually more than two odd degreed edges, and unfortunately a pendant (the point by the water sticks out all in it's own with degree 1). I can however tweak some of the points into being even numbers. I do this in two ways. First, I can generalize clusters of three way intersection as single n-degree points. The yellow circles are examples of places where I unified the intersections. Second, I added a new path which I make by running out to street bordering the front of the park. Lastly to deal with the pendant I figure, I can either give up and remove the line, or just have my run end at the end of the pendant.
Armed with my new graph that has only two odd numbered vertices I toast to mister Euler and start tracing. Twenty minutes later I am consulting the text book. After 5 failed attempts I have not found a Euler path! Perhaps I misread the theorem?
Trying again I do something different I start at one of the odd degreed vertices. Success! After this I notice something, any path I try which does not start and end at an odd degreed vertex is doomed to fail. I go to the library and after further research I find this:
"If the degree of both u and v is odd, then G, has a walk which begins at point u, contains every line of Gi exactly once and ends at point v; let us call Gu in this case nearly-Eulerian with respect to u and v."[2] So yes, this confirms it. You have to start and stop on a point which connects an odd number of trails for it to work.
It turns out that this is even true for pendants. Like the one I initially removed in red on the graph above. After all if you connect the pendant to an odd degree vertex, you've just made the connecting point even, and the far end of the pendant is still degree one. One is odd right? So, now I realize that I will be making the walk to the beach on the path I previously removed after all. Why not?
I'm happy to have a cure for my issue. It is a bummer though that after such a long run, I am at the furthest point from the parking lot. Oh well. I won't spoil it for you. Trace the graph and see if you can find the Euler path. I will put my answer in white font inside the brackets below, yours could be different:
{k,n,m,i,j,h,e,p,o,q,r,b,a,g,f,c,d,s,t,water}
References:
[1] Rosen, Kenneth. Discrete Mathematics and Its Applications. Seventh Edition. New York: McGraw-Hill, 2012.
[2] S. Goodman, Hedentniem S., Eulerian Walks in Graphs, SIAM Journal of Computing, Vol.2, No 1, March 1973
