|
SEVEN BRIDGES OF KÖNIGSBERG
Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregolya and the bridges.
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 question is whether it is possible to walk with a route that crosses each bridge exactly once, and return to the starting point. In 1736, Leonhard Euler proved that it was not possible.
Circa 1750, the prosperous and educated townspeople allegedly walked about on Sundays trying to solve the problem, but this might be an urban legend.
Euler's solution
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 there are no nodes of odd degree. Such a walk is called an Eulerian circuit or an Euler tour. Since the graph corresponding to Königsberg has four nodes of odd degree, it cannot have an Eulerian circuit.
The problem can be modified to ask for a path that traverses all bridges but does not have the same starting and ending point. Such a walk is called an Eulerian path or Euler walk. Such a path exists if and only if the graph has exactly two nodes (or none) of odd degree, those nodes being the starting and ending points. (So this too was impossible for the seven bridges of Königsberg.)
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.
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.
• Solutions to the variants are hidden on this page. If you have trouble viewing them, you may also see the solutions here.
The Blue Prince's eighth bridge
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?
Solution
This Euler walk is desired to begin at the blue castle (which can be thought of as the blue node) and end at the inn, or the beer-colored node. Thus a new edge is drawn between the other two nodes between the Red Prince's castle and the church. Since they each formerly had an odd number of edges, they must now have an even number of edges. This is a change in parity from odd to even degree. The graph now has exactly two nodes of odd degree--the Blue Prince's castle and the inn. Thus, the Blue Prince can perform an Euler walk to the inn or anyone starting at the inn could perform an Euler walk to the Blue Prince's castle, but the Red Prince is unable to get to the inn.
The Red Prince's ninth bridge
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?
Solution
In this case, the required solution is for the Red Prince's castle and the inn to have an odd number of edges, while the church and the Blue Prince's castle have an even number. The church has an even number already, and the inn already has an odd number. The Red Prince's castle has 4 edges, an even number, while the Blue Prince's has 3. To make the red node of odd degree and the blue node of even degree, the Red Prince must build a bridge between those two—giving his castle 5 edges and the Blue Prince's 4. Again, there are exactly two nodes of odd degree, but now they are the Red Prince's castle and the inn. The Red Prince can perform the walk, but the Blue Prince cannot.
The Bishop's tenth bridge
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?
Solution
His desired result is a circuit rather than a walk. This requires that all nodes have an even number of edges. Following the Red Prince's construction, the church and the Blue Prince's castle each have an even number. It is the Red Prince's castle and the inn that have odd numbers, 5 each. To bring them to even numbers, the Bishop must build a bridge between the Red Prince's castle and the inn. This completes the Eulerian circuit as all nodes are of even degree. Everyone can traverse each bridge precisely once and return to their starting point. Of course, this means that anyone starting at the inn will return there!
See also
External links
|