Real MATHEMATICS – Graphs #4

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.

hermitage-map-st-petersburg
Map of Hermitage.

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?

indir
Mei-Ko Kwan

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:

20190324_210039
A, B, C, D and E are the houses as the lines are the streets. The numbers above the lines show how much time it takes to walk from one house to another.
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:

20190325_123338.jpg
The numbers above each line represents the distances (e.g. in km) between the points.

First of all we must determine the degree of each vertex:

20190325_123326.jpg

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:

20190325_123311.jpg
The shortest path takes 11 km.

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:

  1. Find the vertices that have odd degrees.
  2. Split these vertices into pairs.
  3. Find the distance for each pair and compare them. The shortest pair(s) shows where to add new line(s).
  4. 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:

20190324_210039

Unfortunately A and D have odd degrees which is why the postman can’t finish his walk:

20190324_210102

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:

20190324_210157

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?

20190324_210225

M. Serkan Kalaycıoğlu

Real Mathematics: Graphs #1

Puzzles and mathematics have a deeper relationship than one might assume. When you take a look at history of mathematics, it is not that rare to see a puzzle causing mathematics to change.

Without a doubt, Seven Bridges of Königsberg (1736) is the most famous one of those stories.

Leonhard Euler, one of the most influential mathematicians of all times, was given this puzzle/problem in the 18th century. Euler had a great reputation for solving “unsolvable” questions, and major of Königsberg asked for his help. Euler was not pleased to receive this problem at first as he said “… I don’t believe this question has anything to do with mathematics.” Although after some time he believed that the problem was interesting enough to deal with.

Görsel 1
Leonhard Euler (1707-1783)

Euler’s solution to Seven Bridges of Königsberg problem culminated a couple brand new mathematics branches to emerge: Topology and graph theory. What fascinates me about this story is that these branches came out almost 150 years after Euler’s solution.

Seven Bridges of Königsberg

Take any book on graph theory. Open first chapter’s first title. You’ll see Euler’s solution for this simple problem:

indir (2)

The old town of Königsberg has seven bridges as shown on the map. Is it possible to take a walk through the town, visiting each part of the town and crossing each bridge once and only once?

I encountered with this problem for the first time in the junior year of my math major. I first thought that the question was dull and I could solve it with ease. After spending a night with full of disappointments and a lot of cursing, I gave up. I knew that it was impossible to take that walk and I knew that it was possible when I removed one bridge. But I didn’t know why.

Soon enough, I realized that I needed fundamentals of the graph theory to understand the answer. Euler’s solution to this simple puzzle is the basis of a whole new mathematics branch: Graph theory.

What Euler Did

First thing Euler did was to imagine that bridges and lands as two different groups. According to him, solution of Königsberg problem didn’t depend on the physical appearances of them. Euler realized that it didn’t matter how long or curvy a bridge is, or if a land is an island or not.

He just thought that bridges could be represented as edges numbered from 1 to 7, and lands could be represented as vertices named A,B,C and D. When all Königsberg problem map is put into a piece of paper with using on edges and vertices, we would end up with a graph.

Degree of a vertex is the number of edges it has.

According to Euler, in order to find a solution for Königsberg problem either of these should be found in the graph:

  1. Exactly two vertices should have odd number of degrees. That would mean one of the vertices is the start of the tour as the other is the finish.
  2. All of the vertices should have even number of degrees. That would mean one could start the tour from any vertex.

Why?

If a vertex is neither start nor finish of the tour, then in case one edge comes to that vertex another one should leave so that the vertex would be neither the start nor the finish. (Because if an edge comes to a vertex and another doesn’t leave, it means that vertex is the finish of the tour. And if an edge leaves from a vertex but another doesn’t come back to it, then it means that vertex is the start of the tour.) This would mean that the vertex should have even number of degree. Although, if vertex has odd number of edges, in order to keep odd degree we shouldn’t let another edge to leave in case there is an edge coming to that vertex. This would mean that the so called vertex is either start or finish of the tour.

Also, if there are no vertices in the graph with an odd degree, then a chosen vertex could well be both start and finish of the tour.

Eulerian Path: If a path/tour in a graph contains each edge of the graph once and only once, then that path is called Eulerian Path.

I am aware that the paragraph above is a bit confusing. Let me give you a few examples to clear your mind about degree of a vertex.

Examples:

  1. One Bridge: Two lands and one bridge graph.
    köpr
  2. Two Bridges: Two lands and two bridges graph.
    Görsel 8
  3. Three Lands: Add land C into the previous graph.
    Görsel 7

In this case there are two vertices with odd number of degrees. Hence, there is a solution for this graph but vertices B and C should be the start and finish of the path.

Solution to Königsberg

Euler saw the Seven Bridges of Königsberg as this graph.

Numbers of degrees for the vertices are 5, 3, 3 and 3 in order. This means that the Königsberg graph has more than two odd numbers of vertices which is a violation for the rule. This is concludes that there is no such tour/path for the seven bridges of Königsberg.

Topology is the mathematical study of the properties that are preserved through twisting and stretching of objects. (Tearing, however, is not included.) Topologically a circle and an ellipse are equivalent to each other.

IMG_5281
A simit is topologically equivalent to a coffee cup.

Check it out

Which objects are topologically equivalent to each other ?

IMG_5282