Vierfarbensatz - ein einfacher Beweis

Der Vierfarbensatz - ein einfacher Beweis

Übersicht

Der Vierfarbensatz besagt, dass eine Landkarte (oder allgemein eine in Gebiete unterteilte ebene Fläche) sich mit 4 Farben so einfärben lässt, dass benachbarte Gebiete nie die gleiche Farbe haben, also immer gut unterscheidbar sind.

(Benachbart meint, dass zwei Gebiete eine gemeinsame Grenzlinie haben.
Gebiete, die sich nur in einem Punkt berühren, gelten nicht als benachbart.)

Wir geben zunächst anhand von vereinfachenden Darstellungen der Nachbarschaftsverhältnisse einen geometrisch-abstrakten Beweis, dass 4 Farben ausreichen. Dann untersuchen wir verschiedene Typen von Nachbarschaften (Ringen) und wie man diese möglichst systematisch einfärben kann. Mit dieser Kenntnis formulieren wir einen sehr einfachen Algorithmus, der - von einem Gebiet ausgehend - benachbarte Gebiete und damit sukzessive eine ganze Landkarte "konfliktfrei" mit 4 Farben einfärbt.

Die Grundidee des Beweises

Wir gehen von folgender Beobachtung aus:

- In einem Dreieck berühren sich alle Ecken gegenseitig (d.h. sind mit Kanten verbunden)
- In einem Viereck trifft das nicht mehr zu - nur je 2 Ecken berühren sich gegenseitig
- Allgemein berührt bei zyklisch angeordneten Dingen (Ringen) jedes Ding nur seinen
Vorgänger und seinen Nachfolger, und nur je 2 Dinge berühren sich gegenseitig.

Anwendung auf eine Landkarte

Was hat obige Beobachtung mit einer Landkarte zu tun? Nun, ganz einfach: Betrachten wir auf einer Landkarte ein Gebiet, so bilden alle seine Nachbarn einen Ring um dieses, die Ringnachbarn.
Das kann man (egal wie wirr die Landkarte aussehen mag) optisch übersichtlich veranschaulichen. Das Bild unten rechts repräsentiert jedes Gebiet einer Landkarte mit 3 Nachbarn ringsum:

Geometrisch-abstrakter Beweis des Vierfarbensatzes

Im Bild oben grenzt jedes der 4 Gebiete an jedes andere. Jedes Ringgebiet ist mit jedem benachbart (wie oben die Eckpunkte beim Dreieck) und gleichzeitig mit der Mitte. Das beweist, dass mindestens 4 Farben nötig sind, um jede Karte "konfliktfrei" einzufärben. (Die Zahlen repräsentieren Farben.)

Die folgenden Beispiele zeigen aber, dass nie mehr als 4 Gebiete benachbart sein können:

Bild links: Hat ein Gebiet 4 Nachbarn ringsum, so sind sogar immer nur je 3 Gebiete gegenseitig benachbart (gelb), die Mitte und 2 sich berührende Ringfelder. (Man vergleiche oben das Quadrat). Gegenüberliegende Ringfelder sind nicht benachbart (können deshalb dieselbe Farbnummer haben).

Bild Mitte: Man kann zwar durch Umformen eines Ringfelds ("Ranke") dieses mit dem gegenüberliegenden Ringfeld verbinden (Letzteres muss dann zur Abgrenzung eine neue Farbe erhalten. hier Farbe 3). Dann hat man 4 gegenseitig benachbarte Felder (gelb). Jetzt ist aber das gelbe Feld 2 rings umschlossen, es kann also nicht mit einem weiteren Ringfeld verbunden werden.

Bild rechts: Das ist auch der Fall, wenn ein Ringfeld eine Klammer bildet, die den Ring zwei mal berührt: Die eingeschlossenen Felder (gelbe 1 und 2) können nicht mit weiteren verbunden werden.

Für alle Gebiete mit 4 oder mehr Nachbarn ist die Situation ähnlich. Man stelle sich dazu vor,
in obigen Bildern würden Ringfelder radial zweigeteilt (evtl. mehrfach):

- - Wird ein weißes Feld geteilt, so verändert das die Nachbarschaftsverhältnisse zwischen den gelben (alle miteinander benachbarten) Feldern überhaupt nicht. Und weil kein weißes Feld alle gelben Felder berührt (dann wäre es gelb), kann auch kein Teilfeld davon alle gelben Felder berühren.

- - Wird ein gelbes Ringfeld geteilt, so gilt:
- Wenn eine Situation wie im Bild oben links vorliegt (keine Ranken oder Klammern):
Nur die Hälfte des gelben Ringfelds, die an das andere gelbe Ringfeld grenzt, bleibt gelb.
Die andere Hälfte wird weß, weil sie die Verbindung zu letzterem verliert.

- Wenn eine Situation wie in den Bildern oben Mitte oder rechts vorliegt (Ranke oder Klammer):
Wird ein äußeres (an ein weißes grenzendes) gelbes Ringfeld geteilt, so verliert sein äußerer Teil die Verbindung zum mittleren gelben Ringfeld, wird also weiß. Wird ein inneres gelbes Ringfeld geteilt, so hat eine Hälfte keine Verbindung mehr zu einem der gelben Ringnachbarn, wird also weiß.

Wir haben also gezeigt:
1) Jedes Gebiet kann als Zentrum eines Ringes aufgefasst werden.
2) Es gibt 3 Typen von Nachbarschaft von Ringfeldern: Direkte Nachbarschaft und Verbindung durch Ranken oder Klammern. Weitere Möglichkeiten gibt es nicht. Für diese Typen ist bewiesen, dass maximal 3 Ringfelder (mit Zentrum also maximal 4 Gebiete) alle gegenseitig benachbart sein können.

-- Das beweist, dass nie mehr als 4 Gebiete alle gegenseitig benachbart sein können
-- Daraus folgt, dass 4 Farben ausreichen, um jede Landkarte "konfliktfrei" einzufärben
Denn man kann, von einem Gebiet ausgehend, jedem Nachbargebiet eine Farbe geben,
die noch kein Nachbar hat.

- - - Damit ist der Vierfarbensatz bewiesen - - -

[ Man könnte auf die Idee kommen, im Bild oben Mitte die zwei Felder mit Farbe 2 zu verbinden durch einen Kanal durchs Zentrum oder zwischen dem Zentrum und dem Feld mit Farbe 3, oder mittig durchs Feld 3. Aber das würde eine neue Landkarte schaffen, bei der jedem Gebiet samt Nachbarschaft wieder eine der obigen 3 Situationen entspricht - andere gibt es nicht.]

Ringtypen und Färbestrategien

Wir gruppieren Ringe nach ihrer Struktur und zeigen, wie man sie möglichst systematisch einfärben kann. Wir untersuchen zunächst Ringe mit einfacher Struktur (jedes Ringfeld grenzt - außer an die Mitte - nur an seinen Vorgänger und Nachfolger) und mit unterschiedlicher Anzahl von Feldern:

Isoliertes Gebiet (von 1 Nachbargebiet umringt): Dieser Fall ist völlig problemlos.
Hat das innere Gebiet z.B. die Farbe 4, so kann der Ring darum jede beliebige andere Farbe (hier 1, 2, oder 3) haben. Für Gebiete, die außen an den Ring angrenzen, stehen alle Farben außer der Ringfarbe zur Verfügung, auch die Farbe der Mitte. Denn an ein Gebiet dürfen durchaus mehrere Gebiete der gleichen Farbe angrenzen, nur dürfen diese nicht benachbart sein.
Der einfeldrige Ring um ein isoliertes Gebiet wird genauso weiterbehandelt wie ein einzelnes Gebiet, wie wenn das innere Gebiet überhaupt nicht vorhanden wäre.
In eine bereits gefärbte Landkarte kann man nachträglich ein isoliertes Gebiet eingefügen, ohne etwas umzufärben außer dem neuen Gebiet.

Gebiet mit gerader Anzahl Nachbarn: Man beginnt an einem Ringfeld, geht ringsum und färbt die Ringfelder abwechselnd mit 2 Farben (im Bild Farben 1 und 2).

Gebiet mit ungerader Anzahl Nachbarn: Man beginnt an einem Ringfeld, geht ringsum und färbt die Ringfelder abwechselnd mit 2 Farben Das letzte Feld erhält eine andere Farbe (die letzte unbenutzte), damit es nicht dieselbe Farbe hat wie das zuerst gefärbte Feld, an das es angrenzt (im Bild Farbe 3 statt 1).

Prinzipell gilt also für Ringe mit einfacher Struktur:
- Hat ein Gebiet eine gerade Anzahl Nachbarn, so erhalten diese abwechselnd die Farben 1 und 2
- Hat ein Gebiet eine ungerade Anzahl Nachbarn, so erhalten diese abwechselnd die Farben 1 und 2
aber der (zyklisch) letzte Nachbar erhält Farbe 3 (statt 1).

Unterbrochener Ring: Bei einer nicht unendlichen Landkarte gibt es Gebiete, die am Rande (oder in einer Ecke) liegen. Deren Nachbarn kann man durch einen unterbrochenen Ring "beziehungstreu" darstellen, wie folgendes Beispiel zeigt:

Hier reichen immer 2 Farben aus, um den Ring einzufärben, auch bei ungerader Anzahl Nachbarn des Zentrums. Denn das (zyklisch gesehen) erste und letze Ringfeld berühren sich nicht, können also die gleiche Farbe haben (im Bild Farbe 1).

Ringe mit komplizierter Struktur: Ranken und Klammern
Hier grenzt mindestens 1 Ringfeld - außer an die Mitte und seinen Vorgänger und Nachfolger - noch an ein weiteres Feld des Rings. Hier gibt es 2 Typen von Verbindungen:

Bild links: Ring mit Ranke: Ein Ringfeld berührt außer seinem unmittelbaren Vorgänger
und Nachfolger weitere Ringfelder, aber nur ein Mal die Mitte
Bild rechts: Ring mit Klammer: Ein Ringfeld berührt an 2 Stellen die Mitte

Bei einem Ring können Ranken und Klammern mehrfach auftreten, auch miteinander kombiniert: Ranke (linkswendig) + Ranke (rechtswendig), Klammer + Klammer(n) [Doppel- bzw. Mehrfach-klammer], Klammer(n) + Ranke. Das ist aber kein Problem. Auch solche Ringe lassen sich konfliktfrei mit 4 Farben einfärben. Meist sogar sehr systematisch (wenn sich Ranken / Klammern nicht gegenseitig berühren, und wenn nicht durch vorher gefärbte Felder der Spielraum eingeengt ist):
Beispiel: Das Zenttrum erhält Farbe 4, alle Ranken und Klammern Farbe 3. Die sonstigen Ringfelder werden abwechselnd mit Farbe 1 und 2 gefärbt (wobei optimalerweise das im Drehsinn erste Feld innerhalb einer Ranke oder Klammer Farbe 1 erhält).

Fazit: Alle Ringtypen (außer solchen mit sich berührenden Ranken / Klammern) lassen sich systematisch einfärben - wenn man bei ihnen beginnt. Wenn bereits Ringfelder oder äußere Nachbarfelder gefärbt sind, ist die Farbgebung eingeschränkt und deshalb meist unsystematischer.

Von einem Gebiet zum nächsten

Hat man den Ring um ein bestimmtes Gebiet eingefärbt, so nimmt man irgendein Feld dieses Ringes als neues Zentrum. Dann färbt man dessen Umgebung. Man geht dabei prinzipiell genauso vor wie beim vorigen Gebiet
Zu beachten ist aber: Das neue Zentrum, seine Nachbarn auf dem alten Ring und das alte Zentrum sind bereits eingefärbt, Man muss also von deren Farben ausgehend die noch ungefärbten Felder um das neue Zentrum färben.

Der Algorithmus

Da nie mehr als 4 Gebiete alle gegenseitig benachbart sein können, reichen also 4 Farben aus, um eine Landkarte konfliktfrei zu färben, Das leisten folgende sehr einfache Algorithmen:

Algorithmus 1: super einfach, aber total unstrukturiert

1) Wähle 1 Gebiet. Färbe es
2) Wähle irgendeinen ungefärbten Nachbarn Gib ihm eine Farbe, die noch kein Nachbar hat
3) Gehe zu 2

Algorithmus 2: ringorientiert

1) Wähle 1 Gebiet als Zentrum, färbe es
2) gehe ringsum alle Nachbarn des Zentrums (Ringfelder) durch und gib allen ungefärbten
eine Farbe, die noch kein Nachbar hat
3) Wähle irgendein Ringfeld als neues Zentrum
4) Gehe zu 2

Beide Algorithmen enden, wenn die ganze Karte gefärbt ist. Je nach Ablauf des Färbens kann es - besonders am Rand der Karte - nötig sein, bei einem weiter entfernten Gebiet weiterzumachen. Dieses muss jedoch unbedingt an ein bereits gefärbtes Gebiet angrenzen, da es sonst zu Konflikten kommen kann - siehe das folgende Beispiel mit den Schachbrettern.

Obiger Algorithmus ist für Menschen leicht durchführbar. Er ist auch leicht als einfaches Computerprogramm darstellbar. Hierfür muss natürlich die Landkarte als Datenstruktur vorliegen. Diese muss alle Gebiete enthalten mit Angabe aller Nachbarn. Für die Verarbeitung ist noch bei jedem Gebiet die Angabe der Farbe nötig (Farben 1-4; Farbe 0 = "noch nicht gefärbt").

Färbestrategien 2

Beim Färben einer Karte hat man die freie Wahl des Startgebietes und einen Spielraum, welche Nachbarn man zuerst färbt. Man darf aber immer nur von 1 Gebiet aus fortschreiten, nie von 2 oder mehr. Denn sonst kann es beim Zusammenwachsen der bereits gefärbten Verbunde zu Konflikten kommen. Das läßt sich einfach veranschaulichen:

Ein Feld von 8 x 8 Quadraten läßt sich - an einer Ecke beginnend - leicht schachbrettartig einfärben (Bild oben links). Diagonal gegenüberliegende Eckquadrate werden dabei gleich gefärbt.
Würde man aber an einer Ecke mit einem schwarzen und der diagonal gegenüberliegenden Ecke mit einem weißen Quadrat beginnen und zeilenweise einfärben, würden in der Mitte gleichfarbige Quadrate aneinander grenzen (Bild oben rechts).

Man hat (zumindest am Anfang) einen Spielraum bei der Farbauswahl. Diesen kann man nutzen, um eine Karte möglichst übersichtlich zu gestalten (was wir oben bei den Ringtypen versucht haben). Dazu drei Beispiele:

- Im Beispiel links alternieren die Nachbarn des Zentrums in 2 Farben - das ist übersichtlich
- Im mittleren Beispiel sind gegenüberliegende Ringfelder gleich gefärbt
- Das rechte Beispiel hat eine völlig unsystematische Färbung

Außer der Übersichtlichkeit kann man beim Färben weitere Ziele verfolgen, z.B. die Hervorhebung von Gebieten mit vielen Nachbarn. Dies durch Färbung der Zentren z.B. in Rot (wenn möglich) und durch Färbung der Nachbarn wie im Beispiel oben links. Oder man versucht, durch die Karte möglichst auffällige senkrechte und / oder waagrechte Linien von Gebieten gleicher Farbe zu ziehen (die natürlich immer von einem Gebiet anderer Farbe unterbrochen sein müssen). Hier spielt auch die Größe der Gebiete sowie ihre Form und Ausrichtung eine Rolle. Das erinnert etwas an das Go-Spiel.
Hier tut sich hier ein Zweig der künstlichen Intelligenz auf, dessen Verwendungsmöglichkeiten noch nicht abzusehen sind.

Darstellung durch Rechtecke statt Ringe

Die Darstellung eines Gebiets als Kreis und seiner Nachbarn als Ring(segmente) darum ist sehr übersichtlich. Aber sie lässt sich nicht fortführen. Das heißt, wenn man ein Ringsegment als neues Zentrum wählt, ist es eben kein Kreis, und seine Nachbarn bilden keinen Ring (außer man malt eine neue Grafik). Die ungefärbten äußeren Nachbarn des Ringsegments können nur als Segmente eines zweiten, äußeren Rings dargestellt werden ähnlich Iris-Koordinaten, was aber unübersichtlicher ist.

Diesen Nachteil vermeidet die Darstellung aller Felder als Rechtecke oder abgewinkelte Rechtecke, basierend auf einem quadratischen Muster. Beispiel:

Hier sieht man ein Gebiet (weiß, inneres Quadrat), das 3 Nachbarn hat (blau, grün, rot, im mittleren Quadrat), die 6, 6, 4 Nachbarn haben (im inneren, mittleren und äußeren Quadrat).

Geschichte

Darüber informiert ausführlich der Wikipedia-Artikel "Vierfarbensatz". Das Problem wurde angeblich 1852 zum ersten Mal formuliert. 1879 gab es einen Beweisversuch, der aber 11 Jahre später als fehlerhaft erkannt wurde. Es gab weitere Beweisversuche, die auch oft erst spät widerlegt wurden. Bei einem jüngeren Beweisversuch 1976 überprüfte ein Computer rund 1500 problematische Konfigurationen. Der Beweis umfasste 50 Seiten Text mit Abbildungen, 85 weitere Seiten mit 2500 Abbildungen, 400 Seiten Mikrofilm mit Beweisdetails und die Ergebnisse der Computerrechnung. [2]
Er wird deshalb von manchen Mathematikern angezweifelt.
Zur Zeit gibt es keinen allgemein anerkannten Beweis.

Literatur

1) Wikipedia Artikel "Vierfarbensatz", Download vom 18. 9. 2021
2) Keith Devlin, "Muster der Mathematik", Spektrum Akademischer Verlag, Heidelberg 2002
3) Michael Thiel, "Vier-Farben-Satz Ein logischer Beweis", BoD-Verlag, Norderstedt
4) Weitere mathematische Werke



Homepage  Leonhard Heinzmann               Erstveröffentlichung:  4. 10. 2021           Stand:  7. 3. 2022