Kartenmaler zum Vierfarbensatz
Wie kompliziert eine Karte auch ist, vier Farben reichen immer aus, um sie so zu färben, dass Länder mit gemeinsamer Grenze nie dieselbe Farbe haben. Die Aussage ist so einfach, dass ein Kind sie mit Buntstiften ausprobieren kann, und doch brauchte es mehr als ein Jahrhundert und einen Computer, um sie zu beweisen. Färben Sie selbst eine zufällige Karte, sehen Sie, an welchen Grenzen es Konflikte gibt, und sehen Sie dann drei Methoden bei der Arbeit zu, von einer schnellen gierigen Regel, die manchmal eine fünfte Farbe braucht, bis zu einer Backtracking-Suche, die immer mit vier auskommt. Wählen Sie eine Farbe und klicken Sie auf Länder, um sie zu färben; eine Grenze wird rot, wenn zwei Nachbarn dieselbe Farbe haben. Länder, die sich nur an einer Ecke berühren, dürfen dieselbe Farbe haben. Oder lassen Sie den Computer arbeiten: Wählen Sie eine Methode und drücken Sie Lösen, um zuzusehen, oder Schritt, um Zug für Zug zu folgen. Wenigste Farben prüft, ob diese Karte mit drei oder sogar zwei Farben auskäme. Neue Karte zeichnet eine andere Karte, und Nachbarn zeigen zeichnet das Netz der Länder, die eine gemeinsame Grenze haben.
Wie es funktioniert
- Wählen Sie die Anzahl der Länder und drücken Sie Neue Karte, oder beginnen Sie mit der angezeigten Karte.
- Wählen Sie eine Farbe und klicken Sie auf Länder, um sie zu färben; achten Sie auf rote Grenzen, wo Nachbarn in Konflikt geraten.
- Wählen Sie eine Methode und drücken Sie Lösen oder Schritt, um zuzusehen, wie sie die Karte färbt, und drücken Sie Wenigste Farben, um zu sehen, wie viele Farben diese Karte braucht.
Von Karten zu Graphen
Setzen Sie in jedes Land einen Punkt und verbinden Sie zwei Punkte, wenn ihre Länder eine gemeinsame Grenze haben. So wird aus der Karte ein Graph, und die Karte zu färben ist dasselbe, wie die Punkte so zu färben, dass verbundene Punkte verschiedene Farben haben. Weil Karten auf einem flachen Blatt gezeichnet werden, sind diese Graphen planar: Sie lassen sich ohne sich kreuzende Linien zeichnen. Länder, die sich nur in einem einzigen Punkt treffen, wie vier Quadrate an einer Ecke, sind keine Nachbarn. Der Vierfarbensatz besagt, dass sich jeder planare Graph mit vier Farben färben lässt. Schalten Sie Nachbarn zeigen ein, um den Graphen der aktuellen Karte zu sehen.
Drei Arten zu färben
Die gierige Färbung nimmt die Länder eines nach dem anderen, die mit den meisten Nachbarn zuerst, und gibt jedem die erste Farbe, die seine Nachbarn noch nicht verwendet haben. Sie ist schnell, aber kurzsichtig, und auf manchen Karten greift sie zu einer fünften oder sogar sechsten Farbe. DSATUR, 1979 von Daniel Brélaz erfunden, wählt als Nächstes immer das Land, dessen Nachbarn bereits die meisten verschiedenen Farben zeigen, und vermeidet diese Falle meist. Backtracking probiert die Farben der Reihe nach aus und macht, wenn für ein Land keine mehr übrig ist, die letzten Entscheidungen rückgängig und versucht es erneut; es findet immer eine Färbung mit vier Farben, manchmal erst, nachdem es viele Male zurückgegangen ist.
Häufig gestellte Fragen
Warum reichen vier Farben immer aus?
Eine kurze Begründung hat niemand gefunden. Der Beweis von Kenneth Appel und Wolfgang Haken aus dem Jahr 1976 zeigte, dass jede Karte eine von 1.936 kleinen Konfigurationen enthalten muss und dass sich jede davon entfernen und die Färbung anschließend wiederherstellen lässt; alle zu prüfen kostete mehr als tausend Stunden Rechenzeit. Ein einfacherer Computerbeweis von Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas aus dem Jahr 1996 kommt mit 633 Konfigurationen aus, und 2005 verifizierte Georges Gonthier einen Beweis vollständig mit dem Beweisassistenten Coq.
Brauchen manche Karten alle vier Farben?
Ja. Vier Länder, von denen jedes die anderen drei berührt, etwa ein Land, das von drei anderen in einem Ring umgeben ist, brauchen vier. Viele Karten kommen jedoch mit drei aus, und Wenigste Farben findet das für die Karte auf dem Bildschirm heraus. Allgemein zu entscheiden, ob sich eine Karte mit drei Farben färben lässt, ist ein schweres Problem, NP-vollständig, obwohl vier Farben immer ausreichen.
Warum verwendet die gierige Methode manchmal fünf Farben?
Sie färbt jedes Land einmal und ändert ihre Meinung nie. Eine frühe Wahl kann ein späteres Land mit allen vier Farben umgeben zurücklassen, und der einzige Ausweg ist dann eine fünfte. Backtracking würde stattdessen zurückgehen und die früheren Entscheidungen ändern.
Gilt der Satz auch auf anderen Flächen?
Auf einer Kugel ja: Sie verhält sich wie die Ebene. Auf einem Torus, der Oberfläche eines Donuts, brauchen manche Karten sieben Farben, und sieben reichen immer aus, wie Percy Heawood zeigte. Wenn Länder aus mehreren getrennten Teilen bestehen dürfen, wie ein Staat mit Kolonien, reichen vier Farben nicht mehr aus.
Wird etwas an einen Server gesendet?
Nein. Die Karte, die Färbungsmethoden und die Prüfung laufen in Ihrem Browser. Ihre Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor