Posted by: Dave Richeson | September 25, 2008

Königsberg today

In 1736 Leonhard Euler solved the now-famous bridges of Königsberg problem.  It is often hailed as the birth of topology and graph theory. Although no graph appears in Euler’s paper, his argument is topological in spirit. (He proved another famous topological theorem a decade and a half later.)

The problem is stated as follows. If a resident of Königsberg were to stroll through the city, would it be possible for her to cross all seven bridges without crossing one of them twice?  If so, is it possible to do so starting and ending at her house?  Below is a map of Königsberg from roughly that era.

The modern solution is to turn the problem into a graph theory problem.  Place a vertex on each landmass and add an edge for each bridge.  Euler discovered that there exists such a route if, and only if, there are zero or two vertices of odd degree (the degree of a vertex is the number of edges that meet at the vertex).  If there are zero, then it is possible to start and end at home.  If there are two, then the route must start and end on the landmasses of odd degree. As we see below, 1736 Königsberg has four vertices of odd degree.  So no such walk is possible.

On a whim, I decided to look for Königsberg and its bridges on Google Maps. (The city happens to be called Kaliningrad today.)

It turns out that two bridges are gone and there is one new one, so the graph is completely different! (There are several unidentifiable objects crossing the river.  I had to zoom in to see what is a bridge and what is not.) Unfortunately for the residents of Kaliningrad, there are still four vertices of odd degree.  So they still can’t take their city-wide stroll and not cross a bridge twice.

About these ads

Responses

  1. [...] A topological map is a map that is only concerned with relative locations of features on the map, not on exact locations. A famous example is the graph that we use to solve the Bridges of Königsberg problem. [...]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 204 other followers

%d bloggers like this: