Nachdem mein letzter Post über Primzahlen ja durchaus positiv aufgenommen wurde, soll es heute mal um ein anderes Fachgebiet innerhalb der Mathematik gehen, welches auch gleichzeitig mein Lieblingsthemenfeld ist. Die Graphentheorie. “Theorie? Klingt öde. Schnell weg hier.”. Stop! Statt hier groß Definitionen und Sätze anzugeben, habe ich mir vorgenommen ein schönes Beispiel zu bringen, wie Graphentheorie in der Praxis angewandt wird. Und zumindest die, die Auto fahren, werden sich demnächst an einer Kreuzung an das Folgende erinnern. Darauf gestoßen bin ich durch ein Plakat bei uns an der Uni, dass dieses Beispiel erklärt, jedoch in stark verkürzter Weise.

Schauen wir uns das folgende Bild einer Kreuzung an. Ich hoffe ihr könnt erkennen, was ich meine.

Die Pfeile symbolisieren, in welche Richtung Autos auf den jeweiligen Spuren abbiegen. Wir haben Rechts- und Linksabbieger und Geradeausfahrer. Jeder weiß, dass nicht alle Autos gleichzeitig fahren können (es soll Länder geben, da soll das tagtäglich ohne Unfall passieren), aber wir nehmen jetzt mal eine typische Kreuzung. Um den Verkehr zu regeln gibt es im Normalfall Ampeln. Nehmen wir an, dass die Grünphase genau 1 Minute dauert. Das Problem beseht jetzt darin, dass man jeder Verkehrsrichtung einen Zeitintervall zuweist, in dem die Autos auf dieser Spur grünes Licht haben.

Naja, wir könnten uns jetzt denken: Die beiden Rechtsabbieger-Spuren haben immer grün, da kann nichts passieren (sieht man in der Grafik daran, dass sie keinen andere Fahrtrichtung schneiden). Und für die anderen Spuren gehen wir der Reihenfolger nach. Erst hat rot grüne Ampel für eine Minute, dann blau, dann grün, dann gelb, dann cyan, dann wieder von vorne. Bei einer Grünphase von einer Minute, dauert dann eine vollständige Ampelperiode (der Zeitraum, in dem jede Richtung einmal grün hatte) 5 Minuten. D.h. für mich als Autofahrer: Wenn ich bei grün nicht über die Ampel komme, muss ich 4 Minuten warten. Hm. Irgendwie nicht so berauschend. Schauen wir mal, ob wir da nicht was machen können.

Der erste Schritt besteht darin, dass wir uns überlegen, wie wir das Szenario auf eine andere Weise darstellen können. Wie oben schon gesagt, können wir die Rechtsabbieger vernachlässigen, die kriegen einfach einen grünen Pfeil an die Ampel geklebt und gut ist. Wir haben also 5 Fahrtrichtungen in unterschiedlichen Farben.

Jetzt kommt die Graphentheorie zum Einsatz. Wie der Name sagt, geht es um Graphen. Was ist denn überhaupt ein Graph? Naja, ein Graph aus einer Menge von Punkten (sogenannte Knoten) und Verbindungslinien (sogenannte Kanten) zwischen den Punkten (Graphentheoretiker bitte weghören ;-)). Gut, das sind die zwei wesentlichen Begriffe, die wir hier erstmal benutzen. Nicht schwierig, oder?

Und nun? Nun könnten wir zum Beispiel festlegen, dass jede Fahrtrichtung einem Knoten entspricht. Dann haben wir 5 Knoten.

Die Position der Knoten hat keine Bedeutung, man könnte sich auch beliebig anders anordnen. Ich hoffe ihr erkennt, dass die Farben den Farben aus dem Bild der Kreuzung entsprechen. Jetzt überlegen wir ein bisschen, was wir beachten müssen, bei unserer Ampelschaltung: Wir können auch mehreren Fahrtrichtungen gleichzeitig grün geben, solange sie sich nicht überschneiden. Andersherum: Wenn eine Richtung grün hat, dürfen alle anderen, die diese Richtung schneiden kein grün haben. Wie setzen wir das um? An dieser Stelle kommen die Kanten ins Spiel: Kanten starten an genau einem Knoten und enden an genau einem Knoten.

Wir verbinden jetzt jeden Knoten mit Hilfe einer Kante mit allen anderen Knoten (also Fahrtrichtungen), deren Grün-Phase sich nicht mit unserer überschneiden darf. Verstanden? Nein? Kein Problem, hier die Grafik und Erklärung:

