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.

Map of Königsberg

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.

Related sites

Oh, and the Eagles have a song called Seven Bridges Road, which is completely unrelated!

Back to the Bridges of Friendship Garden Homepage

Modified: 6-Apr-1999