12 11 10 9 8 7 6 5 4 3 2 1 Abbildung 4: Darstellung als Graphen 1. Keine Kante darf mehr als einmal in derselben Richtung durchlaufen werden. 2. Erreichen wir zum  ersten  Mal  v  6 =  u₀, so markieren wir die Kante (u, v), auf der wir gekommen sind. Wir m¨ussen nun zuerst alle Kan- ten (v, x), x  6 =  u  benutzen, bevor wir den Knoten  ¨uber (v, u) wieder verlassen d¨urfen. Es handelt sich also um ein einfaches Backtracking-Verfahren. Wir bewegen uns durch das Labyrinth, bis wir nicht mehr weiterkommen (d.h. alle Kanten zu einem Knoten schon einmal besucht worden sind) und bewegen uns dann einen Schritt zur¨uck. 12 11 10 9 8 7 6 5 4 3 2 1 Abbildung 5: Der Weg durchs Labyrinth Wieso funktioniert das Verfahren nun? Sei also  u₀, u₁, . . . u_p  der durch den Algorithmus konstruierte gerichtete Kantenzug W . Wir halten ersteinmal fest, daß u₀ = u_p gelten muß, damit wir am Ende der Tour wieder am Eingang ankommen. Außerdem muß f¨ur alle Ecken  x     W  gelten  d⁺_W (x) =  d^-_W (x), denn jede Ecke, die man betritt, verl¨aßt man auch wieder. Wir nennen v eine gute Ecke, falls alle mit v inzidente Kanten (e = (x, v)) in beiden Richtungen in W erscheinen (e = (v, x)). O enbar ist e₀ eine gute Ecke, da wir ansonsten vom Eingang her im Labyrinth noch in anderen Weg w¨ahlen k¨onnten, die wir bisher noch nicht betreten haben. 9