Hamilton-Kreis auf einem Dodekaeder
Sir William Hamilton erfand im Jahr 1857 das „Icosische Spiel“, bei dem es darum geht, alle Ecken eines Dodekaeders längs eines geschlossenen Kantenzuges genau einmal zu besuchen. Auch wenn der kommerzielle Erfolg bescheiden blieb, so wurde der Name Hamilton-Kreis bekannt für einen Typ von geschlossenen Kurven auf Graphen: Alle Ecken eines Graphen sollen auf einem geschlossenen Kantenweg genau einmal besucht werden.Für die Kantengraphen der platonischen Körper kennt man Hamilton-Kreise, für das Beispiel von William F. Lindgren gibt es keinen Hamilton-Kreis. Die Frage der Entscheidbarkeit, ob ein vorgegebener Graph einen Hamilton-Kreis besitzt, ist algorithmisch nicht leicht zu beantworten. Nach Richard Karp (1972) gehört die Frage zur Klasse der NP-vollständigen Probleme.
Der Graph von Lindgren enthält keinen Hamilton-Kreis
Der Graph von Lindgren ist ein hypohamiltonischer Graph. Solch ein Graph besitzt zwar keinen Hamilton-Kreis, allerdings enthält er nach Entfernung eines beliebigen seiner roten Eckpunkte und angrenzenden Kanten einen Hamilton-Kreis.
* Bilder von Kai Lawonn und Konrad Polthier
* Text von Konrad Polthier
mit freundlicher Genehmigung aus dem Buch:
Georg Gläser und Konrad Polthier
Bilder der Mathematik
SpringerSpektrum 2. erw. Auflage 2014
www.bilder-der-mathematik.de
