Zum Inhalt
Alle Apps

Barnettes Vermutung: Rundreise über jedes Polyeder (3D)

Über diese App

Ein Polyeder mit je drei Kanten an jeder Ecke und nur geraden Flächen hat immer eine Rundreise, die jede Ecke genau einmal besucht. Ein leuchtender Faden sucht sie live per Backtracking: auf Würfel, Prisma, archimedischen Körpern und Zufallspolyedern mit Flächen bis zum Zwölfeck und mehr. Ecken zweifarbig, große Flächen getönt. Zwei Gegenbeispiele, denen je eine Bedingung fehlt (Tutte-Graph, drei Kammern), lassen die vollständige Suche scheitern. openai/math Familie 180 (Lean-formalisiert). Exponatfähig.

Worum es geht

David Barnette fragte 1969: Hat jedes Polyeder, an dessen Ecken je drei Kanten zusammenkommen und dessen Flächen alle eine gerade Eckenzahl haben, eine Rundreise, die jede Ecke genau einmal besucht? Eine solche Rundreise heißt Hamiltonkreis. Bewiesen waren nur Sonderfälle: Flächen mit 4 und 6 Ecken (Goodey 1975) und Flächen bis 8 Ecken (Schnieders 2025). Ein KI-erzeugtes Preprint aus github.com/openai/math (Familie 180) beweist die Vermutung nach eigener Darstellung ohne Grenze für die Flächengröße. Laut Katalog ist der Hauptsatz in Lean formalisiert, begutachtet ist das Preprint nicht. Der Beweis zeigt nur, dass die Rundreise existiert, und liefert keinen schnellen Algorithmus.

Was die App zeigt

Ein leuchtender Faden sucht die Rundreise live per Backtracking: Kommt er nicht weiter, zieht er sich zurück und probiert die nächste Abzweigung. Zur Wahl stehen Würfel, Sechseckprisma, archimedische Körper wie stumpfes Oktaeder und stumpfes Kuboktaeder sowie Zufallspolyeder mit Flächen bis zum Zwölfeck und mehr. Die Ecken sind zweifarbig, was genau bei geraden Flächen geht; Flächen ab zehn Ecken sind getönt, denn für sie war die Frage offen. Die App ist exponatfähig.

Die Gegenbeispiele

Zwei Gegenbeispiele zeigen, dass keine Bedingung entbehrlich ist. Der Tutte-Graph von 1946 hat ungerade Flächen; dort scheitert die Zweifärbung an warmen Kanten, und es gibt keine Rundreise. Beim Beispiel mit drei Kammern trennen zwei Ecken das Polyeder so, dass eine Rundreise durch die zwei Nadelöhre höchstens zwei Kammern erreicht. In beiden Fällen läuft die vollständige Suche sichtbar ins Leere. Vergleiche das mit einem Zufallspolyeder, bei dem der Faden nach einigen Rückzügen ans Ziel kommt.

Häufige Fragen

Was ist ein Hamiltonkreis?
Ein Hamiltonkreis ist ein geschlossener Weg in einem Graphen, der jede Ecke genau einmal besucht und zum Start zurückkehrt. Ob ein Graph einen Hamiltonkreis hat, ist im Allgemeinen schwer zu entscheiden (NP-vollständig). Für spezielle Graphenklassen gibt es Sätze, die seine Existenz garantieren.
Was besagt Barnettes Vermutung?
Barnettes Vermutung (1969) sagt: Jeder 3-zusammenhängende, kubische, bipartite planare Graph hat einen Hamiltonkreis. Anschaulich: Jedes Polyeder mit drei Kanten an jeder Ecke und nur geraden Flächen hat eine Rundreise über alle Ecken. Ohne die Bedingung gerader Flächen ist die Aussage falsch, wie der Tutte-Graph zeigt.
Ist Barnettes Vermutung bewiesen?
Ein KI-erzeugtes Preprint aus dem Katalog github.com/openai/math (Familie 180) beweist sie nach eigener Darstellung für alle Flächengrößen; vorher waren nur Polyeder mit Flächen bis acht Ecken geklärt. Laut Katalog ist die Existenz des Hamiltonkreises in Lean formalisiert. Das Preprint ist noch nicht begutachtet.
Was kann ich in dieser App ausprobieren?
Du wählst ein Polyeder und siehst einem Faden zu, der per Backtracking eine Rundreise sucht und findet. Zufallspolyeder erzeugen immer neue Fälle mit großen Flächen. Zwei Gegenbeispiele zeigen, woran die Suche scheitert, wenn eine Bedingung fehlt.

Fach: Offene Probleme, gelöst von KI

Mehr aus Offene Probleme, gelöst von KI

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps