Direkt zum Inhalt

Nachtwächterin auf Platos Körpern

von Norbert Treitz
Treitz-Rätsel
© iStock / nicolas (Ausschnitt)
Amanda die Ameise arbeitet neuerdings als Nachtwächterin auf den platonischen Körpern. Dabei soll sie jeweils auf einem geschlossenen Weg alle Ecken genau einmal besuchen. Sie darf nur an Kanten entlanglaufen und jede einzelne Kante pro Rundgang höchstens einmal benutzen. Geht das auf jedem dieser Körper (Tetraeder, Oktaeder, Würfel, Ikosaeder und Dodekaeder), wenn ja: wie? Und wenn nicht, kann man zeigen, dass es nicht geht?

Zur Erleichterung des Probierens projizieren Sie die Kanten kreuzungsfrei in eine Ebene (Schlegel-Diagramm, im Prinzip stereografische Projektion).

Beachten Sie bitte, dass auch der unendlich große Rest der Ebene (hier kreisförmig abgeschnitten) jeweils eine Fläche des Polyeders darstellt.

Jetzt müssen Sie nur noch die Wege finden.

Für einen allgemeinen Graphen nennt man einen Weg mit diesen Eigenschaften einen Hamilton-Kreis. Der Aufwand, einen solchen zu finden, steigt mit der Knotenzahl des Graphen exponentiell an: Das Problem gehört zur berüchtigten Klasse der NP-vollständigen Probleme.

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Themenkanäle

Partnerinhalte