Topologie von Flächen XV

Kategorie: Technik

Mit wievielen Farben kann man eine Landkarte färben, so daß benachbarte Länder (bzw. Provinzen o.ä.) stets unterschiedliche Farben haben?

Wenn man sich Beispiele anschaut, wird man feststellen, daß (jedenfalls für Landkarten auf der Sphäre oder in der Ebene) 4 Farben immer ausreichen.

Es gibt natürlich auch Beispiele, in denen dies nicht völlig offensichtlich ist. Die folgende Karte benutzt z.B. 5 Farben und es ist auf den ersten Blick nicht klar, wie man mit einer Farbe weniger auskommen kann.

Mit ein wenig Probieren findet man dann aber doch eine Lösung mit 4 Farben.

Als 4-Farben-Problem bezeichnet man die Frage, ob sich jede ebene Landkarte mit 4 Farben färben läßt.

Sehr viel schwieriger ist schon das folgende Beispiel einer Karte mit 110 Ländern. Martin Gardner hatte die linke Karte 1975 in einem Aprilscherzartikel veröffentlicht und behauptet, sie lasse sich nicht mit 4 Farben färben. Erst durch Benutzung des Computeralgebra-Systems Mathematica fand Wagon die rechts abgebildete Färbung mit 4 Farben.

Was hat das Problem des Färbens von Landkarten nun mit dem Problem des Graphfärbens von letzter Woche zu tun? Einer Landkarte kann man einen Graphen zuordnen, indem man sagt, daß die Ecken des Graphen gerade den Ländern der Karte entsprechen sollen, und daß zwei Ecken durch eine Kante verbunden werden, wenn die entsprechenden Länder eine gemeinsame Grenze haben.

Damit wird das Problem der Färbung der Landkarte also auf das Problem der Färbung des entsprechenden Graphen (so daß verbundene Ecken unterschiedliche Farben haben) zurückgeführt.

Für die praktische Herstellung von Landkarten ist die Frage nach der minimalen Anzahl an Farben natürlich irrelevant, weil man dort immer genug Farben zur Verfügung hat und es keinen Grund gibt, sich unbedingt auf 4 Farben beschränken zu wollen (siehe Not for mapmakers).

Die Theorie der Graphfärbungen ist also zwar nicht bei der Erstellung von Landkarten, aber wie in Teil 14 beschrieben in der Registerzuteilung von praktischer Bedeutung.

Die Bedeutung des 4-Farben-Problems in diesem Zusammenhang liegt darin, daß es der Anstoß war für die Entwicklung eines ganzen mathematischen Gebietes, nämlich der Graphentheorie und insbesondere natürlich der Theorie der Graphfärbungen. Diese historische Entwicklung kann man in dem sehr schön geschriebenen Lehrbuch 'Graphentheorie. Eine Entwicklung aus dem 4-Farben-Problem' von M. Aigner nachlesen.

Mehr dazu und zur Lösung des 4-Farben-Problems (1976 durch Appel und Haken) nächste Woche.

Hier noch eine Färbung der deutschen Bundesländer mit 4 Farben. Wegen Thüringen (und seinen Nachbarn) gibt es keine Färbung mit 3 Farben.