I visited the world famous Hermitage museum in Saint Petersburg (Russia) back in 2014. Hermitage is so huge that it has 1057 rooms and one would have to walk around 22 km to see all the rooms. And numbers of artistic & historical items are not that shallow either: It is believe that it would take a little over 11 years if one would spare 1 minute for each piece of art.
Now you can relate why I had trouble when I wanted to visit Hermitage for a few hours. I didn’t have enough time and I wanted to see important art works such as the Dessert: Harmony in Red by Henri Matisse. Eventually I realized that this is a problem I had faced before.
Actually, each and every one of you must have faced such problems in your daily lives. Most common one: “Which route you should take between home and work during rush hour traffic?”
Postman’s Path
Facing such problem in Saint Petersburg is a pleasing coincidence as this magnificent city once was home to one of the giants of mathematics: Leonhard Euler. If you take a look at the first article of graphs you can see that Euler is the person who initiated the discovery of Graph Theory with his solution to the famous Seven Bridges of Königsberg problem.
In 1960 (almost 230 years after the solution of Königsberg) a Chinese mathematician named Mei-Ko Kwan took a similar problem into his hands:
A postman has to deliver letters to a given neighborhood. He needs to walk through all the streets in the neighborhood and back to the post-office. How can he design his route so that he walks the shortest distance?
This problem is given the name Chinese Postman Problem as an appreciation to Kwan. There are a few things you should know about the postman problem:
- Postman must walk each street once.
- Start and finish point must be at the post-office.
- Postman must fulfill these two conditions in the shortest possible time.
Power of Graphs
Mei-Ko Kwan turned to Euler’s Königsberg solution in order to solve the postman problem. According to Kwan postman problem could have been shown as a graph: Lines represent the streets and letters represent the houses.
Example Graph:
Reminder (You can read the first three articles of Graphs and learn the detail of the following.)
What is an Euler circuit?
Euler circuit is a walk through a graph which uses every edge (line) exactly once. In an Euler circuit walk must start and finish at the same vertex (point).
How do we spot an Euler circuit?
A graph has an Euler circuit if and only if the degree of every vertex is even. In other words, for each vertex (point) count the number of edges (lines) it has. If that number is even for each vertex, then it is safe to say that our graph has an Euler circuit.
Solution
As you can see above, if the degree of every vertex in a graph is even, then we can conclude that the graph has an Euler circuit. Let’s assume that the following is our graph:
First of all we must determine the degree of each vertex:
As seen above all the vertices have even degrees. This is how we can conclude that the graph has an Euler circuit even without trying to find the path itself. Hence the postman can use the existent roads and finish his route in the shortest time:
When a graph has vertices with odd degrees, then we must add new line(s) to the graph in order to create an Euler circuit. These are the steps you can follow:
- Find the vertices that have odd degrees.
- Split these vertices into pairs.
- Find the distance for each pair and compare them. The shortest pair(s) shows where to add new line(s).
- Add the line(s) to the graph.
Let’s use an example and test Kwan’s algorithm for the solution. Assume that A is the starting point. First we must check the degrees of the vertices:
Unfortunately A and D have odd degrees which is why the postman can’t finish his walk:
Here we have only one pair that is A-D. There are three routes between A-D. If we find the shortest one and add that to our graph, we will have an Euler circuit:
The shortest one is the line between A-D as seen above. If we add that line, we will have the shortest route for the postman:
One wonders…
If the post office is at A, what is the route for the postman to take so that he will finish his day in the shortest way?
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 