Eulerian Cycles: Why Are They So Unique, and Are They Significant to Us in the 21st Century?
Eulerian cycles and paths are by far one of the most influential concepts in Graph Theory. However, what really are Eulerian cycles and paths, and how is the 18th-century path meaningful to the futuristic 21st century?
Eulerian Cycles and paths are by far one of the most influential concepts of graph theory in the world of mathematics and innovative technology. These circuits and paths were first discovered by Euler in 1736, therefore giving the name “Eulerian Cycles” and “Eulerian Paths.” When it comes to graph theory, understanding graphs and creating them are slightly more complex than it looks. There are many variables to consider, making them seem more like a puzzle than an actual problem. However, when we talk about Eulerian Cycles and Paths, it’s relatively easy to understand what’s going on.
An Eulerian Path is a path in a graph where each edge is visited exactly once. An Euler path can have any starting point with any ending point; however, the most common Euler paths lead back to the starting vertex. We can easily detect an Euler path in a graph if the graph itself meets two conditions: all vertices with non-zero degree edges are connected, and if zero or two vertices have odd degrees and all other vertices have even degrees. Do note that only one vertex with an odd degree is not possible in an undirected graph (Eulerian Paths are commonly found in undirected graphs) as the sum of all degrees is always even in an undirected graph. But you may ask, “how do we know if a vertex has an odd degree or an even degree?”. For those who don’t know about degrees in graphs, finding degrees of vertices is different than finding the degrees of typical angles. If the total number of edges of a vertex is odd, the vertex is said to have an odd degree. Though, if the total number of edges of a vertex is an even number, the vertex is said to have an even degree. This odd-even vertex condition allows us to understand if a given graph is Eulerian or not.
To know if a graph is Eulerian, or in other words, to know if a graph has an Eulerian cycle, we must understand that the vertices of the graph must be positioned where each edge is visited once and that the final edge leads back to the starting vertex. The Eulerian Cycle is essentially just an extended definition of the Eulerian Path. If it seems confusing, then picture it like this, “is it possible to draw the graph without lifting your pencil or pen (in one stroke)?”. Eulerian Cycles aren’t typically as common, and that is because of one of its conditions about its vertices. Remember even degrees and odd degrees of a vertex? Yes, for a graph to be Eulerian, all the vertices must have an even degree since there is no “specific” vertex representing the middle of the graph. Moreover, having an even number of edges for each vertex allows us to traverse the graph and return back to the starting vertex, no matter what vertex we choose as the starting point, which is our primary goal by definition.
If you didn’t get it, don’t worry; let’s look at a little visual and how we can traverse and find an Eulerian path and an Eulerian Cycle with a modified Depth-First traversal algorithm. We will be traversing the same graph as the one in the diagram above using Depth-First traversal as we want to traverse paths by depth, not laterally, because it would be inefficient.
In an Eulerian Path, each time we visit a vertex, we go through two unvisited edges with an endpoint. By definition, all the middle vertices in the Eulerian Path must have an even degree. However, instead of assuming that all the middle vertices have an even number of edges, we assumed that the absolute middle vertex is the vertex with the most edges. Moreover, just in case, if two vertices have the same amount of vertices, which are the greatest out of the graph, we can choose either one because it wouldn’t affect the traversal. The vertex with the most edges means that the vertex is the middle of most vertices, creating paths to most of the vertices in the graph. Thus, we have understood that the vertex with the biggest number of edges has to be traveled at least more than once on distinct edges to traverse the whole graph.
With the Depth-First traversal algorithm, we traverse each path by depth starting from each vertex. Remember, each vertex can only be visited once; however, the vertex with the most edges can be visited multiple times to allow the complete traversal of the graph as some vertices may not lead to other vertices on the opposite side graph. The algorithm will see if the vertex (or the current vertex’s neighbors) has not been visited and add it to the path. Otherwise, with the use of backtracking (keeping track of the previous vertex and its edges), the algorithm makes sure that if the current vertex is the same as the biggest vertex, we can add it to the path; else, we can leave the vertex and continue traversing its edges if the current vertex has already been visited. This process recurses for each vertex and its neighbors in the graph to create every possible potential Eulerian Path. Of course, there is a margin-of-error with the algorithm; while finding the Eulerian Paths, the algorithm may travel to other vertices of which, may not be a part of the current vertices’ neighbors. For this reason, in the end, we make the algorithm evaluate each path and check if the biggest vertex is the root vertex of the path as the biggest vertex has edges to multiple vertices. If so, we can conclude that the path is an Eulerian Path.
For the Eulerian Cycle, remember that any vertex can be the middle vertex. Hence, all vertices, by definition, must have an even degree. But remember that the Eulerian Cycle is just an extended definition of the Eulerian Path: the last vertex must lead to an unvisited edge that leads back to the start vertex. With the natural behavior of Depth-First traversal, the last vertex will always have unvisited edges until the vertex itself has been traversed. We know this because the DFS algorithm keeps track of the vertices that have been visited. If the last vertex is the only vertex in the graph that has not been traversed, then its edges should be assumed that they are the only non-visited ones left in the graph. However, if there are multiple edges left, that means either the graph is not Eulerian (the last vertex has an odd number of edges), or there is another unvisited vertex. Thus to summarize it up, only one edge leads to the start vertex. By traversing each edge one-by-one by depth, and getting our Eulerian Paths (since a graph with Eulerian Paths is considered Semi-Eulerian), we can compare if the last vertex of the Eulerian path has an edge that leads to the vertex with we started with. If it does, the graph is considered to be Eulerian. But you might be asking, “what if there are no Eulerian Paths in the graph?”. Good question! There are always Eulerian Paths in a graph. It’s all about re-arranging the graph in such a way, where a path can be created where each edge is crossed only once. You can think of it as solving a puzzle!
Here’s the link to my Eulerian Cycle and Path Simulation: https://github.com/GEEGABYTE1/Eulerian
But why are Eulerian Cycles and Paths so important anyways? What’s so significant about traversing each edge exactly once and ending off on where we started? There are many practical applications to Euler Circuits and Paths. In mathematics, graphs can be used to solve many complex problems, like the Konigsberg Bridge Problem. Moreover, mail carriers can use Eulerian Paths to have a route where they don’t have to retrace their previous steps. On a broader spectrum, Eulerian Cycles and Paths are useful to painters, garbage collections, airplane pilots, GPS developers (for example, Google Maps developers), marketers distributing ads; essentially anyone or anything that uses paths.
Let’s take a look at a prevalent Graph problem, called the Traveling Salesman, to look at how Eulerian Paths and Cycles are significant to salesmen and saleswomen as an example. The problem is that you have a graph of cities with certain distances (edge weights) between them. The objective is to find the shortest path that will allow you to visit each city once, leaving you at the city where you began your journey.
To solve this problem, and to give you an idea of how Eulerian Paths and Cycles play a role in real-life applications, I have developed a Greedy algorithm that outputs the most cost-efficient path to visit all the cities.
Assuming that the salesperson has to go to the cities [a,b,c,d] , with certain costs to travel a path (for example, traveling from point a to point d costs a value of 5), the algorithm evaluates the weights of every neighbor of a city (current vertex). We start by setting all the places as unvisited , because we actually have not traversed them yet. For now, we get a current vertex (our starting point) by random since we want our algorithm to compute every possible case and path, which in this case, would be 4! (since we have 4 inputs). To compare the edges and their weights, we get the edge with the most negligible weight (assuming it’s the cheapest), and we set that as the current vertex after adding it to the final path, which will be returned at the end. Just like keeping track of edges and vertices to see if a graph has an Eulerian Path or Cycle, the algorithm keeps track of all the visited vertices for every time a current vertex updates (goes to the next city) by constantly updating the dictionary that keeps track of vertices that are unvisited and visited. We do this because we don’t want the salesperson to go back to a path they have already traveled, just like how we didn’t want our traversal algorithm to traverse an edge that had already been traversed when finding an Eulerian Path.
Check out my complete solution to the Traveling Salesperson problem: https://github.com/GEEGABYTE1/TravelingSalesMan
Suppose I were to summarize the two previous paragraphs up about how Eulerian Cycles and Paths are significant. In that case, they are essential because they are the basis of optimal pathfinding or pathfinding in general. Over the years, pathfinding has been growing tremendously with new algorithms being introduced, but what’s so important about them anyways? Believe it or not, most of the algorithms we know of are pathfinding algorithms. One of the most popular algorithms that use pathfinding concepts and Eulerian Paths are Google Maps and their efficient route finding algorithms, Uber’s driver and traveler finding algorithm (when we order an Uber and see where the driver is located, that’s their pathfinding algorithm at work!), Tesla’s feature where their car can self-drive to the owner, routing packets over the internet, and much more! Do you see anything common within these algorithms I just listed? These algorithms reduce the extra work of traveling unnecessary paths and distances to get to the desired location. With Eulerian Paths and Cycles, these pathfinding algorithms have introduced traveling efficiency on a whole new level (remember, pathfinding algorithms and Eulerian Paths share the same base behavior). They will continue to do so at even a better rate as technology and algorithm development continue to grow. Take a look back at the Traveling Salesperson problem again. Instead of making the salesperson travel random paths at a random cost to each house until they have done their task, the Eulerian Paths have allowed the salesperson to travel more efficiently by reducing the energy needed to travel and the potential overall cost of the salesperson.
Eulerian Cycles and Paths are helpful in a variety of fields. Mathematics and Pathfinding happen to be one of the many prominent and relevant examples we have today. These cycles and paths are one of the many small mathematical models that have brought breakthroughs to our everyday lives. So imagine the many more breakthroughs other math expressions, models, and paradoxes have created in our lives that we don’t even pay attention to! Don’t worry though; as a passionate person about mathematics and computer science, I will continue to write about how various math concepts from famous mathematicians and today’s ever-growing innovative technology correlate and work together to help us live our lives more “efficiently”!
