Diese Seiten können nicht richtig dargestellt werden, da Sie Ihren Internet Explorer mit aktivierter Kompatibiltätsansicht verwenden. Wir empfehlen 'fu-berlin.de' aus der Liste der Websites mit aktivierter Kompatibilitätsansicht zu entfernen:
- Blenden Sie bitte in Ihrem Internet Explorer die Menüleiste ein, indem Sie entweder 'Alt' drücken oder in der Adressleiste mit der rechten Maustaste klicken und dann 'Menüleiste' auswählen.
- Klicken Sie auf 'Extras' und wählen das Menü 'Einstellungen der Kompatibilitätsansicht' aus.
- Wählen Sie unter 'Zur Kompatibilitätsansicht hinzugefügte Websites' 'fu-berlin.de' aus.
- Klicken Sie auf 'Entfernen'.
Das Königsberger Brückenproblem (3. Semester)
Das Königsberger Brückenproblem ist ein Klassiker in der Informatik und Mathematik. Leonhard Euler löste dieses mathematische Problem 1736 direkt am konkreten Beispiel der Stadt Königsberg, der Hauptstadt des damaligen Ostpreußens. Dort vereinigen sich Alter und Neuer Pregel zum Fluss Pregel. Im 18. Jahrhundert überquerten nur sieben Brücken die Flüsse, insbesondere führten sie auch auf eine Insel.
Es kam die Frage auf, ob es einen Rundweg gibt, bei dem man alle Brücken der Stadt genau einmal überquert und wieder zum Ausgangspunkt zurückgelangt.
Das Brückenproblem ist kein klassisch geometrisches Problem, da es nicht auf die genaue Lage der Brücken ankommt, sondern vielmehr darauf, welche und wieviele Brücken die Inseln und Ufergebiete miteinander verbinden. Es handelt sich deshalb um ein sogenanntes topologisches Problem. Euler entwickelte dazu Methoden, die wir heute der modernen Graphentheorie zuordnen - einer Theorie, die mittlerweile in vielen Bereichen der Informatik Verwendung findet.
Geboren am 15. April 1707 in Basel als Sohn eines Pfarrers, studierte Leonhard Euler an der Universität Basel zunächst Philosophie und Theologie, bevor er sich dem Studium der Mathematik bei Johann Bernoulli zuwandte. 1727 folgte er einem Ruf an die St. Petersburger Akademie der Wissenschaften. Zunächst wirkte er hier als Adjunkt, ab 1730 als Professor für Physik und nach der Rückkehr Daniel Bernoullis nach Basel im Jahre 1733 als Professor für Mathematik. 1741 übersiedelte Euler nach Berlin, wo er einen wesentlichen Anteil am Aufbau der Preussischen Akademie der Wissenschaften unter Friedrichs II. von Preussen leistete. Hier bekleidete Euler das Amt des Direktors der Mathematischen Klasse. Aufgrund von Unstimmigkeiten mit Friedrich II. kehrte Euler 1766 an die St. Petersburger Akademie zurück, wo ihm Katharina die Große einen ehrenvollen Empfang bereitete. Trotz einer schweren Augenkrankheit, die zu seiner vollständigen Erblindung führte, blieb er bis zu seinem Tod am 18. September 1783 überaus produktiv.
Er verfasste über 900 Arbeiten, davon rund 40 Monographien. Die Bandbreite seiner wissenschaftlichen Tätigkeit ist heute unvorstellbar. Euler lieferte maßgebliche Beiträge zur Algebra, Zahlentheorie, Analysis, Mechanik und Physik, Geometrie und Trigonometrie, Astronomie, Schiffbau, Artillerie und Architektur sowie Philosophie, Musiktheorie und Theologie. Euler gilt als der Begründer der Analysis - in seinem Grundlagenwerk Introductio in analysin infinitorum wurde zum ersten Mal der Begriff der „Funktion“ verwendet. Entsprechend geht ein großer Teil der modernen mathematischen Symbolik auf Euler zurück.
Insbesondere schreibt man ihm auch eine der schönsten Formeln der Mathematik zu:
eiπ + 1 = 0
Dabei bezeichnet e die Eulersche Zahl, i die imaginäre Einheit (definiert durch i²=-1) und π die Kreiszahl.
1. Aufgabe
Unsere Aufgabe ist es nun, das Königsberger Brückenproblem als Graph zu modellieren: aus den Brücken werden Kanten und aus den Stadtteilen Knoten, eine Kante verläuft zwischen zwei Knoten genau dann, wenn eine Brücke die entsprechenden Stadtgebiete verbindet. Daraus ergibt sich der abgebildete Graph.
Die Frage nach dem Rundgang in Königsberg wird nun zur Frage nach einem geschlossenen Weg durch den Graphen, der genau einmal jede Kante durchläuft - einen solchen Weg bezeichnet man als geschlossenen Eulerweg.
Bitte beantworten Sie nun die folgende Frage:
Gibt es für den Graphen zum Königsberger Brückenproblem einen geschlossenen Eulerweg?
Bezeichnet man als den Grad eines Knotens die Anzahl der Kanten, die diesen Knoten mit anderen Knoten verbindet, so kann man zeigen, dass es genau dann einen geschlossenen Eulerweg gibt, wenn der Graph zusammenhängend ist und jeder Knoten geraden Grad hat. Schließlich muss man jedes Gebiet, das man über eine Brücke erreicht, über eine andere Brücke wieder verlassen.
2. Aufgabe
Das „Haus vom Nikolaus“ kennt jeder aus seiner Kindheit und ist letztendlich eine ganz ähnliche Fragestellung: kann man in einem Zug den Graphen zeichnen, ohne abzusetzen oder eine Strecke doppelt zu fahren?
Im Unterschied zum Königsberger Brückenproblem muss man zum Ausgangspunkt nicht notwendigerweise zurückkehren – wir sprechen daher auch von einem Eulerweg, jedoch nicht notwendigerweise geschlossen.
Welcher der folgenden Graphen besitzt einen Eulerweg?
Ein zusammenhängender Graph besitzt genau dann einen Eulerweg, wenn die Anzahl der Knoten mit ungeradem Grad entweder zwei oder null ist. Im ersten Fall bestimmen diese Knoten jeweils Anfang und Ende des Weges, im zweiten Fall ist der Weg sogar geschlossen.
Das Problem lässt sich recht einfach auf den geschlossenen Eulerweg zurückführen, indem man eine zusätzliche Kante zwischen den Knoten ungeraden Grades einführt, damit die Existenz eines geschlossenen Eulerwegs hat und anschließend die zugefügte Kante entfernt.
3. Aufgabe
Wir wissen nun von der Existenz eines (geschlossenen) Eulerwegs unter gewissen Umständen, aber wie konstruiert man einen solchen? Dafür geben wir hier einen Algorithmus an, genannt Algorithmus von Hierholzer. Wir gehen dabei von einem zusammenhängenden Graphen G aus (sprich je zwei Knoten sind immer durch einen Weg verbunden), der nur Knoten mit geraden Grad aufweist. Geschlossene Wege bezeichnen wir auch als Kreise.
Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten, die nacheinander ausgeführt werden. Somit können sie zur Ausführung auch in einem Computerprogramm implementiert werden. Bei der Problemlösung wird eine bestimmte Eingabe (Input) in eine bestimmte Ausgabe (Output) überführt.
Leider wurde die Reihenfolge der Einzelschritte durcheinander geworfen – sortiere sie neu, so dass am Ende ein geschlossener Eulerkreis konstruiert wird.
Wenn K ein Eulerkreis ist, breche ab. Andernfalls:
Vernachlässige nun alle Kanten des Unterkreises K.
Füge in K den zweiten Kreis K' ein, indem der Startknoten von K' innerhalb K durch alle Knoten von K' in der entsprechenden Reihenfolge ersetzt wird.
Wähle einen beliebigen Knoten v des Graphen G und konstruiere von v ausgehend einen Unterkreis K in G, der keine Kante in G zweimal durchläuft.
Nenne jetzt den so erhaltenen Kreis K und fahre bei Schritt 2 fort.
Am ersten Knoten von K, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis K' entstehen, der keine Kante in K durchläuft und keine Kante in G zweimal enthält.
Die richtige Reihenfolge lautet wie folgt:
- Wähle einen beliebigen Knoten v des Graphen G und konstruiere von v ausgehend einen Unterkreis K in G, der keine Kante in G zweimal durchläuft.
- Wenn K ein Eulerkreis ist, breche ab. Andernfalls:
- Vernachlässige nun alle Kanten des Unterkreises K.
- Am ersten Knoten von K, dessen Grad größer 0 ist, lässt man nun einen weiteren Unterkreis K' entstehen, der keine Kante in K durchläuft und keine Kante in G zweimal enthält.
- Füge in K den zweiten Kreis K' ein, indem der Startknoten von K' innerhalb K durch alle Knoten von K' in der entsprechenden Reihenfolge ersetzt wird.
- Nenne jetzt den so erhaltenen Kreis K und fahre bei Schritt 2 fort.
Will man einen nicht geschlossenen Eulerweg konstruieren, so verbindet man die beiden Knoten ungeraden Grades mit einer Kante, führt den Algorithmus aus und entfernt schließlich wieder die zusätzlich eingefügte Kante.