Fakultät für Informatik - Technische Universität München Lehrstuhl für Effiziente Algorithmen

Systementwicklungsprojekt

Symmetrie-Eigenschaften Hamiltonscher Kreise in Platonischen Körpern

Die fünf platonischen Körper haben Automorphismen-Gruppen von sehr hoher Mächtigkeit (z.B. Dodekaeder: 120, siehe Tabelle).

In der Menge der Hamilton-Kreise (Rundweg, der jeden Knoten genau einmal enthält) auf diesen Körpern gibt es viele symmetrische Exemplare. Diese sind hinsichtlich ihrer Symmetrie zu klassifizieren und zu reduzieren.

Manuelle Untersuchungen haben ergeben, dass im Falle von Tetraeder, Hexaeder und Dodekaeder tatsächlich bis auf Symmetrie nur ein einziger Hamilton-Kreis zu existieren scheint. Für das Oktaeder wurden zwei verschiedene Lösungen gefunden. Die Frage ist nun vor allem, wieviele verschiedene Hamilton-Kreise es in einem Ikosaeder gibt. Ein bereits existierendes Programm hat die Anzahl ohne Symmetrie-Bereinigung mit 1280 berechnet. Aufgrund der Mächtigkeit der Automorphismengruppe von 120 existieren damit mindestens 11 verschiedene (symmetrie-bereinigte) Lösungen.

Betreuer: Dr. Ludwig Zagler

Programmiersprache: C/C++

Die Arbeit ist mit Hilfe von LaTeX anzufertigen (mit graphischer Darstellung der Platonischen Körper und ihrer Hamilton-Kreise).
Gegebenenfalls wäre auch eine Ausschreibung als Bachelor-Arbeit denkbar.

Bei Interesse wenden Sie sich bitte an Frau Annelies Schmidt (schmiann@in.tum.de) oder Hanjo Täubig (taeubig@in.tum.de)