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'.
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?