Wegen Jugendschutz darf die Links im Artikel nur anklicken, wer mindestens 16 Jahre alt ist.

Ich weiß nicht, ob es mit dem Jahr der Mathematik zu tun hat. Jedenfalls findet man jetzt in manchen Kneipen Bierdeckel mit Mathe-Rätseln. Wer dort nicht zum Knobeln kommt, kann die Bierdeckel-Rätsel auch online bei Jever lösen. Wie gesagt, nur für über 16-jährige. (Bei Jever nimmt man den Jugendschutz wirklich ernst. Das kann man nicht oft genug wiederholen.)
Einer der Bierdeckel stellt folgendes graphentheoretische Problem:

i-b6d1c9cbca4bddf7f87e618862ccaa62-deckel_spiel_friesentour.gif

Die anderen Rätsel (und auch die Lösungen) sind hier.

Die Aufgabe mit der Friesentour ist übrigens eine Variante des Königsberger Brückenproblems: Euler hatte 1736 bewiesen, daß es keinen Spaziergang durch Königsberg gibt, bei dem jede Brücke einmal und nur einmal überquert wird. (Die Bierdeckel-Aufgabe ist etwas einfacher, weil man zwar jeden Punkt besuchen, aber nicht jede “Brücke” überqueren muß.)

i-ac2c4ccfaf130be919a3d661ea880646-Konigsberg_bridges.png
Euler’s Arbeit zum Brückenproblem wird gelegentlich als Geburtsstunde der Topologie bezeichnet, nach heutiger Terminologie gehört sie aber eher in die Graphentheorie. Die Lösung ist nicht schwer: weil die Insel in der Mitte 5 Brücken hat, kann sie nicht gleich oft betreten und verlassen werden (wenn man jede Brücke einmal und nur einmal benutzt). Also gibt es keinen Spaziergang, der jede Brücke genau einmal benutzt.

Euler hatte dann auch allgemein untersucht, welche Bedingungen ein Stadtplan erfüllen muß, damit es einen solchen Spaziergang gibt: Die einzige Bedingung ist, daß jeder Teil von einer geraden Anzahl von Brücken zu erreichen ist.

i-2ca69373cde080df5ab4dde4e05f87f1-konisberg.jpg

Die Lösung in Gedichtform (paßt nicht ganz auf einen Bierdeckel):


Seven bridges spanned the River Pregel,
Many more than might have been expected,
Konigsberg’s wise leaders were delighted
To have built such very splendid structures.

Crowds each ev’ning surged towards the river,
People walked bemused across the bridges,
Pondering a simple sounding challenge
Which defeated them and left them puzzled.

Here’s the problem; see if you can solve it!
Try it out at home on scraps of paper,
Starting out and ending at the same spot,
You must cross each bridge just once each evening.

Eulerian graphs all have this restriction:
THE DEGREE OF ANY POINT IS EVEN.
That’s the oldest graph result
That mankind has ever known.

All the folk in Konisberg were frantic!
All their efforts ended up in failure!
Happily, a learned mathematician
Had his house right there within the city.

Euler’s mind was equal to the problem
“Ah”, he said, “You’re bound to be disheartened,
Crossing each bridge only once per outing
Can’t be done, I truly do assure you.

Laws of Nature never can be altered,
We can’t change them, even if we wish to.
Nor can flooded rivers or great bridges
Interfere with scientific progress.

War brought strife and ruin to the Pregel,
Bombs destroyed those seven splendid bridges.
Euler’s name and fame will, notwithstanding,
Be recalled with Konigsberg’s for ever.

Mehr Informationen zu den Königsberger Brücken findet man hier. Es sind im Lauf der Zeit natürlich weitere Brücken gebaut bzw. auch im Krieg zerstört worden. Im heutigen Kaliningrad sind Spaziergänge möglich, bei denen jede Brücke genau einmal überquert wird, bei denen allerdings der Endpunkt nicht der Startpunkt ist. (In mathematischer Terminologie: es gibt einen Eulerweg, aber keinen Eulerkreis.)

i-a3f9a29f7cbee6d3ecdf675b985204b6-puentes.jpg

(via microsiervos via cgredan)

Kommentare (4)

  1. #1 Thilo Kuessner
    7. März 2009

    Im ALGTOP-Verteiler wurde gerade diskutiert, ob Euler überhaupt je in Königsberg gewesen ist. Prof.em. Rudolf Fritsch (LMU München) schreibt dazu:

    I am just visiting Professor in Königsberg (at the Russian State
    Immanuel-Kant-University Kaliningrad) and lecturing on graph theory clearly starting with famous bridge problem and showing slides from Eulers original paper in “Commentarii Academiae scientiarum Petropolinae” from 1736.
    At the time Euler worked in St. Petersburg as academician.
    As far as I know Euler never visited Königsberg, it is said that he learned the problem from the Mayor of Danzig.
    He might have got some familarity with Königsberg from the secretary of the Petersburg academy at that time, Christian Goldbach from Königsberg, the namesake of the Goldbach conjecture.

  2. #2 John
    26. Februar 2016

    Schön was über Graph-Theorie hier zu lesen is nur leider falsch. Das Problem auf dem Bierdeckel ist ein Abwandlung eines Hamiltonpathproblems nicht die des Königsbergerbrückenproblems. Das Königsbergerbrückenproblem setzt voraus das jede “Brücke” oder Kante einmal besucht wird. Das ist hier nicht gefragt und auch nicht möglich. Dafür müsste jeder Punkt eine gerade Anzahl an Kanten haben, das ist zum Beispiel an Punkt 15 nicht der Fall. Beim Hamilton Path wird nur gesagt das er jeden Punkt einmal besucht haben muss. Und da es ein Path ist darf er auch keine Kante zweimal genutzt werden.
    https://de.wikipedia.org/wiki/Hamiltonkreisproblem

  3. #3 rolak
    26. Februar 2016

    ..ede “Brücke” oder Kante einmal besucht wird. Das ist hier nicht gefragt..

    Und das hat Deine tiefstmögliche Analyse von “..,.und fahre keine Strecke doppelt” ergeben, John?

  4. #4 John
    27. Februar 2016

    Nein.
    Den Ausschnitt meines Satzes, den du gibst, ist keine Analyse, sondern nur die Wiedergabe das Brückenprobelms: Jede Kante MUSS einmal besucht werden.
    Das Zitat was du gibts stammt vom Bierdeckel und bedeutet das gleich wie: Jede Kante KANN einmal und nur einmal besucht werden, muss aber nicht.
    Das ist das Hamiltonkreisproblem. Ich denke der Unterschied ist offensichtlich.
    Oder ich weiß nicht was du meinst.