Eulerwege und Eulerkreise erklärt
Manche Figuren lassen sich in einem Zug zeichnen, ohne den Stift abzusetzen und ohne eine Linie doppelt zu ziehen, andere nicht, so lange man es auch versucht. Man muss es gar nicht versuchen: Zählen Sie die Linien an jeder Ecke. Haben höchstens zwei Ecken ungerade viele Linien, lässt sich die Figur zeichnen, und an diesen Ecken muss der Zug beginnen und enden. Leonhard Euler fand diese Regel 1736 und begründete damit die Graphentheorie.
Die sieben Brücken von Königsberg
Die preußische Stadt Königsberg, heute Kaliningrad, lag an beiden Ufern des Pregels und auf zwei Inseln darin, dem Kneiphof und der Lomse. Sieben Brücken verbanden die vier Teile: je zwei vom Kneiphof zu jedem Ufer, eine zwischen den beiden Inseln und je eine von der Lomse zu jedem Ufer. Die Bürger fragten sich, ob ein Spaziergang jede Brücke genau einmal überqueren könne. Euler antwortete in einer Arbeit, die er 1735 der Akademie in Sankt Petersburg vorlegte und die 1741 gedruckt wurde: Es geht nicht. Sein entscheidender Schritt war, alles wegzulassen außer den Stadtteilen und den Brücken dazwischen, und genau das tut ein Graph: ein Knoten für jedes Landstück und eine Kante für jede Brücke, mit zwei Kanten, wo zwei Brücken dieselben Teile verbinden.
Die Gradregel
Der Grad eines Knotens ist die Zahl der Kanten an ihm. Ein Zug, der durch einen Knoten läuft, kommt über eine Kante herein und geht über eine andere hinaus, er verbraucht die Kanten dieses Knotens also paarweise. Nur der erste und der letzte Knoten des Zuges können eine Kante ohne Partner behalten. Ein Knoten mit ungeradem Grad muss deshalb Anfang oder Ende des Zuges sein. Der Kneiphof hatte fünf Brücken, die anderen drei Teile je drei: vier ungerade Knoten, zwei zu viel. Allgemein hat ein zusammenhängender Graph einen Eulerkreis, einen Zug, der dort endet, wo er begann, wenn jeder Grad gerade ist, und einen Eulerweg, wenn genau zwei Grade ungerade sind, vom einen zum anderen. Die Zahl der ungeraden Knoten ist nie eins oder eine andere ungerade Zahl: Jede Kante erhöht die Summe aller Grade um 2, also ist die Summe gerade. Auch das bemerkte Euler, und es heißt heute Handschlaglemma.
Warum die Regel ausreicht
Euler zeigte, dass sich eine Figur mit mehr als zwei ungeraden Knoten nicht zeichnen lässt, und behauptete ohne Beweis, dass es bei jeder anderen zusammenhängenden Figur geht. Den Beweis lieferte Carl Hierholzer, ein deutscher Mathematiker, der 1871 jung starb; seine Arbeit erschien 1873. Beginnen Sie an einem ungeraden Knoten, falls es einen gibt, sonst irgendwo, und gehen Sie über unbenutzte Kanten, solange es geht. Weil jeder andere Knoten geraden Grad hat, kann man nur am Endknoten stecken bleiben. Sind noch Kanten übrig, berühren einige von ihnen den bisherigen Weg, denn die Figur ist zusammenhängend. Gehen Sie von einem solchen Knoten erneut los, bis es nicht weitergeht, was nun wieder an diesem Knoten geschieht, und fügen Sie die Schleife dort in den Weg ein. Wiederholen Sie das, bis keine Kante übrig ist. Der Beweis ist zugleich der schnellste Algorithmus: Jede Kante wird nur eine feste Zahl von Malen angesehen.
Der Algorithmus von Fleury: Brücken nicht abbrechen
Ein Zug kann auch bei einer Figur scheitern, die sich zeichnen lässt. Nehmen Sie zwei Dreiecke, die eine einzelne Kante verbindet, und beginnen Sie an einer Ecke des ersten: Wechseln Sie ins zweite Dreieck, bevor das erste fertig ist, kommen Sie nie zurück. Die verbindende Kante ist eine Brücke: Entfernt man sie, zerfällt die Figur in zwei Teile. Der Algorithmus von Fleury aus dem Jahr 1883 gibt eine Regel: Nimm an jedem Knoten eine Kante, die keine Brücke der noch übrigen Kanten ist, außer es gibt keine andere. Wer ihr folgt, wird immer fertig. Der Brückentest kostet Zeit, deshalb ist Fleurys Algorithmus langsamer als der von Hierholzer, aber er ist der, dem man mit dem Stift folgen kann, und der Tipp in der App benutzt ihn.
Eine Figur reparieren
Eine Figur mit k ungeraden Knoten braucht k/2 Züge. Um sie in einem zu zeichnen, fügt man Kanten hinzu, die ungerade Knoten paarweise verbinden: Jede neue Kante macht zwei ungerade Knoten gerade. Mit k/2 − 1 Kanten bleiben zwei ungerade Knoten und es entsteht ein Weg; mit k/2 bleibt keiner und es entsteht ein Kreis. Eine weitere Brücke in Königsberg, zwischen zwei beliebigen der vier Teile, hätte den Spaziergang möglich gemacht, zwei einen Rundgang. Die Geschichte tat etwas Ähnliches: Zwei Brücken gingen im Zweiten Weltkrieg verloren, zwei wurden durch eine moderne Straße ersetzt, und die fünf Brücken an den alten Stellen lassen sich heute je einmal überqueren, von einer Insel zur anderen.
Die Möglichkeiten zählen
Das Haus vom Nikolaus, ein Quadrat mit beiden Diagonalen und einem Dach, ist die Kinderversion des Rätsels: „Das ist das Haus vom Ni-ko-laus“ hat acht Silben, eine für jeden Strich. Seine beiden unteren Ecken sind die einzigen ungeraden Knoten, und von jeder gibt es genau 44 Möglichkeiten, es zu zeichnen, zusammen 88. Für gerichtete Graphen gibt es eine Formel für die Zahl der Eulerkreise, das BEST-Theorem, benannt nach de Bruijn, van Aardenne-Ehrenfest, Smith und Tutte. Für gewöhnliche Graphen ist keine solche Formel bekannt, und das Zählen gilt im Allgemeinen als schwer, deshalb zählt die App kleine Figuren, indem sie jede Möglichkeit ausprobiert und Schritte überspringt, die die Figur in zwei Teile trennen würden.
Wo Eulerwege gebraucht werden
Ein Schneepflug, eine Kehrmaschine oder ein Briefträger will jede Straße einmal abfahren und zurückkehren. Hat jede Kreuzung eine gerade Zahl von Straßen, leistet das ein Eulerkreis; sonst müssen einige Straßen doppelt gefahren werden, und die günstigsten auszuwählen ist das Briefträgerproblem, das Meigu Guan 1962 stellte. Ein Stiftplotter oder ein Laserschneider spart Zeit, wenn er möglichst viele Linien ohne Absetzen zieht. Bei der Genomsequenzierung werden Millionen kurzer DNA-Stücke zusammengesetzt, indem man einen Eulerweg durch einen De-Bruijn-Graphen sucht, in dem jedes Stück eine Kante ist. Und dieselbe Regel verrät, welche Strichzeichnungen in einem Rätselheft einen Versuch wert sind.
Ausprobieren
Öffnen Sie den Eulerweg-Finder und zeichnen Sie zwölf Figuren selbst nach, von Königsberg 1736 und heute bis zu Sternen, verschachtelten Quadraten und einem Würfel, oder zeichnen Sie eigene mit parallelen Kanten. Die ungeraden Knoten sind gefüllt, jeder Knoten zeigt seinen Grad, und die Gradregel unter der Figur sagt, was möglich ist und welche Kanten die Figur reparieren würden. Wenn Sie stecken bleiben, sagt die App, ob Sie am falschen Knoten begonnen oder zu früh eine Brücke überquert haben, und in welchem Schritt. Tipp nennt eine sichere nächste Kante, und Lösen zeichnet die Figur mit dem Algorithmus von Fleury, mit Brückentest, oder mit dem von Hierholzer, mit jeder eingefügten Teiltour.
Häufig gestellte Fragen
Ist ein Eulerweg dasselbe wie ein Hamiltonweg?
Nein. Ein Eulerweg benutzt jede Kante einmal und darf einen Knoten mehrmals besuchen; ein Hamiltonweg besucht jeden Knoten einmal und muss nicht jede Kante benutzen. Ob ein Graph einen Eulerweg hat, beantwortet das Zählen der ungeraden Knoten sofort, für Hamiltonwege aber ist kein schneller Test bekannt, und einen zu finden ist eines der klassischen schweren Probleme der Informatik.
Gilt die Gradregel, wenn zwei Knoten durch mehr als eine Kante verbunden sind?
Ja. Jede Kante zählt zum Grad ihrer beiden Enden, ob nun eine weitere Kante dieselben Knoten verbindet oder nicht. Königsberg ist ein solcher Multigraph, mit zwei Brücken vom Kneiphof zu jedem Ufer. Eine Kante von einem Knoten zu sich selbst, eine Schlinge, erhöht seinen Grad um 2 und ändert nie, ob er ungerade ist.
Und bei Einbahnstraßen?
In einem gerichteten Graphen hat jede Kante eine Richtung, und die Regel vergleicht die Kanten, die in einen Knoten hinein- und aus ihm herausführen. Es gibt einen Eulerkreis, wenn bei jedem Knoten gleich viele Kanten hinein- wie herausführen und die Kanten zusammenhängen, und einen Eulerweg, wenn ein Knoten eine Kante mehr hinaus als hinein hat, einer eine mehr hinein als hinaus und alle anderen ausgeglichen sind. Der Weg läuft dann vom ersten zum zweiten.
Kann es eine Figur mit genau einem ungeraden Knoten geben?
Nein. Die Grade aller Knoten ergeben zusammen das Doppelte der Kantenzahl, weil jede Kante zwei Enden hat. Diese Summe ist gerade, also muss auch die Zahl der ungeraden Grade darin gerade sein: 0, 2, 4 und so weiter, nie 1 oder 3.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Den Eulerweg-Finder öffnen