Seven Bridges of K nigsberg
The Seven Bridges of Königsberg is a problem inspired by an actual place and situation. The city of Königsberg, Prussia (now Kaliningrad, Russia) is set on the river Pregel, and included two large islands which were connected to each other and the mainland by seven bridges, as in the schematic figure below:
Graph theory
In graph theory, the problem was first solved by Leonhard Euler. In the history of mathematics, it is one of the first problems in graph theory to be formally discussed, and also, as graph theory can be seen as a part of topology, one of the first problems in topology. (The field of combinatorics also has a claim on graph theory, but combinatorial problems had been considered much earlier.)
The question was whether it was possible to walk a route that crossed each bridge exactly once, and returned to the starting point. In 1736, Euler proved that it was not possible. In proving the result, he formulated the problem in terms of abstract graphs, with the case of Königsberg corresponding to the following graph:
Euler showed that a path of the desired form is possible if and only if there are no nodes (dots in the picture of the graph) that have an odd number of edges touching them. Such a walk is called an Eulerian circuit or an Euler tour. Since the graph corresponding to Königsberg has four such nodes, the path is impossible.
If the starting point does not need to coincide with the end point there can be either zero or two nodes that have an odd number of edges touching them. Such a walk is called an Eulerian trail or Euler walk.
Map of Königsberg
Bridges of Königsberg
actual layout
This is a map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the waterways with blue and the bridges with green.
The difference between the actual layout and the graph schematic is a good example of the idea that topology is not concerned with the rigid shape of objects.
There is a social aspect to the problem of the Königsberg bridges. Circa 1750, the prosperous and educated townspeople would walk about on Sundays and try to solve the problem. Perhaps it is an urban legend, but interesting.
de:Königsberger Brückenproblem es:Problema de los puentes de Königsberg fr:Sept ponts de Königsberg nl:Zeven bruggen van Koningsbergen ja:一筆書き sv:Königsbergs broproblem [[zh:柯尼斯堡七桥问题]]
Categories: Graph theory | Topology