Seven Bridges of Königsberg
From Wikipedia, the free encyclopedia
The Seven Bridges of Königsberg is a famous solved mathematics problem inspired by an actual place and situation. The city of Königsberg, Prussia (now Kaliningrad, Russia) is set on the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges. The problem is to decide whether it is possible to walk a route that crosses each bridge exactly once.
Contents |
[edit] Euler's solution
In 1736, Leonhard Euler proved that it was not possible. In proving the result, Euler formulated the problem in terms of graph theory, by abstracting the case of Königsberg — first, by eliminating all features except the landmasses and the bridges connecting them; second, by replacing each landmass with a dot, called a vertex or node, and each bridge with a line, called an edge or link. The resulting mathematical structure is called a graph.
→ 
→ 
The shape of a graph may be distorted in any way without changing the graph itself, so long as the links between nodes are unchanged. It does not matter whether the links are straight or curved, or whether one node is to the left or right of another.
Euler realized that the problem could be solved in terms of the degrees of the nodes. The degree of a node is the number of edges touching it; in the Königsberg bridge graph, three nodes have degree 3 and one has degree 5. Euler proved that a circuit of the desired form is possible if and only if the graph is connected, and there are exactly two or zero nodes of odd degree. Such a walk is called an Eulerian path or Euler walk. Further, if there are two nodes of odd degree, those must be the starting and ending points of an Eulerian path. Since the graph corresponding to Königsberg has four nodes of odd degree, it cannot have an Eulerian path.
An alternative form of the problem asks for a path that traverses all bridges and also has the same starting and ending point. Such a walk is called an Eulerian circuit or an Euler tour. An Eulerian circuit exists if and only if the graph is connected and there are no nodes of odd degree. It can be seen that all Eulerian circuits are also Eulerian paths.
Euler's work was presented to the St. Petersburg Academy on August 26, 1735, and published as Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position) in the journal Commentarii academiae scientiarum Petropolitanae in 1741.[1]
[edit] Significance in the history of mathematics
In the history of mathematics, Euler's solution of the Königsberg bridge problem is considered to be the first theorem of graph theory, which is now generally regarded as a branch of combinatorics (although combinatorial problems had been considered much earlier).
In addition, Euler's recognition that the key information was the number of bridges and the list of their endpoints (rather than their exact positions) presaged the development of topology. 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.
[edit] Variations
The classic statement of the problem, given above, uses unidentified nodes — that is, they are all alike except for the way in which they are connected. There is a variation in which the nodes are identified — each node is given a unique name or color.
The northern bank of the river is occupied by the Schloß, or castle, of the Blue Prince; the southern by that of the Red Prince. The east bank is home to the Bishop's Kirche, or church; and on the small island in the center is a Gasthaus, or inn.
It is understood that the problems to follow should be taken in order, and begins with a statement of the original problem:
It being customary among the townsmen, after some hours in the Gasthaus, to attempt to walk the bridges, many have returned for more refreshment claiming success. However, none have been able to repeat the feat by the light of day.
8: The Blue Prince, having analyzed the town's bridge system by means of graph theory, concludes that the bridges cannot be walked. He contrives a stealthy plan to build an eighth bridge so that he can begin in the evening at his Schloß, walk the bridges, and end at the Gasthaus to brag of his victory. Of course, he wants the Red Prince to be unable to duplicate the feat. Where does the Blue Prince build the eighth bridge?
9: The Red Prince, infuriated by his brother's Gordian solution to the problem, wants to build a ninth bridge, enabling him to begin at his Schloß, walk the bridges, and end at the Gasthaus to rub dirt in his brother's face. His brother should then no longer walk the bridges himself. Where does the Red Prince build the ninth bridge?
10: The Bishop has watched this furious bridge-building with dismay. It upsets the town's Weltanschauung and, worse, contributes to excessive drunkenness. He wants to build a tenth bridge that allows all the inhabitants to walk the bridges and return to their own beds. Where does the Bishop build the tenth bridge?
[edit] Solutions
Reduce the city, as before, to a graph. Color each node. As in the classic problem, no Euler walk is possible; coloring does not affect this. All four nodes have an odd number of edges.
8: Euler walks are possible if exactly 2 nodes have an odd number of edges. If this is so, then the walk must begin at one such node and end at the other. Since there are only 4 nodes in the puzzle, solution is simple. The walk is desired to begin at the blue node and end at the orange node. Thus a new edge is drawn between the other two nodes. Since they each formerly had an odd number of edges, they must now have an even number of edges, fulfilling all conditions. This is a change in parity from odd to even degree.
9: The 9th bridge is easy once the 8th is solved. It is desired to enable the red and forbid the blue as a starting point; the orange node remains the end of the walk and the white node is unaffected. To change the parity of both red and blue nodes, draw a new edge between them.
10: The 10th bridge takes us in a slightly different direction. The Bishop wishes every citizen to return to his starting point. This is an Euler cycle and requires that all nodes be of even degree. After the solution of the 9th bridge, the red and the orange nodes have odd degree, so they must be changed by adding a new edge between them.
[edit] Present state of the bridges
Two of the seven original bridges were destroyed by bombs during World War II. Two others were later demolished by the Russians and replaced by a modern highway. The three other bridges remain, although only two of them are from Euler's time (one was rebuilt by the Germans in 1935).[2] Thus, in all, there are five bridges in modern-day Königsberg.
In terms of graph theory, two of the nodes now have degree 2, and the other two have degree 3. Therefore, an Eulerian path is now possible, but since it must begin on one island and end on the other, it is impractical for tourists.[3]
[edit] See also
[edit] References
- ^ The Euler Archive, commentary on publication, and original text, in Latin.
- ^ Taylor, Peter (December 2000). What Ever Happened to Those Bridges?. Australian Mathematics Trust. Retrieved on 2006-11-11.
- ^ Stallmann, Matthias (July 2006). The 7/5 Bridges of Koenigsberg/Kaliningrad. Retrieved on 2006-11-11.
[edit] External links
- Kaliningrad and the Konigsberg Bridge Problem at Convergence
- Euler's original publication (in Latin)
- The Bridges of Königsberg
- How the bridges of Königsberg help to understand the brain