Fangen wir mit der Fahrtrichtung “blau” an. Wenn wir in unsere Kreuzung schauen, so sehen wir, dass die blaue Linie zwei andere Linien schneidet: Die grüne und die gelbe. Das heißt, wenn blau eine Grün-Phase hat, dann dürfen gelb und grün keine Grün-Phase haben. Nach der Idee von eben, müssen wir nun den blauen Knoten einmal mit grün und einmal mit gelb verbinden. So wie es in der Skizze auch getan wurde. Schauen wir uns die gelbe Fahrtrichtung an. Sie schneidet blau und cyan. Zu blau haben wir schon eine Kante. Also noch eine von gelb zu cyan hinzufügen. Der Rest erklärt sich von alleine, denke ich mal. Wir erhalten also eine Art von “Kreis”. Wir wissen jetzt: Für Knoten, die miteinander verbunden sind, dürfen zugehörige Fahrtrichtungen nicht gleichzeitig eine Grün-Phase haben. Oder andersherum: Für Knoten, die nicht miteinander verbunden sind, dürfen die zugehörigen Fahrtrichtungen gleichzeitig grün anzeigen.

Versuchen wir doch einmal, durch eine Nummerierung festzustellen, welche Farben gleichzeitig grün haben dürfen.

Wir geben dem blauen Knoten eine 0. Schauen wir uns jetzt den gelben Knoten an. Er kann keine 0 bekommen, da in Gruppe 0 nur Fahrtrichtungen sein dürfen, die blau nicht schneiden. Dies ist für gelb aber nicht der Fall. Also bekommt der gelbe Knoten eine 1 zugeordnet. Wir machen also einfach eine neue Gruppe auf.

Schön. Weiter gehts mit dem nächsten Knoten. Cyan. Er kann keine 1 haben, denn er ist mit gelb verbunden. Kann er eine 0 haben? Ja, denn mit blau ist er nicht verbunden, also schneiden sich die beiden Fahrtrichtungen auch nicht.

Roter Knoten? Zu Gruppe 0 kann er nicht gehören. Aber zu Gruppe 1. Sehr gut. Das geht ja schön fix.

Bleibt noch der grüne Knoten. Gruppe 0? Geht nicht, er ist mit blau verbunden. Gruppe 1? Geht auch nicht, denn er ist mit rot verbunden. Bleibt uns also nichts anderes übrig, als eine neue Gruppe einzuführen. Der grüne Knoten kommt in Gruppe 2.

Sehr schön, denn jetzt sind wir eigentlich fertig. Wieso, fragt ihr euch? Naja. Wir geben zuerst den Fahrtrichtungen aus Gruppe 0 für eine Minute ein grünes Ampelsignal. Anschließend den Fahrtrichtungen aus Gruppe 1 und danach der Fahrtrichtung aus Gruppe 2. Und fangen wieder von vorne an. Graphisch aufbereitet, sieht das ganze dann so aus:

Die 0 symbolisiert den Start unserer Ampelphase. Dort kriegen blau und cyan grünes Licht. Die 1 symbolisert, dass eine Minute vergangen ist. Also wechselt die grüne Ampel bei blau und cyan auf rot und die Fahrtrichtungen gelb und rot kriegen ihre grüne Ampelphase. Nach einer weiteren Minute sind wir bei der 2 angekommen. Die Autos auf rot und gelb müssen anhalten, da die Grünphase vorbei ist und die grüne Fahrtrichtung kann befahren werden. Nach einer weiteren Minute ist auch diese Phase vorbei und alle Fahrtrichtungen hatten einmal grün – eine vollständige Ampelperiode ist vorbei. In 3 Minuten. Das sind immerhin 2 Minuten weniger als im ersten Ansatz ganz oben und bedeutet für uns Autofahrer, dass wir “nur” zwei Minuten an einer roten Ampel stehen müssen.

Man kann das ganze auch noch ein bisschen mehr optimieren, in dem man den Knoten keine ganzen Zahlen sondern rationale Zahlen zuordnet. Darauf möchte ich jetzt jedoch nicht weiter eingehen, nur soviel: Die Wartezeit kann sich dann auf 1 1/2 Minuten verkürzen.

Das was wir hier gemacht haben, nennt man in der Graphentheorie auch Knotenfärbung. Es gibt auch Kantenfärbungen, Totalfärbungen und noch andere Varianten. Ein Beispiel für eine Kantenfärbung werde ich vielleicht später noch einmal zeigen, nur soviel: Es geht darum, wie man ein Sportturnier effizient planen kann, dass bestimmte Paarungen nicht auftreten oder bestimmte Spieler nicht gleichzeitig an einem Tag spielen dürfen. Auch Stundenpläne lassen sich so erstellen (da dürfen ja keine Räume/ Lehrer doppelt vergeben werden).

Ich hoffe ich konnte euch hier ein bisschen zeigen, dass Mathematik nicht immer nur Theorie ist, sondern durchaus auch auf Probleme in der realen Welt angewandt werden kann.

Kommentare, Anmerkungen, Fragen oder Hinweise (insbesondere Rechtschreibfehler und/oder Grammatikfehler) bitte in die Kommentare. Danke ;-)