Bridges Of Konigsberg Solved Assignment
Activity: The Seven Bridges of Königsberg
The old town of Königsberg has seven bridges:
Can you take a walk through the town, visiting each part of the town
and crossing each bridge only once?
This question was given to a famous mathematician called Leonhard Euler... but let's try to answer it ourselves!
And along the way we will learn a little about "Graph Theory".
We can simplify the map above to just this:
There are four areas of the town - on the mainland north of the river, on the mainland south of the river, on the island and on the peninsula (the piece of land on the right)
Let us label them A, B, C and D:
To "visit each part of the town" you should visit the points A, B, C and D.
And you should cross each bridge p, q, r, s, t, u and v just once.
And we can further simplify it to this:
So instead of taking long walks through the town,
you can now just draw lines with a pencil.
Can you draw each line p, q, r, s, t, u and v only once, without removing your pencil from the paper (you may start at any point) ?
Have a try and see if you can.
Did you succeed?
Well ... let's take a step back and try some simpler shapes.
Try these (remember: draw all the lines, but never go over any line more than once, and don't remove your pencil from the paper.)
Put your results here:
So, How Can We Know Which Ones Work and Which Ones Do Not?
But first, time to learn some special words:
Yes, it is called a "Graph"... but it is NOT this kind of graph:
They are both called "graphs".
Diagram 7 has
Diagram 8 has
OK, imagine the lines are bridges. If you cross them once only you have solved the puzzle, so ...
... what we want is an "Euler Path" ...
... and here is a clue to help you: we can tell which graphs have an "Euler Path" by counting how many vertices have an odd degree.
So, fill out this table:
|Shape||Euler Path?||Vertices||how many with even degree||how many with odd degree|
Is there a pattern?
Don't read any further until you have found some kind of pattern ... the answer is in the table.
OK ... the answer is ...
The number of vertices of odd degree must be either zero or two.
If not then there is no "Euler Path"
And if there are two vertices with odd degree, then they are the starting and ending vertices.
And the reason is not hard to understand.
A path leads into a vertex by one edge and out by a second edge.
So the edges should come in pairs (an even number).
Only the start and end point can have an odd degree.
Now Back to the Königsberg Bridge Question:
Vertices A, B and D have degree 3 and vertex C has degree 5, so this graph has four vertices of odd degree. So it does not have an Euler Path.
We have solved the Königsberg bridge question just like Euler did nearly 300 years ago!
Bonus Exercise: Which of the following graphs have Euler Paths?
|Shape||Euler Path?||Vertices||How many with even degree||How many with odd degree|
Leonhard Euler (1707 - 1783), a Swiss mathematician, was one of the greatest and most prolific mathematicians of all time. Euler spent much of his working life at the Berlin Academy in Germany, and it was during that time that he was given the "The Seven Bridges of Königsberg" question to solve that has become famous.
The town of Königsberg straddles the Pregel River. It was formerly in Prussia, but is now known as Kaliningrad and is in Russia. Königsberg was situated close to the mouth of the river and had seven bridges joining the two sides of the river and also an island and a peninsula.
Answer to the diagrams table:
Copyright © 2016 MathsIsFun.com
Math was never my strong suit. Basic Algebra was the limit of my arithmetical competence. Everything beyond that was a struggle. In geometry I struggled to a grade of C, Algebra II a grade of D and I dropped Trigonometry after one week. I knew getting through any university level math courses would be a struggle. Imagine my surprise then, after I got to college and found a course called Infinite Math. It was not nearly as daunting as its name. The course consisted of Maths that could be applied to the real world. My favorite of these was something called Euler Circuits, which meant finding the most efficient route for a journey. There was also the less rigorous Euler Path. Trying to figure out the most efficient Euler Circuit or Path became one of my favorite mathematical exercises. As for the name Euler, it never meant much to me until I recognized it again after many years while reading about Konigsberg, the old capital of Prussia and today the city of Kaliningrad, in the Russian oblast of the same name.
The Seven Bridges of Konigsberg
A Problem Without A Solution – Explaining The Impossible
The Old Town of Konigsberg stood on both sides of the Pregel River. Uniquely, as the river flowed through the city it wove its way around two islands. The more famous of the two was the Kneipfhof which had five bridges going across arms of the river. Another two bridges crossed branches of the river from another island, Lomse. These seven bridges were the genesis of a puzzle that many in the town tried to solve. As one resident of Konigsberg related in a letter to Swiss mathematician Leonhard Euler, couples in the town liked to try and figure out a route to cross every bridge once without ever having to re-cross any of the same bridges again. An even tougher problem would be to do this while ending up back in the same place they began. In 1736 Euler set himself the task of proving that a solution to this problem was impossible. He did this by focusing only on the land masses and bridges. He made each land mass a “point” or in modern parlance a “node”. Each connecting bridge was an “arc”. This abstraction could then be drawn as a graph. Euler’s proof was published in 1741, six years after he first began to study the bridges problem.
The essence of the problem was how to draw this upon a sheet of paper without retracing any line or lifting a pencil off the paper. This laid the basis for the first ever theorem of graph theory. Euler’s name was given to among other things, Euler Paths which is a continuous route that passes every edge once and only once. His name was also given to Euler Circuits, a path beginning and ending at the same starting point without retracing any part of the route. Many people in Konigsberg understood from experience that there was no route that could be followed to cross all Seven Bridges of Konigsberg once and only once without retracing some part of the route. Euler’s innovation was that he could explain the impossibility of a solution and used it to develop the basis for graphs, networks and topology. Euler’s mathematical genius extended to the counter-intuitive. With the Seven Bridges of Konigsberg he proved the rationale, reasoning and intellectual uses of a problem that could never be solved.
The Wooden Bridge – in 1930’s Konigsberg (Credit: Eigenes Werk)
Bridging A Divide – From Konigsberg To Kaliningrad
Crossing the Seven Bridges of Konigsberg as Euler knew them is impossible today, but not because of any mathematical problems. The difficulty arises from the fact that, like almost all of old Konigsberg, most of the bridges no longer exist in their original form. Two of the bridges – Blacksmith’s Bridge and Giblet’s Bridge – were destroyed in the British bombing of the city. Both of those bridges led to and from Kant Island. The bombing which took place on two nights in late August of 1944, also leveled much of the castle and cathedral, though the latter has been rebuilt. Two other bridges – the Shopkeeper and Green Bridge – disappeared after the war to make way for Leninsky Prospekt in what had suddenly become Kaliningrad, a closed Soviet city. Thus, the Seven Bridges of Konigsberg were now three bridges in Kaliningrad. The most popular of the three that still exists today is also the only one that goes to Kneiphof, the aptly named Honey Bridge. Like many other famous bridges in European metropolises it sports hundreds of padlocks which are symbols of those romantic couples hoping these symbols will secure their love forever.
The Honey Bridge leads between the reconstructed Cathedral and the Fishing Village, two of the most famous spots in the Old Town which only adds to the foot traffic. Another bridge which is original, the Wooden Bridge, was lucky enough to escape destruction by either bombs or Bolsheviks. For historical harmony, it would be nice if all the bridges were rebuilt, only one holds that honor and it was rebuilt before the war by Germans, not afterwards by the Soviets. It is known simply as the High Bridge. The upshot of all this bridge building, crossing and destruction is that only two of the seven bridges that existed during Euler’s time can still be found in their original form today. It is easy enough to cross those two bridges without having to retrace one’s footsteps. Yet there were and still are many more bridges in Konigsberg to cross, perhaps not as famous, but just as important in their own way.
Leonhard Euler – mathematical genius (Credit: Jakob Emanuel Handmann)
Fits Of Mathematical Imagination – The Seven Bridges Of Kaliningrad
One can only speculate as to all the different problems and solutions Euler could have concocted by adding or subtracting these bridges in his theoretical fits of mathematical imagination. Today Euler would have the option of adding the newly built or refurbished Flyover and Jubilee Bridges to his equation. This has brought the total of bridges in the city back up to seven. Many things have changed in Kaliningrad and Konigsberg is no more, but the Seven Bridges problem still exists, albeit in extremely modified form.