The Königsberg Bridge Problem or Where Graph Theory was Invented

If you’ve studied graph theory you may have bumped into The Königsberg Bridge Problem which is essentially the first modern use of Graph Theory.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.
The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk halfway onto the bridge and then turn around to come at it from another side).

Euler proved that the problem has no solution.
To start with, Euler pointed out that the choice of route inside each landmass is irrelevant. The only important feature of a route is the sequence of bridges crossed. This allowed him to reformulate the problem in abstract terms (laying the foundations of graph theory), eliminating all features except the list of landmasses and the bridges connecting them. In modern terms, one replaces each landmass with an abstract “vertex” or node, and each bridge with an abstract connection, an “edge”, which only serves to record which pair of vertices (landmasses) is connected by that bridge. The resulting mathematical structure is called a graph.

… you should probably take a look at the full Wikipedia node. It’s a clever proof.

Anyway. I thought it would be fun to one days visit Königsberg which is now the modern day city of Kaliningrad in Russia.

Then it dawned on me that I could use Google Maps to find it and sure enough it’s still there.

One of the bridges appears to have been removed.

200907141908

200907141907



%d bloggers like this: