Factorio und der Vier-Farben-Satz

Ich habe heute mit einem Freund Factorio gespielt, und dabei kamen wir auf den Vier-Farben-Satz zu sprechen. Dieser besagt, dass man jeden planaren Graph (wie z.B. eine Landkarte) mit maximal vier Farben so einfärben kann, das zwei benachbarte Knoten niemals die gleiche Farbe haben. Einen solchen planaren Graph stellen auch die Gleisabschnitte aus Factorio dar, die auch in verschiedenen Farben angezeigt werden. Aus Spaß habe ich dann dann mal das Minimalbeispiel für das man vier Farben benötig nachgebaut:

Vier-Farben-Graph in Factorio

Ich muss gestehen dass ich die Farbe in der Mitte (dunkelblau) noch die gesehen habe, bis jetzt haben bei meinen Konstruktionen offenbar immer drei Farben ausgereicht 🙂

Auch wenn vier Farben immer reichen, ist es nicht ganz leicht die passende Lösung in allen Fällen zu finden. Laut FFF #201 haben es sich die Entwickler daher leicht gemacht: Es wird einfach immer eine Farbe benutzt, die keiner der angrenzenden Blöcke bereits hat. Das funktioniert offenbar recht passabel (siehe oben), auch wenn es theoretisch Situationen geben kann, in denen die Farben (scheinbar 5) nicht ausreichen und zwei benachbarte Blöcke die gleiche Farbe bekommen.

Fun fact: Der Vier-Farben-Satz wurde bis jetzt nur durch einen Computer bewiesen. Man konnte das Problem auf 633 Variante reduzieren, für die ein Computer dann jeweils eine Lösung gefunden hat.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert