Seven Bridges of Konigsburg
Seven Bridges of Konigsburg
Graph theory.
-
- The problem of the Seven Bridges of Königsberg. (Photo credit: Wikipedia)
I used to think that there was no point in giving someone a math problem that was unsolvable. What could you learn from that except your tolerance for frustration? It turns out, though, that mathematicians, even when they suspect a problem has no answer, are not happy until they can prove it.
That is the case with the famous Seven Bridges of Königsburg problem. Leonhard Euler, a Swiss mathematician and physicist, proved this problem had no solution in 1735, and in the process, invented graph theory, structures used to model pairs of objects.
Materials:
- Pen or pencil
- Paper
Instructions:
- Draw two banks of land with a river in the middle
- Draw two islands in the middle of the river
- Draw seven bridges
- Two bridges from one bank to the first island
- Two bridges from the other bank to the first island
- One bridge connecting the two islands
- One bridge connecting one bank to the second island
- One bridge connecting the other bank to the second island
- Find a path across the bridges in which you cross each one once and only once
- You don’t have to start and end at the same place
- You can’t walk halfway across a bridge, turn around and cross the other half later
- The islands can only be reached by the bridges.
What Should Happen?
Since you must enter and leave each landmass over a bridge, there have to be an even number of bridges. You cannot enter and leave on an odd number of bridges. In this problem, each landmass has an odd number of bridges. So, it is not possible to cross every bridge once and only once. If only two of the the land masses had had an odd number of bridges, you could trace a route across the bridges once and only once, in what is called a Eulerian path.
Koenigsburg is a real city that was in Germany, founded in 1255. Since 1946, the city has been called Kalingrad and is in Russia. The bridges described were built between 1286 and 1542. In World War II, two of those bridges were destroyed.
Before Euler, its citizens used to try, on Sunday afternoons, to walk around the city and solve this puzzle. Euler figured out something to simplify the puzzle to start with. It didn’t matter where else people walked in the city. The only thing that mattered for solving this problem was where the bridges met the land. He turned the key factors into a graph, with nodes representing landmasses and lines connecting them representing bridges.
-
- The Königsberg Bridges graph. This graph is not Eulerian, therefore, a solution does not exist. (Photo credit: Wikipedia)
Why Is This Useful?
Graphing theory was a precursor for topology.
These mathematical disciplines are used to schedule efficient routes and networks, like those for computers.
- For a simple explanation for kids, click on mathsisfun.com
- For a more detailed explanation, click on jcu.edu/math
- For a history of the bridges, click on kursinfo.him.olde.no
Carol Covin, Granny-Guru
Author, “Who Gets to Name Grandma? The Wisdom of Mothers and Grandmothers”
http://newgrandmas.com
Don’t forget to follow Grandmother Diaries via Geek Girl on Facebook and Twitter.
Subscribe to updates by email
Filed in: arts & crafts & educational • education • Playtime
I come for a mathematician family and can relate to the need to solve an (perceived) unsolvable problem. They see it as a challenge. It is so fun to watch the excitement and frustration that ensues when in the hunt to find a solution. 🙂
Susan, I think very few kids understand the need for unsolvable problems. Your family learned it's just a different kind of puzzle.
In my math classes, we would have a puzzle of the week to keep things fun and to challenge critical thinking. Many of the puzzles utilized some kind of network theory to solve. Thanks for reminding me of good times. 🙂
You're welcome, Jeff. For the brief six months I taught programmers, I learned I had to keep extra problems for the times they finished the course material. Best part of the class.
This reminds me of the math class I took that was geared toward liberal arts students. At one point, we had to devise efficient routes for postal carriers.
Routes are a perfect application of topology, Jeri!