Das Modul "Graphentheorie" ist ein Bestandteil der mathematisch-naturwissenschaftliche Profillinie an unserer Schule für die Klassenstufe 8.
Graphentheorie ist ein spannendes Teilgebiet der Mathematik und Informatik mit zahlreichen Anwendungsgebieten. Dabei kommen interessante Frage- und Problemstellungen auf, die auf den ersten Blick keinen Bezug zur Mathematik haben. Dies liegt daran, dass die Methoden der Graphentheorie den Schülerinnen und Schülern aus dem normalen Regelunterricht Mathematik nicht bekannt sind und somit nicht als Mathematik wahrgenommen werden. Auch stößt man dabei auf Probleme, für die die Mathematik noch keine effizienten Lösungen gefunden wurden. Ausgangspunkt des Moduls war die Fragestellung: Gibt es einen Weg an, bei dem alle sieben Brücken der Stadt Königsberg überquert werden, ohne eine Brücke mehr als einmal zu benutzen?
Diese Fragestellung wurde von dem Schweizer Mathematik Leonard Euler (1707-1783) untersucht, und er bewies mit Mitteln der Mathematik, dass es keinen solchen Spaziergang geben kann. Dabei entwickelte er ein neues mathematisches Teilgebiet, die Graphentheorie. Sie ist ein mathematisches Teilgebiet, das sich mit einer Menge von Objekten und deren Verbindungen beschäftigt. Graphen werden in der Praxis häufig als Modelle verwendet, um Probleme zu lösen: Routenplanung (kürzeste/schnellste Route von A nach B) Stadt- und Verkehrsplanung (Bau neuer Straßen, Autobahnen und Schienen um Verkehrsfluss zu verbessern) Optimale Routen (für Müllabfuhr/Straßenreinigung/Post/Winterdienst; Rundreisen) Telekommunikation (Anmietung vom möglichst wenigen Netzleitung, die aber das komplette Netz abdecken) Projektplanung Fertigung von Leiterplatten
Die Arten von Graphen, die Darstellung von Graphen und die Isomorphie von Graphen stehen als anwendungsorientierte Problemstellungen zum Einstieg in die Graphentheorie im Vordergrund. Zuerst wird das Problem, eine optimale Route von A nach B zu finden, behandelt. Eingeleitet wird dieses Kapitel mit dem erstaunlichen Phänomen der kombinatorischen Explosion, wenn man alle möglichen Wege ausprobieren würde, um einen optimalen Weg zu finden. Selbst ein Computer, der eine Million Wege pro Sekunde austesten könnte, stößt dabei an seine Grenzen. Diesbezüglich wird die Breitensuche (mit möglichst wenigen Haltestellen im U-Bahnnetz von Berlin von A nach B zu kommen) und der Algorithmus von Dijkstra (wie ein Navigationssystem eine optimale Route von A nach B findet) als Lösungsverfahren dieser Problemstellung erarbeitet. Eine wichtige Datenstruktur in der Informatik sind Bäume. Diese sind speziellen Graphen, sie sind Gegenstand des dritten Kapitels des Moduls. Insbesondere das Finden von (minimalen) Spannbäumen in Graphen ist Ausgangspunkt für das Entwickeln weiterer Verfahren (Breitensuche, Algorithmus von Prim sowie der Algorithmus von Kruskal). Der letzte Themenbereich des Moduls behandelte Touren. Mit den Eulerwegen bzw. -touren wird dabei die Verbindung zum Einstiegsproblem ("Königsberger Brückenproblem") geschlossen. Auch werden in diesem Zusammenhang Kriterien bewiesen, wann Figuren ohne abzusetzen und ohne eine Kanten mehr zu benutzen gezeichnet werden können. Der Abschluss des Moduls behandelt das sogenannte Problem des Handlungsreisenden (auch „Rundreiseproblem" oder engl. "Traveling Salesman Problem - TSP" genannt).
Die Verwendung anwendungsorientierter Probleme in Verbindung mit der Erkenntnis, dass Brute-Force-Methoden aufgrund der kombinatorischen Explosion keine effizienten Lösungen ermöglichen, motiviert die Schülerinnen und Schüler, eigene Lösungsheuristiken zu entwickeln. Die Entwicklung und Formulierungen eigener Algorithmen stellt daher einen der Schwerpunkte dieses Moduls dar. Es geht demnach nicht darum, vorgegebene Algorithmen abzuarbeiten, da dies keine kreative Tätigkeit anregt.
Weitere Schwerpunkte sind u. a. die Modellierung von Problemen mittels Graphen sowie dem Begründen und Beweisen von Eigenschaften.
(Lehrer: Matthias Richter)
(Fotos: Steffen Wachter)
