Nachtwächterin auf Platos Körpern
© 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).
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