Sunday, November 1, 2015

Communicating Euler's Circuits and Paths

One may look at the image below and ask what does this represent, why is this useful, or how is this math?
Image result for bridges of konigsberg
This is what mathematicians would call a graph in graph theory. It contains vertices (the blue points) and edges (line connecting vertices). This type of graph can be defined as a visual representation of the relations between quantities ( This particular graph above is the graph of the Seven Bridges of Konigsberg, a mathematics problem by Leonardo Euler. Here is a website that describes this particular graph.  A graph can represent a real world problem. For example, a graph can represent airplane traffic between cities. Airlines use graphs to come up with the most efficient travel path to get from point A to point B. To get to B from A, it may not be a straight and simple path. There maybe stops on the way, for fuel or picking up more passengers. A path of travel for an airplane may not be completing straight either, because they want the safest path. Meaning that in case of an emergency they want to fly over other airports for a safer landing. Not only is the most efficient path effective, airlines have to communicate with each other and make sure the traffic high above the clouds isn't crowded at one particular time. Euler, a great mathematician, was the first to look at graph theory. He created the Euler circuit and path. Let's first start with some terminology.

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. 
Circuit: is a closed path
Euler Circuit: is a circuit that uses every edge of a graph exactly once.

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 2
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)
There is at least one Euler Circuit.
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: Important Questions