Friday, May 27, 2011

The Bridges of Konigsberg

From the August 1997 issue of The Mathematical Intelligencer, we have this poem by Judith Saunders about a long-standing puzzle solved solved by the mathematical giant, Leonhard Euler (1707-1783).

The Königsberg Bridge Poem
          Homage to Euler
                                         by Judith Saunders

Flowing throught Königsberg and spanned by seven bridges, the River Pregel surrounds an island (called Kneiphof) in the middle of the city.   It is said that people used to entertain themselves by trying to devise a route around Königsberg which would cross each bridge just once.

Like mice in mazes, locals scampered forth
and back, around and through the town, traversed
and re-traversed the central island, bent
on crossing each of seven bridges once
and only once.
                         You alone declined
to join the briskly questing citizenry.
Knowing the elusive route would not
be found on foot, in chance meandering
(some providential Spaziergang)
you proceeded without stirring from
your chair to take a different sort of trip.

With pen and paper first you razed the place,
demolished houses, Marktplatz, terraces
and domes.  You rid it of shrubbery and trees.
Walls fell.  Cathedrals crumbled.  Squirrels, ducks
and hedgehogs vanished.  Not a lamppost was spared,
not a Denkmal stood.  No cobblestone escaped
your ruthlessly obliterating hand.

And when you'd sheared away particulars,
trimmed Königsburg to the bone, you saw
a skein of penstrokes, luminous patterns
of points and lines, necessary sequences:
where trails of connecitivity led, and where
they failed, and why -- no matter time or place,
terrain or weather.
you built and crossed a single, Ideal Bridge
to reach a quiet Kneiphof of the mind,
an island of essences.  Stripped stark.  Clean.
Bare bedrock of a new geometry.

At the Drexel Math Forum website we find "The Königsberg Bridge Problem" stated in this way:  In Königsberg, Germany, a river ran through the city such that in its center was an island, and after passing the island, the river broke into two parts. Seven bridges were built so that the people of the city could get from one part to another. A crude map of the center of Königsberg might look like this:

The people wondered whether or not one could walk around the city in a way that would involve crossing each bridge exactly once.   Try it.

Imitating the process that Euler used, we may represent Köenigsburg using dots for regions of land and representing bridges with curves, or arcs:

Then, in its stripped down "network" version, the seven bridges problem looks like this:  can we traverse the arcs of the network traveling along each arc once and only once?
The red dots or "vertices" of this network may be identified as "odd" or "even" according to whether there are an odd or an even number of arcs that meet at the vertex.    This network has four odd vertices -- and this "oddness" makes the Königsberg Bridges problem impossible.  (Here is a theorem that Euler was able to prove:  It is possible to trace a network -- going over each arc once and only once and ending at the starting vertex  --  if and only if all vertices of the network are even.)

For further reading:  an online article by Joseph Malkevitch, "The geometry of urban services," celebrates Euler's acheivement and its applications.

No comments:

Post a Comment