Königsberg Bridge Problem
The problem is simply to find a path around a collection of bridges that crosses each bridge exactly once. The map below shows the layout of bridges in the town of Königsberg, with seven bridges and two islands.
The seven bridges problem is well-known in both Maths and Computer Science, and so is particularly appropriate for the garden since the bridges problem links the two departments that sponsored the garden! It is usually associated with the 18th century mathematician Leonhard Euler -- a path that solves the problem is called an Eulerian path. Eulerian paths have interesting properties, both mathematically and computationally. The layout of bridges is from the town of Königsberg in northern Germany (now part of Russia). The islands are in the middle of a river. In our garden the river is represented by the garden. Since it is a river, you aren't allowed to go around the far ends of the diamond!
Euler is supposed to have proved that there is no solution when he was working in St. Petersberg. There could only be a solution if every island had an even number of bridges touching it, since one must leave an island the same number of times one arrives at it. Alternatively, exactly two islands can have an odd number of bridges, and these must be the start and finish point of the tour.
- An incredibly detailed history of the actual bridges in Königsberg has been produced by Gilead
- http://history.math.csusb.edu/HistTopics/Mathematical_games.html (includes a map of the original town of Königsberg).
- Queen's College, Cambridge have a Mathematical Bridge; the mathematics in this case apparently relates to the design of the bridge, and finding an Eulerian path is not so difficult in this case!
Back to the Bridges of Friendship Garden Homepage