Der Vierfarbensatz erklärt

Im Jahr 1852 bemerkte ein junger Mathematiker beim Färben einer Karte der englischen Grafschaften, dass vier Farben auszureichen schienen, um benachbarte Grafschaften auseinanderzuhalten. Konnte das für jede mögliche Karte gelten? Die Frage wurde zu einem der berühmtesten Probleme der Mathematik, zog einen bekannten falschen Beweis an, der elf Jahre lang Bestand hatte, und wurde schließlich 1976 auf eine Weise gelöst, die veränderte, was Mathematiker als Beweis akzeptieren.

Eine Karte unregelmäßiger Länder, mit vier Farben so gefärbt, dass keine zwei Nachbarn dieselbe Farbe haben
Eine Karte unregelmäßiger Länder, mit vier Farben so gefärbt, dass keine zwei Nachbarn dieselbe Farbe haben

Die Frage

Francis Guthrie, ein ehemaliger Student von Augustus De Morgan, fragte, ob sich jede Karte so mit vier Farben färben lässt, dass Länder mit gemeinsamer Grenze verschiedene Farben bekommen. Zwei Regeln machen die Frage präzise. Länder müssen zusammenhängend sein, jedes aus einem Stück, und Länder, die sich nur in einem einzigen Punkt treffen, zählen nicht als Nachbarn. Drei Farben reichen offensichtlich nicht immer aus, denn ein Land, das von einem Ring aus drei anderen umgeben ist, die sich alle berühren, braucht eine vierte. Die Frage ist, ob jemals eine fünfte nötig ist.

Karten als Graphen

Markieren Sie in jedem Land einen Punkt und ziehen Sie eine Linie zwischen zwei Punkten, wann immer ihre Länder eine gemeinsame Grenze haben. Das Ergebnis ist ein Graph, und weil die Karte auf einem flachen Blatt liegt, lassen sich die Linien ohne Kreuzungen zeichnen: Der Graph ist planar. Die Karte zu färben heißt, die Knoten dieses Graphen so zu färben, dass die Enden jeder Kante verschieden sind. Die kleinste Anzahl von Farben, die dafür genügt, ist die chromatische Zahl, und der Vierfarbensatz besagt, dass kein planarer Graph eine chromatische Zahl über vier hat.

Kempes gescheiterter Beweis

1879 veröffentlichte der Rechtsanwalt und Mathematiker Alfred Kempe einen Beweis. Seine geschickte Idee, heute Kempe-Ketten genannt, besteht darin, zwei Farben entlang einer zusammenhängenden Kette von Ländern zu vertauschen, um dort eine Farbe freizumachen, wo sie gebraucht wird. Der Beweis galt elf Jahre lang als richtig, bis Percy Heawood 1890 eine Lücke fand. Heawoods Reparatur bewies ein schwächeres Ergebnis: Fünf Farben reichen immer aus. Kempes Ketten überlebten und wurden zu einem Werkzeug im späteren Beweis.

Warum fünf leicht ist

Jeder planare Graph hat einen Knoten mit höchstens fünf Nachbarn; das folgt aus dem eulerschen Polyedersatz, der einen planaren Graphen mit n Knoten auf höchstens 3n − 6 Kanten beschränkt. Entfernen Sie einen solchen Knoten, färben Sie den Rest der Karte mit demselben Argument und setzen Sie den Knoten wieder ein. Verwenden seine Nachbarn weniger als fünf Farben, ist eine frei. Verwenden sie alle fünf, macht ein Tausch entlang einer Kempe-Kette immer eine frei. Mit vier Farben kann derselbe Tausch scheitern, und genau das ist die Lücke, die Kempe übersah.

Der Computerbeweis

1976 bewiesen Kenneth Appel und Wolfgang Haken an der University of Illinois den Satz. Sie zeigten, dass jede Karte mindestens eine von 1.936 Konfigurationen aus einer unvermeidbaren Menge enthält und dass jede Konfiguration reduzibel ist: Eine kleinste Karte, die fünf Farben bräuchte, könnte sie nicht enthalten. Die Prüfung der Reduzibilität kostete mehr als tausend Stunden Rechenzeit, viel zu viel, um sie von Hand nachzuprüfen. Viele Mathematiker waren mit einem Beweis, den kein Mensch vollständig lesen konnte, nicht glücklich, und die Debatte über computergestützte Beweise begann.

