"Ever had to detangle a ball of wool?" ("Mußten sie jemals ein Wollknäuel entwirren?") wird man bei "Detangle" gefragt. Für die wahrscheinlichere Zielgruppe der Mathe-Nerds wäre wohl "Mußten Sie jemals den Boyer-Myrvold-Algorithmus anwenden?" die passendere Frage. Worum geht es bei dem Spiel? Man bekommt einen Graphen vorgesetzt und soll seine Knoten solange verschieben bis alle Überkreuzungen verschwinden: So sah es vor dem letzten Schritt aus: und so vor dem vorletzten: Was steckt mathematisch dahinter? Es geht darum, einen Graphen ohne Überkreuzungen in die Ebene einzubetten. Graphen, die sich kreuzungsfrei in die Ebene einbetten lassen, heißen planare Graphen. Nach dem Satz von Kuratowski Ist ein Graph genau dann planar, wenn er keine Unterteilungen von K₅ oder K_3,3 als Teilgraphen enthält. Für die Graphen, die man bei "Detangle" vorgesetzt bekommt, ist das natürlich immer der Fall. In dem Spiel geht es nicht nur um irgendwelche überkreuzungsfreien Einbettungen des Graphen in die Ebene, zusätzlich sollen auch noch alle Kanten Geradenstücke sein. Auch das wird aber von der Graphentheorie abgedeckt, nämlich vom Satz von Fary: jeder planare Graph läßt sich überkreuzungsfrei so in die Ebene einbetten, dass die Kanten Geradenstücke sind. Das sind natürlich nur Existenzsätze, die einem bei der Lösung des Problems nicht weiterhelfen. Aber auch für dieses Problem gibt es Algorithmen, die effektivsten sind wohl der Boyer-Myrvold-Algorithmus und der Fraysseix-Ossona-Rosenstiehl-Algorithmus. Die App gibt es hier für 0,99 $.

Um einen Kommentar zu verfassen, müssen Sie sich einloggen bzw. kurz als Gast registrieren.