Trémaux’ Methode

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Mögliche Verzweigungssituationen
Beispiel für das Trémaux’sche Verfahren – Animation (45 s)

Voraussetzungen[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

  • Gehe einen gewählten Weg immer bis zu dessen Ende.
    • Endet der Weg in einer Sackgasse, gehe an deren Anfang zurück.
    • 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!
        • Wurde der Weg jedoch bereits abgegangen, betrachte die Eingänge der anderen Wege.
          • Gibt es einen Weg, der noch nicht betreten wurde, wähle diesen.
          • Andernfalls wähle einen Weg, der erst einmal betreten wurde.

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[Bearbeiten | Quelltext bearbeiten]

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