One may look at the image below and ask what does this represent, why is this useful, or how is this math?
Path: is connected edges with no repeated vertices. Paths can be closed and open
Euler Path: is a path that uses every edge of a graph exactly once.
Example BBADCDEBC
Circuit: is a closed path
Euler Circuit: is a circuit that uses every edge of a graph exactly once.
Example CDEBBADC
How can one just look at a graph and tell that it contains an Euler circuit or path without tracing over the edges and trying to find it? Euler found some patterns and came up with Theorems on these topics.
If a graph has any vertices of odd degree, then it cannot have an Euler Circuit.
If a graph is connected and every vertex has even degree, then it has at least one Euler Circuit.
Theorem 2If a graph is connected and every vertex has even degree, then it has at least one Euler Circuit.
If a graph is connected and has exactly 2 vertices of odd degree, then it has at least one Euler Path.
I found this table that sums up the Theorems nicely in a more visual format:
# of ODD Vertices

Implication (for a connected graph)

0

There is at least one Euler Circuit.

1

THIS IS IMPOSSIBLE!

2

There is no Euler Circuit but at least 1 Euler Path.

more than 2

There are no Euler Circuits
or Euler Paths. 
Although all of this may seem useless and not "mathy," this is development in math has grown over the years. Graph Theory has evolved and more and more people are seeing the value in it. And yet this is another invention that Euler discovered in his life. To learn about everything that Euler discovered click here.
So the next time you look at an image that is simply just lines and points, there is more than just the simple lines and points behind it. It may represent an real world problem or used to show routes. It's math.
References: http://www.ctl.ua.edu/math103/euler/euler.htm#3 Important Questions
https://www.math.ku.edu/~jmartin/courses/math105F11/Lectures/chapter5part2.pdf
https://www.math.ku.edu/~jmartin/courses/math105F11/Lectures/chapter5part2.pdf
Wow, great post! I love how explained it by connecting it to airplanes which everyone can understand. I also like how you explained the terminology and Euler's findings with examples from your diagram. Very nice!
ReplyDeleteI really liked this post. The first example involving the airplanes was well thought out and explained to the reader. I believe that an audience that doesn't have very much experience with mathematics or graph theory would be able to comprehend the "big picture" from this piece. Well done. A suggestion that I might add would be to work out one of the theorems as an example in which one might be able to use the others as exercises. That way your audience is more involved in the material that is being explained and elaborated on.
ReplyDeleteNice connections and exposition. You might link directly to the page the table came from (but at least it's cited). You never say what problem that original graph is from! In the second to last paragraph you could add that and the analysis from the theorems you cite. (content)
ReplyDeleteOther C's +