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“ barg. 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 (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

• Gehe einen gewählten Weg immer bis zu dessen Ende.
  • Endet der Weg in einer Sackgasse, gehe an deren Anfang zurück. (Du wirst den Eingang zur Sackgasse dann mit einem zweiten Strich markieren und deshalb nicht wieder betreten.)
  • Mündet der Weg in einen Platz, analysiere den Platz.
    • Wurde der Platz noch nie betreten, wähle einen beliebigen Weg.
    • Ist der Platz bereits bekannt, analysiere den Weg, der zu dem Platz führte.
      • Wurde dieser Weg das erste Mal begangen, kehre um! (Du hast eine Schleife entdeckt und markierst das zuletzt begangene Teilstück an beiden Enden mit einem zweiten Strich, um zu verhindern, dass du hier künftig im Kreis gehst.)
      • Wurde der Weg jedoch bereits abgegangen, betrachte die Eingänge der anderen Wege. (Du verlässt einen Bereich, den du komplett abgesucht hast, und verschließt ihn mit einem zweiten Strich.)
        • Gibt es einen Weg, der noch nicht betreten wurde, wähle diesen. (Erforsche einen neuen Bereich des Labyrinths.)
        • Andernfalls wähle einen Weg, der erst einmal betreten wurde. (Es wird nur einen solchen Weg geben. Dies ist dein Rückweg aus einem Bereich, den du vollständig, aber vergeblich abgesucht hast.)

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).