Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03587.jsonl.gz/1547

Hans Walser, [20170911]
Hamiltonkreis im Gitterwrfel
Anregung: Heinz Schumann, Weingarten
Die Abbildung 1a zeigt einen 2×2×2-Gitterwrfel (wir zhlen die Gitterpunkte, nicht die Seitenlngen (ãZaunpfahl-ProblemÒ)) mit einem roten Hamiltonkreis. Dies ist ein geschlossener Weg auf den schwarzen Kanten, der jeden Gitterpunkt genau einmal trifft.
Gibt es einen Hamiltonkreis auf dem 3×3×3-Gitterwrfel der Abbildung 1b? Die Leserin ist eingeladen, bei der Abbildung 1b einige Versuche zu machen.
Abb. 1: Fragestellung
Die Abbildung 2 zeigt einen Hamiltonkeis auf einem 4×4×4-Gitterwrfel. Die Leserin ist eingeladen, haptisch nachzuprfen.
Abb. 2: Hamiltonkreis
Bei Versuchen, in den Gitterwrfel der Abbildung 1b einen Hamiltonkreis einzuzeichnen, stellen wir fest, dass es immer bis auf einen Gitterpunkt geht. Das lsst vermuten, dass wir es mit einem Parittsproblem zu tun haben.
Tatschlich werden wir sehen:
Mit einer
geraden Zahl g gibt es im g×g×g-Gitterwrfel immer
einen Hamiltonkreis.
Mit einer ungeraden Zahl u gibt es im u×u×u-Gitterwrfel keinen Hamiltonkreis.
Die Abbildung 3 zeigt das Analogon zur Abbildung 1 in der Ebene.
Abb. 3: Analogon in der Ebene
Im 2×2-Gitterquadrat haben wir einen Hamiltonkreis (Abb. 3a), im 3×3-Gitterquadrat (Abb. 3b) gibt es keinen. Es bleibt immer ein Gitterpunkt brig.
Die Abbildung 4 zeigt ein 4×4-Gitterquadrat mit Hamiltonkreis.
Abb. 4: Gitterquadrat mit Hamiltonkreis
Wir knnen unsere Vermutungen verallgemeinern:
In der Dimension 1 gibt es keine Hamiltonkreise.
In den Dimensionen n >1 gilt:
Mit einer
geraden Zahl g gibt es im gn-Gitter-n-Hyperwrfel immer einen Hamiltonkreis.
Mit einer ungeraden Zahl u gibt es im un-Gitter-n-Hyperwrfel keinen Hamiltonkreis.
Mit einer ungeraden Zahl u ist auch un eine ungerade Zahl. Der un-Gitter-n-Hyperwrfel hat also eine ungerade Anzahl von Gitterpunkten. Wir frben nun die Gitterpunkte abwechslungsweise rot und blau (Abb. 5).
Das geht in beliebigen Dimensionen, da die Gitterpunkte und Kanten eines Gitter-n-Hyperwrfel einen paaren oder bipartiten Graphen bilden. Um dies einzusehen, verwenden wir kartesische Koordinaten fr die Gitterpunkte. Die Koordinatenachsen seien parallel zu den Gitterlinien und die Einheit die Maschenbreite des Gitters. Der Ursprung sei eine Ecke des Gitterwrfels. Die Koordinaten der Gitterpunkte im Gitterwrfel sind also nichtnegative ganze Zahlen in .
Die Summen sind entweder gerade oder ungerade. Das gibt eine Klasseneinteilung der Punkte. Wir frben die Punkte entsprechend rot oder blau. Zwei durch eine Kante verbundene Punkte haben verschiedene Farben, weil sie sich in genau einer Koordinate um 1 unterscheiden.
Da die Gesamtzahl der Gitterpunkte ungerade ist, kann die Anzahl der blauen Gitterpunkte nicht gleich der Anzahl der roten Gitterpunkte sein.
Abb. 5: Rot-blau-Frbung
Ein Hamiltonkreis durchluft abwechslungsweise rote und blaue Punkt. Er ist also eine geschlossene Perlenkette mit abwechslungsweise roten und blauen Perlen. Daher hat es gleich viele rote wie blaue Perlen. Widerspruch.
Fr eine beliebige (particular but not special) gerade Zahl g geben wir konstruktiv eine Lsung mit Induktion ber die Dimension n.
Fr n = 2 haben wir die ãHeizschlangenÒ-Lsung (Abb. 6 fr g = 10).
Abb. 6: Heizschlangen
Fr den Schritt in die Dimension n = 3 arbeiten wir mit g ebenen Heizschlangen, die an einer Ecke etwas geffnet sind. Und zwar nehmen wir 2 geffnete ebene Heizschlangen vom Typ der Abbildung 7a und geffnete ebene Heizschlangen vom Typ der Abbildung 7b.
Abb.7: Geffnete Heizschlangen
Nun stapeln wir diese g ebenen Heizschlangen senkrecht, also im Sinne der neuen, dritten, Dimension, aufeinander. Zuunterst und zuoberst je ein Exemplar der Abbildung 7a, dazwischen die anderen. Die unterste und die oberste Lage verbinden wir mit einer durchgehenden senkrechten Steigleitung an den u§ersten Ecken. Diese trifft auch alle freistehenden Gitterpunkte der Heizschlangen der Abbildung 7b. Und nun verbinden wir abwechslungsweise hinter und neben dieser durchgehenden Steigleitung je zwei der ebenen Heizschlangen mit einer Steigleitung der Hhe 1. Das Verfahren ist bereits in der Abbildung 2 (fr g = 4) illustriert.
Fr den Schritt von der Dimension auf die Dimension n arbeiten wir mit g Lsungen fr die Dimension . Wir whlen je eine Ecke und entfernen dort bei zwei Lsungen eine der beiden zum Hamiltonkreis gehrenden roten Kanten und bei den restlichen Lsungen beide zum Hamiltonkreis gehrenden roten Kanten, analog zur Abbildung 7. Dann schichten wir die Lsungen senkrecht im Sinne der n-ten Dimension so aufeinander, dass die bearbeiteten Ecken bereinander liegen, die schwarzen Kanten mit den nun fehlenden zum Hamiltonkreis gehrenden roten Kanten parallel sind und zudem zuunterst und zuoberst die beiden Sonderflle liegen. Dann verbinden wir unten und oben mit einer durchgehenden Steigleitung und die anderen Schichten mit Steigleitungen der Hhe 1. So erhalten wir eine Lsung fr die Dimension n.
Es gibt auch andere Lsungen. Die Abbildungen 8a bis 8c zeigen Varianten zur Lsung der Abbildung 2. Eine ist allerdings falsch. Welche?
Abb. 8a: Variante
Abb. 8b: Variante
Abb. 8c: Variante
Die Abbildung 9a zeigt eine Lsung fr g = 2 und die Dimension n = 4 nach dem oben beschriebenen Induktionsschritt.
Abb. 9a: Vierdimensionaler Hypergitterwrfel mit Hamiltonkreis
Die Abbildung 9b zeigt eine Variante. Die Frage ist, ob es sich wirklich um eine Variante handelt oder nur um eine andere Sicht.
Abb. 9b: Variante
Die Anzahl der Lsungen zu gegebenem g und gegebener Dimension n ist mir nicht bekannt. Ein schnes kombinatorisches Problem.