Wolfgang Haken, der 1976 zusammen mit Kenneth Appel an der University of Illinois den Vier-Farben-Satz bewies.
Wolfgang Haken, der 1976 zusammen mit Kenneth Appel an der University of Illinois den Vier-Farben-Satz bewies.

Einfachere Beweise und vollständige Verifikation

1996 veröffentlichten Neil Robertson, Daniel Sanders, Paul Seymour und Robin Thomas einen systematischeren Beweis mit 633 Konfigurationen, ebenfalls per Computer geprüft, aber leichter nachzuprüfen. 2005 formalisierten Georges Gonthier und Benjamin Werner den gesamten Beweis im Beweisassistenten Coq, sodass ein kleines, vertrauenswürdiges Programm jeden logischen Schritt prüft. Heute ist der Vierfarbensatz eines der am gründlichsten verifizierten Ergebnisse der Mathematik.

Färbungsalgorithmen

Eine Vierfärbung einer gegebenen Karte zu finden geht in der Praxis schnell, doch die kleinste Farbanzahl für einen allgemeinen Graphen zu finden ist schwer: Zu entscheiden, ob drei Farben genügen, ist NP-vollständig. Zu den praktischen Verfahren gehören die gierige Färbung in der Reihenfolge abnehmenden Grades, DSATUR, das als Nächstes den am stärksten eingeschränkten Knoten färbt, und die Backtracking-Suche, die Möglichkeiten durchprobiert und sie rückgängig macht, wenn sie nicht weiterkommt. Graphenfärbung plant Prüfungen ohne Überschneidungen, vergibt Funkfrequenzen so, dass benachbarte Sender sich nicht stören, und teilt in Compilern Register zu.

Selbst ausprobieren

Öffnen Sie den Kartenmaler zum Vierfarbensatz, um Karten mit 4 bis 120 Ländern zu erzeugen, sie von Hand mit vier Farben zu färben und zu sehen, wie Konflikte rot erscheinen. Lassen Sie gierige Färbung, DSATUR oder Backtracking die Karte Schritt für Schritt lösen, zeigen Sie den Graphen der benachbarten Länder an und prüfen Sie, wie viele Farben die Karte wirklich mindestens braucht.

Häufig gestellte Fragen

Hilft der Satz Kartografen?

Kaum. Echte Karten werden der Übersichtlichkeit halber meist mit mehr Farben gefärbt, und sie enthalten Ozeane, Seen und Länder aus mehreren Teilen, die der Satz nicht abdeckt. Seine Bedeutung ist mathematisch: Er trieb die Entwicklung der Graphentheorie voran und warf die Frage auf, was als Beweis gilt.

Was ist eine Kempe-Kette?

Nehmen Sie zwei Farben, etwa Rot und Blau, und ein rot gefärbtes Land. Seine Kempe-Kette ist die Menge aller roten und blauen Länder, die man von ihm aus erreicht, indem man nur über rote und blaue Nachbarn geht. Vertauscht man Rot und Blau in der ganzen Kette, bleibt die Färbung gültig, und es kann eine Farbe für ein Land neben der Kette frei werden.

Warum widerlegen Länder aus mehreren Teilen den Satz?

Wenn ein Land aus getrennten Gebieten bestehen darf, die alle dieselbe Farbe haben müssen, ist der Nachbarschaftsgraph nicht mehr planar, und es lassen sich Karten bauen, die bei zwei Teilen pro Land jede beliebige Anzahl von Farben bis 12 brauchen, wie Heawood in seinem Imperienproblem untersuchte.

Warum erzeugt der Kartenmaler Karten aus Punkten?

Jedes Land ist der Bereich des Quadrats, der einem zufälligen Punkt näher liegt als jedem anderen, ein Voronoi-Diagramm. So entstehen realistisch aussehende Karten aus konvexen Ländern, und zwei Länder sind genau dann Nachbarn, wenn ihre Bereiche ein Stück Grenze teilen, was die App exakt berechnet.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Kartenmaler zum Vierfarbensatz öffnen