„Graphentheorie – Vom Königsberger Brückenproblem zum Traveling-Salesman-Problem“
Am Donnerstag, 04.07.2013, besuchten Frau Dr. Christina Büsing und Frau Annika Thome, M.Sc., Mathematikerinnen der RWTH-Aachen (Lehrstuhl für Operations Research), den Mathematik-Leistungskurs 1 der Jahrgangsstufe Q1 des Stiftischen Gymnasiums. Auf Einladung von Kurslehrer Dr. Jens Paulßen führten sie einen Workshop zum Thema „Graphentheorie – Vom Königsberger Brückenproblem zum Traveling-Salesman-Problem“ durch.
Einblicke in den Workshop zur Graphentheorie
Die Graphentheorie ist eine der jüngeren mathematischen Disziplinen. Sie fand ihren Anfang im sogenannten Königsberger Brückenproblem. Im Zentrum dieses im frühen 18. Jahrhundert formulierten Problems steht die Frage, ob sich die sieben Königsberger Brücken über den Pregel derart genau einmal überqueren lassen, dass sich ein Rundweg ergibt. Der Mathematiker Leonhard Euler konnte 1736 beweisen, dass dies nicht möglich ist. Dieses leicht zugängliche Problem erforderte dabei jedoch eine beachtliche mathematische Denkarbeit. Dies zeigt sich – gewissermaßen als äußeres Zeichen – auch daran, dass derartige geschlossene Wege, bei denen die einzelnen Wegabschnitte nur genau einmal durchlaufen werden, heute auch als Euler-Wege bezeichnet werden. Die wesentlichen Fragen und Resultate lassen auch abseits eines realen Kontextes formulieren. So spielt es keine Rolle, wofür die einzelnen „Wegpunkte“ und die „Verbindungen“ konkret stehen. Verallgemeinert man das zu Grunde liegende Konzept, so erhält man mathematische Strukturen, die heute als Graphen bezeichnet werden. Sie bestehen aus Knoten und Kanten, die als mathematische Formalisierung für die Wegpunkte und Verbindungen stehen. Die entsprechenden Euler-Wege werden daher verallgemeinert auch als Euler-Graphen bezeichnet.
Im Workshop hatten die Schülerinnen und Schüler unter Anleitung von Frau Dr. Büsing und Frau Thome die Möglichkeit, mithilfe verschiedener „Knobel-Aufgaben“ einen tieferen Zugang zu dem Problem zu entwickeln. Diese Phase des Workshops resultierte im Theorem von Euler, das eine vollständige Charakterisierung der Euler-Graphen liefert. Euler war es dabei nicht möglich, den Beweis des Theorems vollständig zu führen. Dies gelang erst – rund 150 Jahre später – dem Mathematiker Carl Hierholzer mit seinem heute als Hierholz-Algorithmus bezeichneten konstruktiven Beweis (siehe Foto der Präsentationsfolie).
Im zweiten Teil des Workshops ging es um das sogenannte Traveling-Salesman-Problem. Hierbei handelt es sich erneut um eine recht einfach zugängliche Problemstellung, deren Lösung jedoch ebenfalls tiefe mathematische Erkenntnisse erfordert. Man stelle sich einen Handlungsreisenden vor, der eine vorgegebene Anzahl von Städten – beispielsweise in Deutschland – besuchen soll. Bei der Planung seiner Tour ist es natürlich sinnvoll, eine Reihenfolge der Städte zu wählen, sodass die resultierende Gesamtstrecke minimal wird. Die entscheidende Frage scheint dann schon fast offensichtlich: Wie sollte diese Strecke gewählt werden bzw. gibt es ein (konstruktives) Verfahren, eine solche Tour zu generieren? Eine naive Methode könnte natürlich wie folgt aussehen: Mittels einer computergestützten Tabellenkalkulation werden einfach alle möglichen Routen generiert, die entsprechenden Wegstrecken berechnet und schließlich die kürzeste Route gewählt. Wie die Schülerinnen und Schüler jedoch im Workshop erarbeiten konnten, wächst der Rechenaufwand und somit auch die Zeit (mindestens) exponentiell in Abhängigkeit von der Anzahl der Städte. Daraus folgt, dass schon für 16 Städte eine Rechenzeit von zwei Monaten und für 25 Städte bereits eine Rechenzeit von erstaunlichen 109 mal 10 hoch 9 Jahren (das Universum ist hingegen lediglich geschätzte 13,7 mal 10 hoch 9 Jahre alt!!!) erforderlich ist.
Der Schlüssel zu diesen Problem findet sich wieder in der Graphentheorie. Daher interessieren sich auch beispielsweise Firmen, die Navigationssysteme bzw. deren Software produzieren, sehr für aktuelle Forschungsergebnisse in diesem Bereich. Weitere Anwendungsfelder finden sich bei bestimmten Organisationsproblemen, etwa der Steuerungssoftware für die Computer, die die Gepäckbänder eines Flughafens steuern, aber auch in Bereichen wie der Hörsaalplanung oder auch der Erstellung von Stundenplänen in Schulen.
Gruppenfoto des LK Mathematik zusammen mit C. Büsing und A. Thome
Somit hatten die Schülerinnen und Schüler einerseits einfach einen Einblick in eine spannende mathematische Disziplin, die über die Schulmathematik hinausgeht. Andererseits konnte aber auch unmittelbar erfahren werden, wo (diese Art der) Mathematik im „täglichen Leben“ von großer Bedeutung ist – eine Erfahrung, die man – einmal gemacht – nicht mehr missen möchte!
(Pau)