Direkt zum Inhalt

Mathematik: Das komplizierteste Labyrinth der Welt

Aus zwei mathematischen Kuriositäten erzeugt ein Algorithmus dieses außergewöhnliche Labyrinth. Doch die Technik ist keineswegs nur schöne Spielerei.
Aperiodisches Labyrinth auf grauem Hintergrund.
Dieses Labyrinth macht schwindelig!

Dieses Labyrinth ist außergewöhnlich: Auf den ersten Blick scheint es aus den stets gleichen Bögen und Zacken zu bestehen. Doch schaut man genauer hin, findet man immer wieder neue Varianten des Motivs, die besonders verschlungene Pfade bilden. Tatsächlich ist es nur ein Nebenprodukt eines besonderen Algorithmus. Shobhna Singh von der Cardiff University, Jerome Lloyd von der Universität Genf und Felix Flicker von der University of Bristol entwickelten eine Rechenvorschrift, um alle Knotenpunkte eines Gitters durch eine einzelne durchgehende Linie zu verbinden.

In ihrer Veröffentlichung im Fachjournal »Physical Review X« verwendeten sie jedoch kein normales Gitternetz, sondern eine aperiodische Kachelung. Das ist ein exotisches Phänomen der Geometrie, bei dem eine Ebene lückenlos mit zwei verschiedenen Kacheln gepflastert wird, so dass sie mit unendlich vielen unterschiedlichen Variationen ähnlicher Muster bedeckt ist. Und diese zahllosen Varianten machen das Labyrinth so komplex. Das Verfahren ist allerdings mehr als eine hübsche Spielerei: Die zu Grunde liegende Technik könnte auch helfen, bessere Katalysatoren für die Chemie zu entwickeln, und löst eine Reihe von komplexen Problemen der Geometrie.

Konstruktion des Labyrinths
Konstruktion des Labyrinths | So entsteht das Labyrinth aus der aperiodischen Kachelung. Die schwarze Linie ist der algorithmisch konstruierte Hamiltonkreis.

Die Labyrinthe basieren auf einem Hamiltonkreis. Der entsteht, wenn man in einem beliebigen Gitternetz eine durchgehende Linie entlang der Kanten zieht, so dass jeder Gitterpunkt genau einmal berührt wird und man am Ende zum Ausgangspunkt zurückkehrt. Das kann man auf Karopapier ganz einfach nachvollziehen, ist aber ziemlich langweilig. Die Fachleute dagegen verwendeten ein sehr ungewöhnliches Gitter – eine aperiodische Kachelung.

Das ist erst einmal genau das, wonach es klingt: eine lückenlos mit Kacheln bedeckte Fläche, bei der die Ränder der Kacheln das Gitter bilden. Nur mit dem Unterschied, dass sich das Muster nicht in alle Richtungen streng im gleichen Rhythmus wiederholt. Aperiodische Kachelungen basieren auf den Symmetrien, wie sie auch regelmäßige Fünf- oder Achtecke haben. Ebenso wie man mit diesen Formen ein Badezimmer nicht lückenlos kacheln kann, bilden Gitter mit diesen Symmetrien keine unendlichen regelmäßigen Muster in alle Richtungen. Stattdessen bilden sie ein Muster, das immer wieder irgendwie ähnlich, aber doch überall anders ist. Ihr dreidimensionales Gegenstück sind die kuriosen Quasikristalle, in denen die Atome nicht streng regelmäßig angeordnet sind wie in echten Kristallen, aber überall eine lokale kristalline Ordnung einnehmen.

Singh, Lloyd und Flicker entwickelten nun einen Algorithmus, der Hamiltonkreise in einem solchen als Ammann-Beenker-Kachelung bezeichneten Gitter generiert. Diese Kachelung hat eine achtzählige Symmetrie und besteht aus zwei Arten von Kacheln. Das Team erzeugte die Kachelung durch eine als Inflation bezeichnete Technik: Die beiden elementaren Kacheln werden jeweils mit kleineren Versionen ihrer selbst gekachelt und »aufgebläht«. Zusätzlich werden die Pfade, die später das Labyrinth bilden, nach bestimmten Regeln in die Kacheln eingefügt, so dass bei jeder Stufe der Inflation zusammenhängende Pfade des Labyrinths entstehen. Die drei Fachleute demonstrieren außerdem eine Reihe von Anwendungen. Neben hübschen Labyrinthen liefert der Algorithmus außerdem Lösungen für einen Spezialfall des Travelling-Salesman-Problems, des Dreifarbenproblems der Graphentheorie und die Frage, wie man mit einem Rasterelektronenmikroskop eine Probe am effizientesten scannt.

WEITERLESEN MIT »SPEKTRUM +«

Im Abo erhalten Sie exklusiven Zugang zu allen Premiumartikeln von »spektrum.de« sowie »Spektrum - Die Woche« als PDF- und App-Ausgabe. Testen Sie 30 Tage uneingeschränkten Zugang zu »Spektrum+« gratis:

Jetzt testen

(Sie müssen Javascript erlauben, um nach der Anmeldung auf diesen Artikel zugreifen zu können)

  • Quellen
Singh, S. et al.: Hamiltonian cycles on Ammann-Beenker Tilings. Physical Review X, 2024

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.