Posts
X Bridges of Königsberg
The recent Spiked Math comic strip proposes some cheats to build an Eulerian path over the famous bridges of Königsberg, which was originally impossible. Here is the strip:
It turns out that in practice another solution worked out (in fact, the mix of the engineer’s and mythbuster’s solutions). You can ruin the city during a world war and then transfer it to Russians, who will build the new bridges instead. I’ve been to Kaliningrad (the city has been renamed too) two years ago, but did not try to solve the Euler’s problem in field. Let’s find out if it is possible now. Look at the modern map:
View Königsberg bridges in a larger map
So, the modified Spiked Math’s scheme looks as follows (the new bridges are shown in light blue):
Is there an Eulerian path nowadays, i.e. can you walk through the city and cross each bridge once and only once? Recall the theorem:
A connected graph allows an Eulerian path if and only if it has no more than two vertices of an odd degree.
In the picture above, two pieces of land have even number of incident bridges, while the Kneiphof island in the center has degree 3, and the left bank (in the bottom) has degree 5. This means that now Eulerian paths exist. Any such path should begin in the left bank and end in the island, or vice-versa. It may be a good idea to finish your journey near the grave of Immanuel Kant. :) However, there is no Eulerian conduit, i.e. closed Eulerian path.
PS. 1. If you zoom out the above map, you’ll see one more piece of land and two more bridges on the East. However, it only adds a vertex of degree 2, and swaps parity of the banks, so the properties of the new graph are similar, you just need to start/finish your journey in the right bank, not the left one (and walk 10 km more).
2. When I was preparing this article, I found a similar analysis. It used an old map, so the Jubilee bridge and the 2nd Estacade bridges were not marked (they were built in 2005 and 2012, respectively), and also ignored the Reichsbahnbrüke (railroad bridge, but seems pedestrian-accessible).
3. It would be more interesting to analyze the bridge graphs of other cities with more islands like St. Petersburg (several hundred bridges) or Amsterdam (numerous bridges/canals, but have structure).
4. Here is Euler’s original paper (in Latin) with his drawings of the above schemes.
4. Here is Euler’s original paper (in Latin) with his drawings of the above schemes.
17 May 2013 00:41
Superb, what a webpage it is! This webpage presents helpful data to us, keep it up.
Also visit my web blog how can a 14 make money online
17 May 2013 01:11
I am curious to find out what blog system you happen to be utilizing?
I'm experiencing some minor security issues with my latest website and I would like to find something more safe. Do you have any suggestions?
Feel free to surf to my website :: http://www.pizzeriaheden.se/
17 May 2013 01:15
Usually I do not read post on blogs, however I wish to say that this write-up
very compelled me to try and do so! Your writing taste
has been amazed me. Thanks, very nice post.
Visit my web page :: make money working online
17 May 2013 01:20
A person necessarily help to make severely posts I might state.
This is the first time I frequented your web page and so far?
I surprised with the analysis you made to create this particular
put up incredible. Excellent activity!
Feel free to visit my homepage: how to make legal money online
18 May 2013 07:06
It's an awesome post for all the internet users; they will get benefit from it I am sure.
Feel free to visit my blog; most effective cellulitis therapies