Trémaux’ Methode

Trémaux’ Methode ist ein Algorithmus, der ein Passieren jedes Irrgartens oder, allgemeiner, labyrinthischen Wegesystems ohne Kenntnis eines Plans ermöglicht. Das Verfahren arbeitet mit Markierungen und ist für eine praktische Anwendung geeignet.

Geschichte

Der Algorithmus wurde von Charles Pierre Trémaux (1859–1882) entwickelt, der eine Ausbildung an der École polytechnique zum Telegraphen-Ingenieur absolvierte. Nach seinem frühen Tod nahmen sowohl der Mathematiker Gaston Tarry (1843–1913) als auch der Autor und Mathematiker Édouard Lucas (1842–1891) die Idee auf. Während Tarry versuchte, eine einzige „Fundamentalregel“ zu formulieren, gab Lucas in einer populären Sammlung mathematischer Spiele Trémaux’ ursprüngliche, bis dahin unveröffentlichte Regeln in verständlicher Form wieder.

Idee

Während Wegesysteme, die ausschließlich in Sackgassen verzweigen, auf einfache Weise mithilfe der „Rechten-Hand-Regel“ (wall follower method, „Folge-der-Mauer-Methode“) gelöst werden können, wurde ein System mit netzartiger Struktur als „unentrinnbar“ betrachtet, weil es die Gefahr eines unendlichen „Im-Kreis-Gehens“ birgt. Bereits Leonhard Euler hatte sich mit dem Königsberger Brückenproblem einer verwandten Fragestellung gewidmet. Trémaux gelang es, die einzige immer anwendbare Methode zu entwickeln, die im schlechtesten Fall mit einem zweifachen Abgehen des Wegesystems auskam und ein dauerndes Irregehen ausschloss.

Arbeitsweise

Mögliche Verzweigungssituationen

Beispiel für das Trémaux’sche Verfahren – Animation (1 min 45 s)

Voraussetzungen

Das unbekannte Wegesystem wird als Graph aufgefasst. Dieser besteht aus Kanten und Knoten (Wege und Plätze; unter „Plätzen“ werden einfache Abzweigungen, Kreuzungen, aber auch beliebige Wegesterne verstanden). Ein Weg wird beim Betreten und Verlassen markiert, etwa durch einen Strich am Boden. Wege mit zwei Markierungen dürfen nicht mehr betreten werden.

Regeln

• Ein ausgewählter Weg wird immer bis zu dessen Ende gegangen.
  • Endet der Weg in einer Sackgasse, so geht man an deren Anfang zurück. (Daraufhin wird der Eingang zur Sackgasse mit einem zweiten Strich markiert und deshalb nicht wieder betreten.)
  • Mündet der Weg in einen Platz, muss dieser analysiert werden.
    • Wurde der Platz noch nie betreten, wird ein beliebiger Weg gewählt, welcher noch ungekannt ist.
    • Ist der Platz bereits bekannt, so wird der Weg analysiert, der zu dem Platz führte.
      • Wurde dieser Weg das erste Mal begangen, kehrt man um. (Somit hat man eine Schleife entdeckt und markiert das zuletzt begangene Teilstück an beiden Enden mit einem zweiten Strich, um zu verhindern, dass hier künftig im Kreis gegangen wird.)
      • Wurde der Weg jedoch bereits abgegangen, betrachtet man die Eingänge der anderen Wege. (Dementsprechend wird ein Bereich verlassen, der komplett abgesucht wurde und mit einem zweiten Strich „verschlossen“.)
        • Gibt es einen Weg, der noch nicht betreten wurde, wird dieser gewählt. (Somit wird ein neuer Bereich des Labyrinths erforscht.)
        • Gibt es andernfalls einen Weg, der erst einmal betreten wurde, so wird dieser gewählt. (Es wird nur einen solchen Weg geben. Dies ist der Rückweg aus einem Bereich, welcher vollständig, aber vergeblich abgesucht wurde.)
        • Andernfalls kehrt man nach vollständigem zweifachen Abgehen des Labyrinths wieder zum Ausgangspunkt zurück.

Es darf beim Betreten eines Platzes auf keinen Fall vergessen werden, diesen auf Markierungen an den anderen Wege-Einmündungen zu untersuchen, um zu entscheiden, ob es sich um eine noch „unbekannte“ Verzweigung handelt.

Literatur

• Gaston Tarry: Le problème des labyrinthes. In: Nouvelles annales de mathématiques, Bd. 14, 1895, S. 187–190.
• Édouard Lucas: Récréations mathématiques [Band 1]. 2. Auflage. Paris 1891, S. 47–49 (im 3. Abschnitt).