Erkundung eines Labyrinths

In einem Labyrinth sehen wir von jedem Raum nur die ablaufenden Gänge, der Bauplan des Labyrinths liegt uns nicht vor. Die Räume eines Labyrinths bilden die Ecken und seine Gänge die Kanten eines zusammenhängenden Graphen. Es stellt sich also die Frage, wie wir einen zusammenhängenden Graphen möglichst schnell vollständig erkunden, wenn unsere Sicht auf den aktuellen Standort beschränkt ist. Wir werden dabei gewisse Kanten zweimal besuchen müssen, denn ist eine Ecke eine Sackgasse (d. h. ihr Grad ist gleich 1), so müssen wir in die Ecke hinein- und auch wieder zurücklaufen.

Es gibt nun ein überraschend einfaches Verfahren, das ein Labyrinth ausgehend von einer Startecke vollständig erkundet und dabei jede Kante genau einmal in jeder Richtung durchläuft und schließlich auch wieder aus dem Labyrinth herausführt. Dabei darf man an den besuchten Kanten gewisse Markierungspfeile anbringen. Es ist aber nicht nötig, während der Erkundung eine Karte des Labyrinths anzufertigen.

Wir legen einen zusammenhängenden Graphen G = (E, K) mit Eckenmenge E = { 0, 1, …, n } zugrunde, der das Labyrinth modelliert. Zudem sei 0 die Startecke und 1 ihr eindeutiger Nachbar, d. h. die Kante 0 1 ist der Eingang in das Labyrinth. Wir konstruieren nun rekursiv einen geschlossenen Kantenzug a₀, …, a_m mit a₀ = a_m = 0 und m = 2|K| in G. Dabei werden die Kanten von G mit roten oder gelben Pfeilen markiert. Hierbei steht „rot“ für „bereits durchlaufen (in Pfeilrichtung)“ und zugleich für „fortan verboten“, während die gelben Pfeile eine Sonderrolle spielen, die man mit „nicht durchlaufen, solange noch andere Optionen zur Verfügung stehen“ umschreiben kann. Genaueres geht aus dem Algorithmus hervor.

Sagen wir im folgenden, dass a b markiert wird, so zeigt der Markierungspfeil immer von a nach b.

Algorithmus zur Erkundung eines Labyrinths

Wir setzen a₀ = 0 und a₁ = 1 und markieren 0 1 rot.

Sei nun a₀, …, a_i konstruiert für ein i ≥ 1. Ist a_i = 0, so stoppen wir.

Wird a_i zum ersten Mal besucht, so markieren wir a_i a_i − 1 gelb. (Für i = 1 wird also insbesondere 10 gelb markiert.) Im Falle der Existenz sei a_i + 1 eine Ecke derart, dass a_i a_i + 1 weder gelb noch rot markiert ist; andernfalls sei a_i + 1 die eindeutige Ecke, für die a_i a_i + 1 gelb markiert ist. In beiden Fällen markieren wir a_i a_i + 1 rot und wiederholen das Verfahren.

Jede durchlaufene Kante wird also sofort in Durchlaufrichtung mit einem roten Pfeil markiert. Wird eine Ecke zum ersten Mal besucht, so wird die Besuchskante in entgegengesetzter Richtung mit einem gelben Pfeil markiert. Rote Kanten dürfen in der Folge unter keinen Umständen in Pfeilrichtung durchlaufen werden, und Kanten mit einem gelben Pfeil werden so lange wie möglich gemieden. Trägt eine Kante einen gelben Pfeil, so trägt sie auch einen roten Pfeil in umgekehrter Richtung. Wir zeigen nun:

Satz (Korrektheit des Erkundungs-Algorithmus)

Ist Z = a₀, …, a_m der durch den Algorithmus konstruierte Kantenzug in G, so gilt m = 2|K|, a_m = 0, und für jede Kante a b  ∈  K existieren i und j mit a_i = a, a_i + 1 = b und a_j = b,  a_j + 1 = a.

Beweis

Sei Z = a₀, …, a_m. Wir zeigen zunächst, dass der Kantenzug Z geschlossen ist:

(+) Es gilt a_m = 0.

Beweis von (+)

Für a ≠ 0 gibt es zu Beginn d(a)-viele Möglichkeiten, die Ecke a zu betreten und d(a)-viele Möglichkeiten, sie wieder zu verlassen. Durch jeden Besuch von a werden beide Möglichkeiten jeweils um 1 reduziert. Damit können wir jede besuchte Ecke a ≠ 0 von Z auch wieder verlassen. Nach Konstruktion stoppt das Verfahren also mit a_m = 0.

Wir zeigen nun durch starke Induktion nach 1 ≤ i < m:

(++) a_i wird genau d(a_i)-mal auf Z besucht.

Beweis von (++)

Da die gelb markierte Kante 10 nach (+) durchlaufen wird, gilt die Aussage für a₁ = 1. Sei nun i ≥ 2 und die Aussage gelte für alle a_j, j < i. Wurde a_i in a₁, …, a_i − 1 besucht, so ist nichts zu zeigen. Andernfalls wird aber a_i a_i − 1 gelb markiert. Annahme, a_i wird nicht d(a_i)-mal besucht. Dann wird die gelb markierte Kante a_i a_i − 1 nach den Regeln des Algorithmus nicht durchlaufen, und damit wird auch a_i − 1 nicht d(a_i − 1)-mal besucht, Widerspruch.

Nach Konstruktion von Z genügt es zu zeigen:

(+++) Jede Ecke a von G wird von Z besucht.

Beweis von (+++)

Wegen G zusammenhängend gibt es einen Weg b₀, …, b_k von 1 nach a. Wir zeigen durch Induktion nach j ≤ k, dass b_j von Z besucht wird.

Dies ist klar für b₀ = 1. Wird nun aber b_j für ein j < k von Z besucht, so wird b_j nach (++) sogar d(b_j)-oft von Z besucht, und alle diese Besuche führen auf verschiedenen Kanten von b_j weg. Also ist b_j b_j + 1 eine besuchte Kante von Z, und damit wird also auch b_j + 1 von Z besucht.

Aus (++) und (+++) folgt m = (∑_{a  ∈  E − { 0 }} d(a)) + 1 = ∑_{a  ∈  E} d(a) = 2 |K|.

Der Beweis von (+) benötigt die gelben Markierungspfeile nicht. Jede Erkundung eines Labyrinths, die es vermeidet, eine Kante in derselben Richtung zweimal zu durchlaufen, führt aus dem Labyrinth wieder heraus. Die gelben Markierungspfeile stellen sicher, dass die gesamte Zusammenhangskomponente der Startecke 0 erkundet wird. Kommt es uns nur darauf an, einen Schatz im Labyrinth zu finden, so können wir die gelben Pfeile zurücklaufen, sobald der Schatz gefunden ist.

Unser Verfahren zur Erkundung eines Labyrinths lässt sich auch für „Eulersche Fragestellungen“ verwenden: Ein Postbote wird ausgehend vom Postamt gerne jede Straße je einmal in jeder Richtung durchlaufen, da er dann die Post für beide Straßenseiten leichter verteilen kann. Weiter will er am Ende wieder am Postamt ankommen. Obiger Satz zeigt, dass diese Ansprüche für jeden beliebigen zusammenhängenden Graphen erfüllt werden können, ganz ohne eine Gradbedingung.