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 ;-)
. Je nachdem, welchen Lehrer/ Professor man hat(te), zählt manchmal auch noch die 
dazu, aber die lassen wir jetzt erstmal außen vor, die spielt eh eine Sonderrolle.
Dies ist jedoch kein “echter” Bruch – “echter Bruch? Was will der jetzt schon wieder? Zahl oben, Zahl unten, Strich dazwischen. Das ist ganz klar ein Bruch. Wo gibts da was unechtes?”. Kramt ihr nochmal ein bisschen in eurem Mathewissen, so kommt euch vielleicht der Begriff “kürzen” in den Sinn. Der Bruch ist nicht vollständig gekürzt. Also: 
. Okay, und was hat das mit Primzahlen zu tun? Zerlegung? Bei so einfachen Brüchen macht ihr das im Kopf, aber schaut euch mal 
an. Na? Mit ein bisschen überlegen kommen wir wie folgt voran: 
.
wird zu 
. Ebenso lässt sich 
zerlegen.
wird zu 
. Doch 
ist noch keine Primzahl. Dazu schauen wir uns am Besten einmal an, was eine Primzahl ausmacht:
teilen. Also wissen wir sofort, dass 
? Nein. Denn 
. Merke: Nicht jede ungerade Zahl ist eine Primzahl. Eins können wir jedoch festhalten: Alle geraden Zahlen, die größer als 
ist eine Primzahl. Also wird die 
sozusagen von der 
zum Beispiel? Kein Problem: 
. Sie wird also auch aus Primzahlen gebildet. So könnten wir immer weiter schauen, jede natürliche Zahl ist entweder eine Primzahl oder aus Primzahlen gebildet. Noch wichtiger: Für jede Zahl gibt es genau eine einzige Möglichkeit, sie aus den Primzahlen zu bilden. Abgesehen von der Reihenfolge natürlich, wie wir bei der 
und 
sind natürlich identisch.
. Die zweite enthält alle Primzahlen und die dritte enthält alle anderen Zahlen, das sind die, die zusammengesetzt sind. Die 
. Nicht sehr schön, aber schön kurz ;-) Unser 
.Wer gut aufgepasst hat, dem müsste auffallen, dass wir noch eine Zahl brauchen, denn wenn wir unser 
. Einfallsreich. Halten wir also fest: 
. Klar? Wenn 
. 
– unsere neue Zahl. Doch wie soll das gehen? Dann müsste unser 
enthält aber keine Primteiler. Wir haben also schon wieder einen Widerspruch. Somit können wir felsenfest behaupten, dass es unendlich viele Primzahlen gibt. Dieser Beweis stammt übrigens von Euklid, der um 300 v.Chr. lebte. Ist also schon ganz schön alt der Kram.
Jetzt kann man auch hier Beträge mit einem Herzchen versehen und somit Rückmeldung geben, falls man für einen Kommentar zu schüchtern ist, unter Zeitdruck steht oder einfach nur seine unkompliziert Meinung kundtun möchte. Und da Facebook eh nur Daten klaut, wird es hier auch keinen Facebook “Gefällt mir” Button geben. 
. Addieren wir diese 5 Zahlen miteinander, so erhalten wir: 
. Jetzt sollte jeder verstanden haben, was eine perfekte Zahl ist. Die kleinste perfekte Zahl ist übrigens die 6. Das zu überprüfen, sei euch überlassen ;-) Bis zum 16. Jahrhundert waren erst lediglich 5 vollkommene Zahlen bekannt. Nach und nach wurden immer mehr Zahlen dieser besonderen Bauart entdeckt. Mein Stand ist, dass es momentan 47 entdeckte vollkommene Zahlen gibt. Die letzte wurde 2008 gefunden und hat 25.956.377 Ziffern. Die ersten, die diese Eigenschaft bestimmten Zahlen zuwiesen, waren übrigens die alten Griechen.
sein). Aber rein vom wissenschaftlichen Standpunkt haben diese Zahlen, meines Wissens nach, keine besondere Auswirkung. Aber wer weiß was in Zukunft kommt, auch bei Primzahlen hat man sich lange gefragt, wofür man diese brauchen könnte, und was würden wir heute ohne diese machen?
