A Brain Teaser
The eighteenth-century
Swiss mathematician Leonhard Euler was enormously prolific, but he is best
remembered for devising the solution to a recreational math problem: the
Seven Bridges of Koenigsberg. At one time, it was fashionable to stroll
through the Prussian town of Koenigsberg and ponder this problem: Could
one cross each of the seven bridges that traversed the Pregel River and connected
the various districts once and only once?
Although the problem itself was simple - was it possible to walk a circuit that crossed each bridge only once? Euler found the solution by making the situation even simpler. He replaced the bridges and islands of Koenigsberg with lines and points. The four landmasses (two islands and both riverbanks) became special points, or nodes, that were connected by seven lines representing the bridges. Using that abstract graph, Euler demonstrated that to complete a circuit, there would have to be a maximum of two places where an odd number of lines met, and if a return to the start was required, there would have to be no places where an odd number of lines met. The reasoning is simple, once seen: a continuous journey will enter each such junction exactly as often as it leaves except at the start and finish. Since the graph of Koenigsberg had four nodes, each of which possessed an odd number of lines, no solution could exist.
Euler's problem is really one of topology, the branch of mathematics that deals with the properties of figures that are preserved during continuous distortions. Two networks are topologically equivalent if one can be distorted to give the other, as can the city of Koenigsberg and Euler's graph of the city. If a network can be traversed by a single continuous path, so can any topologically equivalent network.
Euler's work on the bridges of Koenigsberg founded the field of graph theory. Not bad for one recreational math puzzle!!!
Borrowed from : 1000 Play Thinks by Ivan Moscovich 2001
Now you try. Can you solve this puzzle using Euler's Ideas?
1. Solve the puzzle.
2. How can this information help you to analyze network matrices.
Although the problem itself was simple - was it possible to walk a circuit that crossed each bridge only once? Euler found the solution by making the situation even simpler. He replaced the bridges and islands of Koenigsberg with lines and points. The four landmasses (two islands and both riverbanks) became special points, or nodes, that were connected by seven lines representing the bridges. Using that abstract graph, Euler demonstrated that to complete a circuit, there would have to be a maximum of two places where an odd number of lines met, and if a return to the start was required, there would have to be no places where an odd number of lines met. The reasoning is simple, once seen: a continuous journey will enter each such junction exactly as often as it leaves except at the start and finish. Since the graph of Koenigsberg had four nodes, each of which possessed an odd number of lines, no solution could exist.
Euler's problem is really one of topology, the branch of mathematics that deals with the properties of figures that are preserved during continuous distortions. Two networks are topologically equivalent if one can be distorted to give the other, as can the city of Koenigsberg and Euler's graph of the city. If a network can be traversed by a single continuous path, so can any topologically equivalent network.
Euler's work on the bridges of Koenigsberg founded the field of graph theory. Not bad for one recreational math puzzle!!!
Borrowed from : 1000 Play Thinks by Ivan Moscovich 2001
Now you try. Can you solve this puzzle using Euler's Ideas?
1. Solve the puzzle.
2. How can this information help you to analyze network matrices.