Open the Spider Web animation to watch a web grow thread by thread. The inspiration to this app was by my daughter who asked me when we were watching my turtle graphics demos if we can also watch the spider building her web, so we “vibe-coded” this “web-app” :-) together. I also found it a nice illustration of Euler tours: closed walks that traverse every edge of a graph exactly once. This is like drawing the graph without lifting the pen or retracing an edge, and finishing where you started.
The resulting Python program has 477 lines of code. Press Run to watch our spider work after choosing some parameters of the web, and also you may let her apply Hierholzer’s algorithm to create a twice reinforced web. An orb web has a broadly wheel-like shape. Its hub is the central working area; its spokes, also called radii, extend towards the supporting frame. The animation is a simplified construction model. Real spiders adapt their movements and web geometry to their surroundings.
The construction algorithm
A typical orb-web construction can be described as a sequence of manageable tasks. The British Arachnological Society’s construction guide explains the bridge, frame and radial stages.
- Establish supports. Span a gap with a bridge thread, strengthen it, and establish an initial framework and hub.
- Build the frame and spokes. Add outer support lines and radial threads between the hub and frame, returning along existing threads when needed. Then make a small strengthening spiral around the hub.
- Lay a temporary spiral outwards. Move around the hub while gradually increasing the distance from it. This widely spaced, non-sticky spiral provides scaffolding.
- Lay the capture spiral inwards. Start near the outside and work towards the hub, attaching a more closely spaced capture thread to successive spokes.
- Remove the temporary spiral as construction proceeds. The finished capture spiral takes over its role. In many familiar orb webs the capture thread is sticky; the supporting frame and spokes are dry silk.
- Finish near the hub. The completed network is ready to intercept prey.
The simulator first builds the temporary spiral outwards, then uses this local rule for the inward capture spiral. It remembers the previous attachment u[j] on each spoke: 0 means the hub and 1 the frame. Here, n is the number of spokes, mean_radius their average length, and spacing the desired distance between turns. A seeded random variation makes the result repeatable. The spider’s body may walk along an existing spoke or guide while new silk spans the sector between attachment points.
u = [1.0] * nu[i] = 0.98 # i is the current spokerepeat at most 60*n times: j = (i - 1) mod n variation = seeded_uniform(0.94, 1.06) u_new = u[j] - (spacing / mean_radius) * variation if u_new < 0.15: stop # leave the central hub clear attach new silk at position u_new on spoke j remove temporary guide silk passed by the capture front u[j] = u_new i = j
The Australian Museum’s account of spider webs describes the temporary spiral’s removal during capture-spiral construction. These stages are a useful algorithmic outline, but their order is flexible: Corver and colleagues’ observations of web-building (2021) include spiders interrupting and repeating stages.
An ideal web that we can count
For the mathematics, use a separate, perfectly regular model: replace the spiral by closed rings. These counts describe that ideal graph, rather than the exact threads in the animated web.
Choose integers n ≥ 3 and k ≥ 1. Define G(n, k) by placing one hub vertex at the centre and n equally spaced vertices on each of k concentric rings. Join neighbours around each ring, join corresponding vertices on neighbouring rings, and connect the hub to all vertices of the innermost ring. Each complete spoke is a chain of k edges.
A vertex is a junction, an edge connects two neighbouring junctions, and a face is a region of the plane drawing. Count the unbounded outside region as a face too.
- V = 1 + nk vertices: one hub plus n vertices on each ring.
- E = 2nk edges: nk ring edges plus nk radial edges.
- F = nk + 1 faces: n inner triangles, n(k − 1) quadrilateral regions between rings, and the outside face.
Thus V − E + F = 2, Euler’s formula for a connected plane graph. For example, eight spokes and five rings give 41 vertices, 80 edges and 41 faces; 40 of those faces are bounded. UC Davis’s graph-theory notes explain why the outside face belongs in Euler’s formula.
Build the graph recursively
Start with G(n, 1): one ring joined to the hub, a wheel graph. To obtain G(n, k + 1), add an outer ring of n new vertices, join its neighbours with n edges, and add n radial connections to the previous ring.
Each step adds n vertices, 2n edges and n faces. In recurrence form: V(k + 1) = V(k) + n, E(k + 1) = E(k) + 2n, and F(k + 1) = F(k) + n, starting from V(1) = n + 1, E(1) = 2n, and F(1) = n + 1. This proves the counting formulas by induction. A program can implement the same recursive construction with a loop that adds one ring at a time.
Rotations and orbits
Rotate this ideal web by 360°/n, or 2π/n radians. Repeating the rotation generates the cyclic group Cₙ and preserves the graph. The orbit of a vertex is the set of positions it reaches under these rotations: each ring gives one orbit of n vertices, while the hub gives an orbit containing only itself. There are therefore k + 1 vertex orbits. This is the group-action meaning of orbit used in Cornell algebra course notes, Definition 1.1.2.
Here, “orbit” describes symmetry; “orb web” names a kind of web. An irregular web or a single spiral generally does not have this exact rotational symmetry.
Can every thread be traversed exactly once?
An Euler trail, often called an Euler path, traverses every edge exactly once (it is a classic of graph theory and is connected with Euler’s famous question whether he can have non-repeating walk around the 7 bridges of Königsberg); it may revisit vertices. An Euler circuit also returns to its starting vertex. In a connected undirected graph, a circuit exists exactly when every vertex has even degree, and an open Euler trail exists exactly when two vertices have odd degree. At each internal vertex, arrivals and departures pair up, so its degree must be even. Only the two distinct endpoints of an open Euler trail have an unpaired incidence and hence odd degree. These criteria are explained in the UC Davis notes on Euler paths and cycles.
In G(n, k), the hub has degree n, each outer-ring vertex has degree 3, and every other vertex has degree 4. There are therefore n odd-degree vertices if n is even, or n + 1 if n is odd. For n ≥ 3, that is at least four, so this ideal graph has no Euler trail. A continuous walk covering all its edges must retrace some edge.
However, if the spider decides to reinforce every link by putting exactly two silk strings on it she can make use of Hierholzer’s algorithm. Doubling every edge is a separate preparation step: it makes every vertex degree even. The resulting connected multigraph therefore has an Euler circuit, which Hierholzer’s algorithm finds. In the app, you can choose Explore maths, then Trace walk to watch the spider produce this twice reinforced graph. Real spiders probably don’t know Hierholzer’s algorithm—unless they watched and listened from their webs as he presented his idea to his mathematician friends :-).
Hierholzer’s algorithm: step by step, with a short proof
The problem. An Euler trail uses every edge exactly once; vertices may be visited repeatedly. It is an Euler circuit if it ends where it starts. Consider a finite undirected graph whose vertices incident with edges form one connected component. A circuit exists when all degrees are even; an open trail exists when exactly two degrees are odd. A loop contributes two to its vertex’s degree, and parallel edges count separately.
- Choose the starting vertex. For a circuit, choose any vertex incident with an edge. Mark all edges as unused.
- Build a first closed trail. Follow any unused incident edge, marking it used, and continue until the current vertex has no unused edge. With all degrees even, this maximal trail ends at its starting vertex.
- Find an attachment point. If unused edges remain, find a vertex on the current trail that has an unused incident edge.
- Build and insert a closed detour. Starting there, follow unused edges until stuck. The detour returns to the same vertex. Insert its edge sequence at that occurrence of the vertex in the current trail. The detour need not be a simple cycle: it may revisit vertices.
- Repeat. Continue inserting closed detours until every edge has been used. The resulting sequence is an Euler circuit.
- Handle two odd vertices. If only s and t have odd degree, add one uniquely marked auxiliary edge between them, allowing a parallel edge if necessary. Run the circuit algorithm, then cut the resulting cyclic sequence at the auxiliary edge and remove that edge. What remains is an open Euler trail from s to t, or in the reverse direction.
Why it works. At any vertex other than the start, arrivals and departures use edges in pairs. If the trail is currently at such a vertex, it has used an odd number of edge incidences there (counting a loop twice); an even original degree therefore leaves an unused exit. It can get stuck only at the start, so the first trail is closed. Removing the edges of a closed trail leaves even residual degrees. Thus every later detour is also closed. Inserting a closed detour preserves continuity and does not repeat an edge, because it uses only unused edges. If any edge is still unused, connectedness guarantees a vertex of the current trail incident with unused edges. Each insertion consumes at least one new edge, so the process terminates after finitely many insertions and covers every edge. For the open case, the auxiliary edge makes both odd degrees even; removing it from the computed circuit gives the required trail. Conversely, pairing arrivals with departures shows why only the two endpoints of an open trail may have odd degree.
The house in the pictures. In the Haus vom Nikolaus, A and B are the two odd vertices; the crossing of the diagonals is not a vertex. The open-trail variant first finds A-B-C-D-B, then inserts the remaining closed detour D-A-C-E-D at D. This gives A-B-C-D-A-C-E-D-B, using all eight edges exactly once. No edge needs to be doubled.
From the idea to an efficient program. A stack stores unfinished visits to vertices; vertices are added to an output list when they have no unused incident edge. Reverse that list at the end. With adjacency lists, distinct edge IDs and used-edge flags, the running time and storage are O(|V| + |E|). Popping a stack is bookkeeping, not physically walking back along an already drawn edge. The PDF below includes precise pseudocode, a fuller correctness argument and a Python implementation.
Connection to the spider. Doubling every edge is a separate preparation step that makes the connected web graph Eulerian. Hierholzer’s algorithm then finds a circuit in that multigraph; it does not itself double edges or minimize the amount of retracing. In the original web, the two copies correspond to two traversals of each thread.
For the interested reader: Read or download the detailed technical note (PDF, English and German). Ten pages with the full explanation, correctness proof, pseudocode, Python code and references. Michael Emmerich, University of Jyväskylä, 17 October 2026; A4, 12-point text.
Reference for Hierholzer’s algorithm: C. Hierholzer & Chr. Wiener (1873). Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6, 30–32. (Original paper in German.) Wiener’s introductory note explains that, after Hierholzer’s death, he reconstructed the oral presentation from memory with Lüroth’s help, as no written record was available.
Choose your updates: Select Mathematical Playground, Nature Photography, Multiobjective Optimization, or any combination. Choose All content to receive everything. :-)
On the next page, select Michael Emmerich (emmerix.net), then choose your categories. If you do not use a WordPress login, request a personal management link by email using the address you subscribed with.
Wie baut eine Spinne ihr Netz? Simulation und Hierholzer’s Algorithmus
Öffne die Spider-Web-Animation und beobachte, wie ein Netz Faden für Faden entsteht. Die Idee zu dieser App kam von meiner Tochter: Als wir uns meine Turtle-Grafik-Demos anschauten, fragte sie, ob wir auch einer Spinne beim Bau ihres Netzes zusehen könnten. Also haben wir diese „Web-App“ gemeinsam per „Vibe-Coding“ programmiert :-). Ich fand es außerdem ein schönes Beispiel für Eulertouren: geschlossene Kantenzüge, die jede Kante eines Graphen genau einmal durchlaufen. Anschaulich zeichnet man den Graphen, ohne den Stift abzusetzen oder eine Kante erneut nachzuzeichnen, und kehrt dabei zum Ausgangspunkt zurück.
Das entstandene Python-Programm umfasst 477 Codezeilen. Wähle einige Parameter für das Netz und drücke Run, um unserer Spinne bei der Arbeit zuzusehen. Du kannst sie auch den Algorithmus von Hierholzer anwenden lassen, um ein doppelt verstärktes Netz zu bauen. Ein Radnetz hat eine annähernd radförmige Gestalt. Seine Nabe ist der zentrale Arbeitsbereich; die Speichen, auch Radien genannt, führen zum tragenden Rahmen. Die Animation zeigt ein vereinfachtes Baumodell. Echte Spinnen passen ihre Bewegungen und die Geometrie ihres Netzes an ihre Umgebung an.
Der Baualgorithmus
Der typische Bau eines Radnetzes lässt sich als Folge überschaubarer Aufgaben beschreiben. Die Beschreibung des Netzbaus der British Arachnological Society erläutert, wie Brückenfaden, Rahmen und Radien entstehen.
- Verankerungen schaffen. Eine Lücke mit einem Brückenfaden überspannen, diesen verstärken und ein erstes Gerüst mit einer Nabe anlegen.
- Rahmen und Speichen bauen. Äußere Tragefäden und Radialfäden zwischen Nabe und Rahmen ergänzen und bei Bedarf auf bereits vorhandenen Fäden zurücklaufen. Anschließend eine kleine Verstärkungsspirale um die Nabe anlegen.
- Eine Hilfsspirale nach außen legen. Die Nabe umrunden und dabei den Abstand zu ihr allmählich vergrößern. Diese nicht klebrige Spirale mit großen Abständen zwischen den Windungen dient als Baugerüst.
- Die Fangspirale nach innen legen. Nahe am äußeren Rand beginnen und sich zur Nabe vorarbeiten. Dabei einen Fangfaden mit engeren Windungen nacheinander an den Speichen befestigen.
- Die Hilfsspirale während des weiteren Baus entfernen. Die fertige Fangspirale übernimmt ihre Aufgabe. Bei vielen bekannten Radnetzen ist der Fangfaden klebrig; der tragende Rahmen und die Speichen bestehen aus trockener Seide.
- Den Bau nahe der Nabe abschließen. Das fertige Netz ist bereit, Beute abzufangen.
Der Simulator baut zunächst die Hilfsspirale nach außen. Für die nach innen verlaufende Fangspirale verwendet er anschließend die folgende lokale Regel. Er merkt sich die vorherige Befestigung u[j] auf jeder Speiche: 0 steht für die Nabe und 1 für den Rahmen. Dabei ist n die Anzahl der Speichen, mean_radius ihre mittlere Länge und spacing der gewünschte Abstand zwischen den Windungen. Eine Zufallsvariation mit festgelegtem Startwert macht das Ergebnis reproduzierbar. Die Spinne kann auf einer vorhandenen Speiche oder einem Hilfsfaden laufen, während neue Seide den Sektor zwischen den Befestigungspunkten überspannt.
u = [1.0] * nu[i] = 0.98 # i ist die aktuelle Speichewiederhole höchstens 60*n Mal: j = (i - 1) mod n variation = seeded_uniform(0.94, 1.06) u_new = u[j] - (spacing / mean_radius) * variation falls u_new < 0.15: beenden # die zentrale Nabe frei lassen befestige neue Seide an Position u_new auf Speiche j entferne Hilfsfäden, die die Fangspirale bereits passiert hat u[j] = u_new i = j
Die Darstellung der Spinnennetze des Australian Museum beschreibt, wie die Hilfsspirale beim Bau der Fangspirale entfernt wird. Diese Phasen geben einen nützlichen algorithmischen Überblick, doch ihre Reihenfolge ist flexibel: Bei den Beobachtungen des Netzbaus durch Corver und Kollegen (2021) unterbrachen Spinnen einzelne Phasen und wiederholten sie.
Ein ideales Netz, das wir abzählen können
Für die Mathematik verwenden wir ein eigenes, vollkommen regelmäßiges Modell: Wir ersetzen die Spirale durch geschlossene Ringe. Die folgenden Anzahlen beschreiben diesen idealen Graphen, nicht die genaue Zahl der Fäden im animierten Netz.
Wir wählen ganze Zahlen n ≥ 3 und k ≥ 1. Wir definieren G(n, k), indem wir einen Nabenknoten im Mittelpunkt und auf jedem von k konzentrischen Ringen jeweils n gleichmäßig verteilte Knoten platzieren. Wir verbinden die Nachbarn auf jedem Ring, die entsprechenden Knoten benachbarter Ringe und die Nabe mit allen Knoten des innersten Rings. Jede vollständige Speiche ist eine Kette aus k Kanten.
Ein Knoten ist ein Verbindungspunkt, eine Kante verbindet zwei benachbarte Verbindungspunkte, und eine Fläche ist ein Gebiet der ebenen Zeichnung. Das unbeschränkte äußere Gebiet zählt ebenfalls als Fläche.
- V = 1 + nk Knoten: eine Nabe und n Knoten auf jedem Ring.
- E = 2nk Kanten: nk Ringkanten und nk radiale Kanten.
- F = nk + 1 Flächen: n innere Dreiecke, n(k − 1) viereckige Gebiete zwischen den Ringen und die äußere Fläche.
Damit gilt V − E + F = 2, die Eulersche Formel für einen zusammenhängenden, in die Ebene eingebetteten Graphen. Acht Speichen und fünf Ringe ergeben beispielsweise 41 Knoten, 80 Kanten und 41 Flächen; 40 dieser Flächen sind beschränkt. Die Graphentheorie-Notizen der UC Davis erklären, warum die äußere Fläche in der Eulerschen Formel mitgezählt wird.
Den Graphen rekursiv aufbauen
Wir beginnen mit G(n, 1): einem Ring, dessen Knoten mit der Nabe verbunden sind, also einem Radgraphen. Um G(n, k + 1) zu erhalten, fügen wir einen äußeren Ring mit n neuen Knoten hinzu, verbinden seine Nachbarn durch n Kanten und ergänzen n radiale Verbindungen zum vorherigen Ring.
Jeder Schritt fügt n Knoten, 2n Kanten und n Flächen hinzu. Als Rekursionsgleichungen geschrieben: V(k + 1) = V(k) + n, E(k + 1) = E(k) + 2n und F(k + 1) = F(k) + n, mit den Anfangswerten V(1) = n + 1, E(1) = 2n und F(1) = n + 1. Damit lassen sich die Zählformeln durch Induktion beweisen. Ein Programm kann denselben rekursiven Aufbau auch mit einer Schleife umsetzen, die jeweils einen Ring hinzufügt.
Drehungen und Orbits
Wir drehen dieses ideale Netz um 360°/n, also um 2π/n Radiant. Die wiederholte Anwendung dieser Drehung erzeugt die zyklische Gruppe Cₙ und erhält den Graphen. Der Orbit eines Knotens ist die Menge der Positionen, die er durch diese Drehungen erreicht: Jeder Ring bildet einen Orbit aus n Knoten, während der Orbit der Nabe nur die Nabe selbst enthält. Insgesamt gibt es also k + 1 Knotenorbits. Dies ist die Bedeutung von Orbit bei einer Gruppenwirkung, wie sie in den Algebra-Vorlesungsnotizen der Cornell University, Definition 1.1.2, verwendet wird.
Hier beschreibt „Orbit“ eine Symmetrie; der englische Ausdruck „orb web“ bezeichnet dagegen eine Art von Spinnennetz, das Radnetz. Ein unregelmäßiges Netz oder eine einzelne Spirale besitzt im Allgemeinen nicht diese exakte Drehsymmetrie.
Lässt sich jeder Faden genau einmal durchlaufen?
Ein Eulerzug, oft auch Eulerweg genannt, durchläuft jede Kante genau einmal. Er ist ein Klassiker der Graphentheorie und hängt mit Eulers berühmter Frage zusammen, ob ein Spaziergang über die sieben Brücken von Königsberg möglich ist, ohne eine Brücke erneut zu überqueren. Knoten dürfen dabei mehrfach besucht werden. Ein Eulerkreis kehrt außerdem zum Ausgangsknoten zurück. In einem zusammenhängenden ungerichteten Graphen existiert ein solcher Kreis genau dann, wenn jeder Knoten einen geraden Grad hat; ein offener Eulerzug existiert genau dann, wenn zwei Knoten einen ungeraden Grad haben. An jedem inneren Knoten lassen sich Ankunft und Abgang paaren; sein Grad muss deshalb gerade sein. Nur an den beiden verschiedenen Endknoten eines offenen Eulerzugs bleibt jeweils eine ungepaarte Inzidenz übrig, sodass ihr Grad ungerade ist. Diese Kriterien werden in den Notizen der UC Davis zu Eulerwegen und Eulerkreisen erläutert.
In G(n, k) hat die Nabe den Grad n, jeder Knoten des äußeren Rings den Grad 3 und jeder andere Knoten den Grad 4. Es gibt daher n Knoten ungeraden Grades, wenn n gerade ist, beziehungsweise n + 1, wenn n ungerade ist. Für n ≥ 3 sind das mindestens vier, also besitzt dieser ideale Graph keinen Eulerzug. Ein durchgehender Weg, der alle seine Kanten abdeckt, muss mindestens eine Kante erneut durchlaufen.
Wenn die Spinne jedoch jede Verbindung verstärken möchte, indem sie genau zwei Seidenfäden darauf legt, kann sie den Algorithmus von Hierholzer nutzen. Das Verdoppeln jeder Kante ist ein eigener Vorbereitungsschritt: Dadurch wird jeder Knotengrad gerade. Der entstandene zusammenhängende Multigraph besitzt deshalb einen Eulerkreis, den der Algorithmus von Hierholzer findet. Wähle in der App zunächst Explore maths und dann Trace walk, um zuzusehen, wie die Spinne diesen doppelt verstärkten Graphen erzeugt. Echte Spinnen kennen den Algorithmus von Hierholzer wohl nicht – es sei denn, sie haben ihm damals von ihrem Netz aus zugeschaut und zugehört, als er seine Idee einem Kreis befreundeter Mathematiker vortrug :-).
Der Algorithmus von Hierholzer: Schritt für Schritt mit kurzem Beweis
Das Problem. Ein Eulerzug benutzt jede Kante genau einmal; Knoten dürfen mehrfach besucht werden. Endet er am Ausgangsknoten, heißt er Eulerkreis. Wir betrachten einen endlichen ungerichteten Graphen, dessen Knoten mit positivem Grad eine einzige Zusammenhangskomponente bilden. Ein Eulerkreis existiert, wenn alle Grade gerade sind; ein offener Eulerzug existiert, wenn genau zwei Grade ungerade sind. Eine Schleife trägt zwei zum Grad ihres Knotens bei; parallele Kanten werden einzeln gezählt.
- Startknoten wählen. Für einen Eulerkreis wählen wir einen beliebigen Knoten, an dem mindestens eine Kante liegt. Zunächst sind alle Kanten unbenutzt.
- Einen ersten geschlossenen Kantenzug bilden. Wir folgen jeweils einer beliebigen unbenutzten angrenzenden Kante, markieren sie als benutzt und setzen dies fort, bis am aktuellen Knoten keine unbenutzte Kante mehr liegt. Bei ausschließlich geraden Graden endet dieser maximale Kantenzug wieder am Startknoten.
- Eine Anschlussstelle suchen. Solange unbenutzte Kanten übrig sind, suchen wir auf dem bisherigen Kantenzug einen Knoten, an dem noch eine unbenutzte Kante liegt.
- Einen geschlossenen Umweg bilden und einfügen. Von dort folgen wir unbenutzten Kanten, bis es nicht mehr weitergeht. Der Umweg endet wieder am selben Knoten. Seine Kantenfolge wird an dieser Stelle in den bisherigen Kantenzug eingefügt. Der Umweg muss kein einfacher Kreis sein: Knoten dürfen mehrfach vorkommen.
- Wiederholen. Wir fügen weitere geschlossene Umwege ein, bis alle Kanten benutzt sind. Die entstandene Folge ist ein Eulerkreis.
- Zwei ungerade Knoten behandeln. Haben nur s und t ungeraden Grad, ergänzen wir eine eindeutig markierte Hilfskante zwischen ihnen, gegebenenfalls als parallele Kante. Wir berechnen einen Eulerkreis und schneiden dessen zyklische Kantenfolge an der Hilfskante auf. Nach Entfernen dieser Kante bleibt ein offener Eulerzug von s nach t oder in umgekehrter Richtung.
Warum funktioniert das? An jedem Knoten außer dem Start werden bei abgeschlossenen Besuchen jeweils eine ankommende und eine abgehende Kante benutzt. Befindet sich der Kantenzug gerade an einem solchen Knoten, hat er dort eine ungerade Anzahl von Kanteninzidenzen verbraucht, wobei eine Schleife doppelt zählt. Bei geradem ursprünglichem Grad bleibt deshalb eine unbenutzte Kante zum Verlassen übrig. Stecken bleiben kann er nur am Start; der erste Kantenzug ist also geschlossen. Nach dem Entfernen der Kanten eines geschlossenen Kantenzugs bleiben alle Restgrade gerade. Deshalb sind auch die späteren Umwege geschlossen. Ihr Einfügen erhält den Zusammenhang der Kantenfolge und wiederholt keine Kante, weil nur unbenutzte Kanten hinzukommen. Gibt es noch eine unbenutzte Kante, garantiert der Zusammenhang des Graphen eine Anschlussstelle auf dem bisherigen Kantenzug. Jeder eingefügte Umweg verbraucht mindestens eine neue Kante. Daher endet das Verfahren nach endlich vielen Einfügungen und erfasst jede Kante. Im offenen Fall macht die Hilfskante beide ungeraden Grade gerade; ihr Entfernen aus dem berechneten Eulerkreis liefert den gesuchten Eulerzug. Umgekehrt zeigt das Paaren von Ankunft und Abgang, weshalb nur die beiden Endknoten eines offenen Eulerzugs ungeraden Grad haben dürfen.
Das Haus in den Bildern. Beim Haus vom Nikolaus sind A und B die beiden Knoten ungeraden Grades; die Kreuzung der Diagonalen ist kein Knoten. Die Variante für offene Eulerzüge findet zunächst A-B-C-D-B und fügt bei D den verbleibenden geschlossenen Umweg D-A-C-E-D ein. So entsteht A-B-C-D-A-C-E-D-B: Jede der acht Kanten wird genau einmal benutzt. Keine Kante muss verdoppelt werden.
Von der Idee zum effizienten Programm. Ein Stapel speichert noch nicht abgeschlossene Knotenbesuche. Hat der oberste Knoten keine unbenutzte angrenzende Kante mehr, wird er in eine Ausgabeliste übernommen; am Ende wird diese Liste umgekehrt. Mit Adjazenzlisten, eindeutigen Kantennummern und Benutzt-Markierungen benötigen Laufzeit und Speicher O(|V| + |E|). Das Entfernen eines Eintrags vom Stapel ist Buchführung und bedeutet kein tatsächliches Zurücklaufen auf einer bereits gezeichneten Kante. Das PDF enthält präzisen Pseudocode, einen ausführlicheren Korrektheitsbeweis und eine Python-Implementierung.
Der Bezug zur Spinne. Jede Kante zu verdoppeln ist ein eigener Vorbereitungsschritt, der den zusammenhängenden Netzgraphen eulersch macht. Hierholzers Algorithmus findet anschließend einen Eulerkreis in diesem Multigraphen; er verdoppelt selbst keine Kanten und minimiert auch nicht die nötigen Wiederholungen. Im ursprünglichen Netz entsprechen die beiden Kopien dem zweimaligen Durchlaufen jedes Fadens.
Zum Weiterlesen: Ausführliche technische Darstellung lesen oder herunterladen (PDF, Deutsch und Englisch). Zehn Seiten mit Erklärung, Korrektheitsbeweis, Pseudocode, Python-Code und Literatur. Michael Emmerich, University of Jyväskylä, 17. Oktober 2026; A4, 12-Punkt-Schrift. Der deutsche Teil beginnt auf Seite 5.
Literatur zum Algorithmus von Hierholzer: C. Hierholzer & Chr. Wiener (1873). Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6, 30–32. (Deutschsprachige Originalarbeit.) Wieners Vorbemerkung erläutert, dass er den mündlichen Vortrag nach Hierholzers Tod mit Unterstützung Lüroths aus dem Gedächtnis rekonstruierte, da keine schriftliche Aufzeichnung vorlag.
Wähle deine Themen: Wähle Mathematical Playground, Nature Photography, Multiobjective Optimization oder eine beliebige Kombination dieser Kategorien. Mit All content erhältst du alle Beiträge. :-)
Wähle auf der nächsten Seite Michael Emmerich (emmerix.net) und anschließend deine Kategorien. Bei einem E-Mail-Abo ohne WordPress-Anmeldung kannst du mit der E-Mail-Adresse deines Abos einen persönlichen Verwaltungslink per E-Mail anfordern.
