Graph Databases: 2. The Seven Bridges of Konigsberg
In 1736 Leonhard Euler established the foundations of Graph Theory, which is the basis of Graph Databases, when he was challenged by the citizens of Konigsberg to solve a problem with the layout of their city.
The city of Konigsberg in Prussia (now Kaliningrad, Russia) is set on both sides of the Pregel River, and includes two large islands – Kniepof and Lomse, which were connected to each other and to the mainland portions of the city by seven bridges.
|
The problem that the fair citizens of Konigsberg were trying to solve was to devise a walk through the city that would cross each bridge once and only once – solutions that involve accessing a bridge without crossing to its other end or reaching a body of land by other means than crossing a bridge were explicitly excluded. Nobody had been able to devise a route and it was assumed that there was no solution to the problem.
Euler pointed out that the route inside each land mass was irrelevant to the solution of the problem and the land-mass could be represented by a single node or vertex. Each bridge could be represented by a connection or edge, which allowed him to restate the problem in an abstract manner.
 |
| Euler’s Solution - Wikipedia |
Once the problem was reduced to its simple terms Euler was able to analyze the “graphs” that he had drawn and determine that there was no solution. Euler observed that, except at the endpoints of the walk – the beginning and end, whenever you enter a land-mass (vertex) by a bridge (edge) you must leave by a different bridge (edge). Therefore, except for the start and end points of the walk, to satisfy the problem the vertices would need to have an even number of edges. There are therefore only 2 possible solutions:
- The graph has only 2 vertices of odd degree. In this solution the two vertices are the start and end points of the “walk”.
- The graph has zero vertices of odd degree. In this solution the “walk” would need to start and finish at the same vertex.
When we look at the graph that represents the “7 Bridges of Konigsberg” problem we notice that all 4 vertices are of odd degree (one of degree – 5, 3 of degree 3). Thus there is no viable solution.
This was an interesting aside. In my next blog post I will go a little deeper into “Why Graph Databases”.