Euler!

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):

graph_bike_routes

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:

  1. Consider the whole graph as given here. Is it possible to find an Euler circuit? Explain why or why not.
  2. 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)

blog signature

Advertisements

Let's have a conversation!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s