Inhalt
„Das – ist – das – Haus – vom – Niko – laus“.
Hinter diesem Zeichenspiel für Kinder verbirgt sich eine nützlichere Mathematik als man zuerst ahnen mag. Ohne den Stift anzuheben, kann das Haus nur von zwei bestimmten Punkten aus gezeichnet werden, ohne eine Linie doppelt zu zeichnen.
Eine Abwandlung von diesem Zeichenrätsel wäre das Doppelte Haus vom Nikolaus. So wird hier dem obigen Satz noch ergänzt: „und – ne – ben – an – vom – Weih – nachts – mann“. Irgendwo muss der dicke Mann ja auch hin, was? Der Nikolaus ist nämlich nicht der Weihnachtsmann, sondern war ein wohlhabender Bischof der Kirche, der vor ca. 1600 Jahren lebte und sein Geld an Arme und Kinder verteilte [Nikolaus von Myra].
Viel interessanter ist dennoch die Tatsache das wir leicht überprüfen können ob sich solche oder auch andere Häuser in einem Zug zeichnen lassen – und was uns das bringt. Um das zu verstehen müssen wir eine kurze Einführung in die Graphentheorie geben.
Grundlagen Graphentheorie
Für den Informatiker ist das was wir hier haben nämlich weniger ein Haus sondern viel mehr ein Graph. Einfach gesagt besteht ein Graph aus Knoten bzw. hier die Hausecken und Kanten also die Linien zwischen den Punkten.
Das einzige was noch wichtig ist, ist der Knotengrad. Nein das hat nichts mit Temperatur und Celsius zu tun – sondern mit der Anzahl der Kanten die von einem Knoten abgehen. Hier gehen zwei Kanten ab, also ist der Grad = 2. An dieser Ecke sind es 3 Kanten also haben wir für diese Knoten den Grad = 3.
Eulerweg
Und jetzt kommts: Wenn ein Graph genau zwei Knoten mit einem ungeraden Knotengrad besitzt, also 3, 5, 7 und so weiter, kann man ihn einem Zug zeichnen. Das nennt sich dann auch Eulerzug oder Eulerweg. Der Name stammt von seinem schweizer Entdecker und Mathematiker Leonard Euler.
Hier sind alle Knotengrade des Haus vom Nikolaus Graphen. Wie zu erwarten, sieht man das diese zwei Knoten hier einen ungeraden Knotengrad haben. Demnach lässt er sich problemlos in einem Zug zeichnen [wow, was du nicht sagst?]. Ist ja auch logisch dass wir einen Knoten mit geraden Grad immer passieren und wieder verlassen können, während man bei einen ungeraden Knoten einmal extra durch laufen muss.
Für Eulerwege gilt weiterhin, dass man in einem der beiden Punkte mit geraden Knotengrad starten und in dem jeweils anderen enden muss. Wir wissen also jetzt das wir beim Haus vom Nikolaus hier oder hier starten können und jeweils beim anderen Punkt aufhören müssen. Daraus ergeben sich by the way 44 mögliche Lösungen und 10 Möglichkeiten zu scheitern. Es gibt also eine Chance von 44 / 54, also knapp 80% das Haus korrekt zu zeichnen.
Eulerkreis
Der gute Euler hat aber noch einen speziellen Eulerweg auf Lager. Sind nämlich alle Knoten vom geraden Grad spricht man von einem Eulerkreis. Wir durchlaufen nicht nur alle Kanten in einem Wisch sondern Enden auch in dem Punkt in dem wir gestartet sind.
So etwas haben wir, wenn der Nikolaus sich noch einen Keller gönnt. Das – ist – das – Haus – vom – Niko – laus – mit Keller [Trocken]. Ich war schon immer gut darin etwas zu reimen, aber egal. Alle Knoten sind nun Gerade. Wir können dieses gepimp’te Haus nun in jedem Punkt starten und würden auch dort wieder enden. Man spricht dann auch davon dass der Graph eulersch ist.
Anwendung: Optimale Routenplanung
Nützlich kann das in der Routenplanung werden. Wenn wir überprüfen wollen, ob wir alle Straßen einer Nachbarschaft einmal abfahren können um Post auszutragen und anschließend am Ausgangspunkt wieder anzukommen. Als Graph sieht unsere Nachbarschaft so aus. Straßenecken oder Kreuzungen sind unsere Knoten und die Kanten unserer Straßen. Alle Knoten sind gerade, wir können also einen Eulerkreis finden und dafür in einem beliebigen Punkt starten
Findet man nicht auf an hieb den Eulerkreis, kann man anfangen kleine Kreise zu zeichnen. Wir beginnen also in irgendeinem Punkt und Enden auch dort wieder. Wenn wir alle Kanten dafür einmal benutzt haben, fügen wir die einzelnen Kreise zusammen. Dafür schauen wir uns an wo sich die Kreise überschneiden. Hier gehen wir nun nicht links in den roten sondern die Alternativroute in den grünen und fahren dann mit dem restlichen roten Weg ab.
Damit haben wir eine optimale Route. Zum Vergleich daneben die Route, die einige Paket Lieferdienste scheinbar nutzten…
Aber was ist eigentlich mit dem doppelten Haus vom Nikolaus? Naja, das hat mehr als zwei Knoten mit ungeraden Grad ist damit weder ein Eulerkreis noch Eulerweg und kann niemals in einem Zug gezeichnet werden…
Außer man ist ein Real Gangsta und zeichnet eine Kante einfach zwei mal…