- 0 ungerade Knoten: ein Kreis, von jedem Knoten zurück zu ihm
- 2 ungerade Knoten: ein Weg vom einen zum anderen
- 4 oder mehr: unmöglich in einem Zug
Eulerweg-Finder
Kann man das Haus vom Nikolaus zeichnen, ohne den Stift abzusetzen und ohne eine Linie doppelt zu ziehen? Ja, aber nur, wenn man an einer der beiden unteren Ecken beginnt, und von jeder gibt es 44 Möglichkeiten. Der Grund ist der Grad eines Knotens, die Zahl der Linien, die sich dort treffen: Jedes Mal, wenn der Stift durch einen Knoten läuft, verbraucht er zwei seiner Linien. Leonhard Euler fand diese Regel 1736 an den sieben Brücken von Königsberg. Zeichnen Sie eine Figur selbst nach, sehen Sie, wo und warum Sie stecken bleiben, holen Sie sich einen Tipp, oder sehen Sie einem Algorithmus beim Zeichnen zu. Wählen Sie eine Figur und zeichnen Sie sie nach: Tippen Sie auf einen Knoten, um zu beginnen, dann der Reihe nach auf die Kanten oder die nächsten Knoten, oder ziehen Sie von Knoten zu Knoten. Jede Kante darf nur einmal benutzt werden. Zurück nimmt einen Schritt zurück, Tipp zeigt die nächste sichere Kante, und Lösen spielt den Algorithmus von Fleury oder von Hierholzer Schritt für Schritt ab. Ungerade Knoten sind gefüllt, und die Marke an jedem Knoten ist sein Grad. Unter Zeichnen fügt ein Tippen auf eine freie Stelle einen Knoten hinzu, und ein Tippen auf zwei Knoten verbindet sie, ein weiteres Mal mit einer zweiten Kante; ziehen Sie einen Knoten, um ihn zu verschieben. Löschen entfernt Knoten und Kanten. Sind mehr als zwei Knoten ungerade, setzt Hinzufügen die Kanten ein, mit denen sich die Figur zeichnen lässt.
Wie es funktioniert
- Wählen Sie eine Figur, etwa die sieben Brücken von Königsberg, das Haus vom Nikolaus oder einen Stern, oder zeichnen Sie unter Zeichnen Ihre eigene, mit beliebig vielen Kanten zwischen zwei Knoten.
- Tippen Sie auf einen Knoten, um zu beginnen, dann der Reihe nach auf die Kanten oder Knoten, oder ziehen Sie von Knoten zu Knoten. Wenn Sie stecken bleiben, sagt die Statuszeile, warum; Zurück nimmt einen Schritt zurück, und Tipp zeigt eine sichere nächste Kante.
- Lesen Sie die Gradregel unter der Figur, fügen Sie einer unmöglichen Figur die vorgeschlagenen Kanten hinzu, oder drücken Sie Lösen und sehen Sie zu, wie der Algorithmus von Fleury oder von Hierholzer sie Schritt für Schritt zeichnet.
Warum die ungeraden Knoten entscheiden
Ein Zug, der durch einen Knoten läuft, kommt über eine Linie an und geht über eine andere weiter, er verbraucht die Linien an diesem Knoten also paarweise. Nur dort, wo der Zug beginnt oder endet, kann eine Linie ohne Partner bleiben. Ein Knoten mit ungerade vielen Linien muss deshalb Anfang oder Ende sein. Ohne ungeraden Knoten endet der Zug, wo er begann: ein Eulerkreis. Mit zweien läuft er vom einen zum anderen: ein Eulerweg. Mit vier oder mehr gibt es zu viele Enden für einen Zug, und k ungerade Knoten brauchen k/2 Züge. Königsberg hatte vier Landstücke mit fünf, drei, drei und drei Brücken: alle vier ungerade, also konnte kein Spaziergang jede Brücke genau einmal überqueren. Eine neue Brücke zwischen zweien von ihnen hätte den Spaziergang möglich gemacht.
Die Algorithmen von Fleury und Hierholzer
Zu wissen, dass sich eine Figur zeichnen lässt, heißt noch nicht, sie zu zeichnen: Ein unbedachter Zug kann sich von den Linien abschneiden, die er noch braucht. Der Algorithmus von Fleury aus dem Jahr 1883 verhindert das mit einer Regel: Überquere nie eine Brücke, also eine Linie, deren Wegfall die übrigen Linien in zwei Teile trennt, außer es gibt keine andere Linie. Der Algorithmus von Hierholzer, aus einer 1873 erschienenen Arbeit, ist schneller: Gehe irgendwohin, bis es nicht mehr weitergeht, was nur am Start passieren kann, gehe dann von einem Knoten der Tour, der noch freie Linien hat, eine weitere geschlossene Schleife und füge sie in die Tour ein. Seine Laufzeit wächst proportional zur Zahl der Kanten, und so finden Computer Eulerwege.
Häufig gestellte Fragen
Was ist der Unterschied zwischen einem Eulerweg und einem Eulerkreis?
Beide benutzen jede Kante eines Graphen genau einmal. Ein Eulerkreis endet dort, wo er begonnen hat; ein Eulerweg endet woanders. Ein zusammenhängender Graph hat einen Eulerkreis, wenn jeder Knoten geraden Grad hat, und einen Eulerweg, wenn genau zwei Knoten ungeraden Grad haben; der Weg läuft dann vom einen zum anderen.
Warum kann man die sieben Brücken von Königsberg nicht je einmal überqueren?
Zeichnen Sie jedes Landstück als Knoten und jede Brücke als Kante. Die Insel Kneiphof hatte fünf Brücken, die anderen drei Landstücke je drei, also sind alle vier Knoten ungerade. Ein Spaziergang kann nur an einem ungeraden Knoten beginnen oder enden, und vier sind zu viele. Eine zusätzliche Brücke zwischen zweien von ihnen lässt zwei ungerade Knoten übrig, und der Spaziergang wird möglich.
Wie viele Möglichkeiten gibt es, das Haus vom Nikolaus zu zeichnen?
44 von jeder der beiden unteren Ecken, zusammen 88, wenn eine andere Reihenfolge oder Richtung als andere Möglichkeit zählt. Von jedem anderen Knoten aus geht es nicht, denn die unteren Ecken sind die einzigen beiden mit ungerade vielen Linien. Die App zählt die Möglichkeiten kleiner Figuren auf diese Weise.
Was ist eine Brücke in einem Graphen?
Eine Kante, deren Wegfall einen zusammenhängenden Graphen in zwei Teile trennt. Der Algorithmus von Fleury überquert nie eine Brücke der noch übrigen Kanten, solange er eine andere Wahl hat, denn sonst bliebe ein Teil der Figur zurück. In dieser App erfährt ein Zug, der nach einer zu früh überquerten Brücke stecken bleibt, welcher Schritt es war.
Kann es mehr als eine Kante zwischen zwei Knoten geben?
Ja. Ein Graph mit parallelen Kanten heißt Multigraph, und Königsberg braucht einen: Zwei Brücken verbanden den Kneiphof mit jedem Ufer. Tippen Sie unter Zeichnen noch einmal auf zwei Knoten, um eine weitere Kante zwischen ihnen hinzuzufügen, bis zu vier. Die Gradregel gilt unverändert und zählt jede Kante.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor