After watching this video lesson, you will be able to Eulerize any graph. Learn what it takes to create a Eulerian graph from a non-Eulerian graph. Learn what Fleury’s algorithm has to do with all of this.
We begin with a graph – this graph:
Now, imagine that you are a chief engineer for the town of Harrisville. Your job is to create roads that will make it easy to navigate the town for both residents and workers, especially the mailman. You want to build the roads in such a way so that the mailman can have an optimized route where he passes each road only once.
In order to do this, you make use of your knowledge of graph theory. Why? Because this graph that you are looking at is actually a drawing of the current roads of the town. The intersections are marked with the dots with numbers in them. You know that when a graph has an Euler circuit or Euler path, then that means the graph is mailman-friendly because there is a route that he can take to pass each road just once. The only difference being that the path takes the mailman to a different end point, and the circuit has the mailman ending where he began.
You also make use of Fleury’s algorithm that tells you that when a graph has zero odd vertices, then it has an Euler circuit, and when the graph has two odd vertices, then it has an Euler path. Knowing this helps you to analyze your current graph to see if the roads are already mailman-friendly. You count the number of odd vertices; remember that an odd vertex is a vertex where the number of edges connecting it to other vertices is odd. In your graph, you count four odd vertices. Hmmm. This means that there currently is no Euler path or Euler circuit in this graph. What are you to do?
Since you are the chief engineer for this town, you go ahead and propose some new roads. But where should you place these roads? Which intersections should the new roads connect?
Eulerizing a Graph
The purpose of the proposed new roads is to make the town mailman-friendly. In graph theory terms, we want to change the graph so it contains an Euler circuit. This is also referred to as Eulerizing a graph. The most mailman-friendly graph is the one with an Euler circuit since it takes the mailman back to the starting point. This means that the mailman can leave his car at one intersection, walk the route hitting all the streets just once, and end up where he began. There is no backtracking or walking of streets twice. This saves him time.
We used Fleury’s algorithm to help us determine whether our graph has an Euler circuit to begin with. We can also use Fleury’s algorithm to help us decide where to place our new roads, our new edges. According to Fleury’s algorithm, in order for a graph to have an Euler circuit, all of the vertices must be even, meaning we have zero odd vertices. To accomplish this, we can draw new lines connecting vertices that are odd together to make them even.
For example, we can connect vertices 3 and 2 together. This changes these two vertices from odd to even. Now we are left with two odd vertices, vertices 4 and 5. To change these to even vertices, we can add another road connecting these two. This changes our graph to one where there are zero odd vertices, meaning that we have a graph with an Euler circuit in it. We have Eulerized our graph by adding two new roads.
Semi-Eulerizing a Graph
But wait, what if you don’t have enough money to build so many roads? What then? You can choose to semi-Eulerize the graph. This means that you change the graph so that it has an Euler path in it. This isn’t as mailman-friendly, but at least there is a route where the mailman only crosses each road just once. He will end up at a different location from where he began though. But if you are limited, this will give you an option to still optimize your graph, but with less edges.
Why do you need fewer edges? Well, we go back to Fleury’s algorithm. It tells us that for a graph to have an Euler path in it, it must have two odd vertices. This means that we can leave two of our odd vertices alone. This means that we don’t have to draw as many new edges.
Going back to our original graph, we see that we have four odd vertices. To semi-Eulerize this graph, we only need to change two of these odd vertices to even. This means that we just need one new road. We can connect vertices 2 and 3, and we will have semi-Eulerized our graph because we are left with two odd vertices.
Now, you have two options available to you depending on what you want to accomplish and what you can accomplish. As the chief engineer of the town, it is your decision based on the budget. You might decide to hold a fundraiser to raise enough funds so that you can build the two new roads needed to fully Eulerize the graph and to fully optimize the town for the mailman, or you might decide to leave the funds as is and to semi-Eulerize the graph to partially optimize the town for the mailman.
Let’s review what we’ve learned now.
Eulerizing a graph means to change the graph so that it contains an Euler circuit. To do this, we make use of Fleury’s algorithm, which tells us that a graph with an Euler circuit in it has zero odd vertices. If our graph has more than zero odd vertices, we add edges until all of our vertices are even.
Semi-Eulerizing a graph means to change the graph so that it contains an Euler path. We again make use of Fleury’s algorithm that says a graph with an Euler path in it will have two odd vertices. We add edges until only two of our vertices are odd. In most cases, fewer edges are needed to semi-Eulerize a graph versus fully Eulerizing a graph.
Following this video lesson, you should be able to:
- Define Euler path and Euler circuit
- Explain how to use Fleury’s algorithm to Eulerize and semi-Eulerize a graph