Graphentheorie

Die Graphentheorie ist ein Teilgebiet der Diskreten Mathematik. Sie untersucht Eigenschaften und Beziehungen von mathematischen Graphen. Als Graph wird dabei eine Struktur bezeichnet, die sich aus Kanten und Knoten zusammensetzt. Das Liniennetz der Bahn kann beispielsweise zu einem Graph abstrahiert werden. Jeder Bahnhof wäre dann ein Knoten und jede vorhandene Bahnstrecke eine Kante des Graphen.

Nicht nur das Bahnnetz kann auf diese Art abstrahiert werden. Für jede Struktur können so Abhängigkeiten dargestellt werden. Mathematiker untersuchen ganz abstrakt die Eigenschaften beliebiger Graphen. Ihre Ergebnisse können dann auf die ursprünglichen Probleme, beispielsweise den Fahrplan, zurückgeführt werden.

Hat man ein Problem so reduziert und abstrahiert, dass man es als Graphen darstellen kann, können Sätze und Erkenntnisse aus der Graphentheorie benutzt werden, um beispielsweise den kürzesten Weg von A nach B zu finden. Oder aber die Anzahl der Wege von A nach B mit genau einem Zwischenstopp. Oder man bestimmt den längsten Weg, den ich mit dem Zug zurücklegen kann, ohne eine Station zweimal zu besuchen.

Wir wollen anhand dieses Graphen verschiedene Methoden aus der Graphentheorie vorstellen und erläutern. Als Veranschaulichung für unser graphentheoretisches Problem kann man sich ein kleines Netz von Bahnhöfen (A bis I) und Schienen dazwischen (Kanten) vorstellen.

Man kann unseren Graphen auch etwas anders darstellen, um die Anordnung der Knoten untereinander zu verdeutlichen. Jetzt versuchen wir, Wege von A nach B zu finden. In diesem Graphen gibt es verschiedene Wege, um von A nach B zu kommen, zum Beispiel ACDB, AFEB, AFEDB, AFGIB,...

Alternativ kann man auch den leichtesten Weg finden, wenn z. B. jeder Kante eine Zahl zugewiesen wird, die der Schwierigkeit des Weges entspricht. Das könnte für die Bahn zum Beispiel der Anstieg der Strecke sein. So gibt es vielleicht einen Weg von A nach B, der zwar kurz ist, bei dem der Zug aber besonders steil bergauf fahren muss. Ein anderer Weg mag zwar länger sein, aber dafür weniger steil und deshalb auch weniger schwierig. Dazu kann man den Kanten des Graphen ein unterschiedliches Gewicht zuweisen. Strecken mit großer Steigung sind schwer zu überwinden und bekommen deshalb ein hohes Gewicht, flache Strecken dafür ein geringeres Gewicht.

Hier haben wir den Kanten unseres Graphen verschiedene Gewichte zugewiesen. Die unterschiedlichen Wege von A nach B, die wir gerade gefunden haben, können wir jetzt nach ihrer Schwierigkeit, also ihrem Gewicht, beurteilen. Der Weg ACDB hat nun ein Gewicht von 3+6+5 = 14. Entsprechend findet man die Gewichte zu AFEB (11) , AFEDB (15), AFGIB (9) und so weiter.

Einige Wege, die im ungewichteten Graphen zwar kurz sind (z. B. ACDB) sind nun nicht mehr optimal, weil sie ein hohes Gewicht haben (14). Hier wäre der Weg AFGIB am leichtesten, weil er nur ein Gewicht von 9 hat.

Statt einem Gewicht kann man einer Kante auch eine Richtung zuweisen. Bei diesen sogenannten gerichteten Graphen kann man berücksichtigen, dass eine Strecke nur in eine Richtung befahrbar ist.

Wir haben hier also einigen Kanten in unserem Graphen eine Richtung zugewiesen. Der Weg AFEDB ist nun nicht mehr befahrbar, da die Kante zwischen E und D nur in die andere Richtung befahren werden kann.

Natürlich kann man diese beiden Konzepte der Richtung und Gewichtung auch kombinieren. Wenn eine Strecke in eine Richtung besonders steil ist, hat sie in diese Richtung auch ein hohes Gewicht. Die umgekehrte Richtung ist dafür aber hat wenig Gewicht, da der Zug keinen steilen Anstieg zu überwinden hat.

Wir haben in unserem Graphen nun gerichtete und gewichtete Kanten. Durch diese zwei simplen mathematischen Zuordnungen von Richtung und Gewicht ist schon ein sehr komplexer und aussagekräftiger Graph entstanden.

Trotzdem kann man noch vergleichsweise einfach Ergebnisse ablesen. Berücksichtigt man die Richtung und Gewichtung der Kanten kann man die verschiedenen Wege von A nach B bewerten.

Der optimale Weg von A nach B ist nun AFGIB mit einem Gewicht von 4+2+1+2 = 9. Jeder andere Weg (z.B. AFEB) hat ein höheres Gewicht und ist deshalb nicht optimal.

Für den Rückweg muss man einen anderen Pfad als diesen wählen, weil die Kante zwischen B und I nur in die eine Richtung verläuft.

Der optimale Weg von B nach A ist BEFA mit einem Gewicht von 3+4+1 = 9. Der einzig andere Weg BDEFA hat ein Gewicht von 12 und ist deshalb nicht optimal.

So konnte Leonhard Euler schon 1735 das Königsberger Brückenproblem betrachten und fand heraus, dass es für dieses Problem keine Lösung gibt.

Zum Weiterlesen:

Film über den berühmten Mathematiker Leonhard Euler

Kurzfilm zur Optimierung von Taktfahrplänen mit Graphentheorie.

Film N is a Number über das ungarische Mathematik-Genie Paul Erdős.

Spielfilm Good Will Hunting und die graphentheoretischen Probleme, die im Film gelöst werden.

Aus dem Buch Bilder der Mathematik: Leseproben zu Euler und Hamilton.