Der Name Erde-Mond-Problem ist ein wenig bombastisch für eine Aufgabe, die nichts weiter ist als eine Verallgemeinerung des bekannten Vierfarbenproblems: Irgendwann in der Zukunft haben die Nationen die Erde einschließlich der Weltmeere so unter sich aufgeteilt, daß jeder von ihnen ein zusammenhängendes – nasses, trockenes oder gemischtes – Stück Erdoberfläche gehört. Außerdem hat jede Nation noch einen Teil des Mondes in Besitz genommen. Es ist eine Landkarte von Erde und Mond zusammen nach den üblichen Prinzipien zu färben: Das irdische und das lunare Territorium jedes Landes sollen die gleiche Farbe erhalten, und nirgends sollen zwei aneinandergrenzende Länder mit der gleichen Farbe eingefärbt werden. Wie viele Farben würden in jedem Falle dafür ausreichen, einerlei wie auf beiden Himmelskörpern die Grenzen verlaufen?

Dieses Problem, das ich schon im September 1993 in dieser Rubrik beschrieben habe, klingt ziemlich weit hergeholt und künstlich. Ein typisches nutzloses Produkt aus dem Elfenbeinturm der Wissenschaften?

Keineswegs. In einem Übersichtsartikel zu derartigen Fragen beschreibt Joan P. Hutchinson vom Macalester College in St. Paul (Minnesota) auch eine Anwendung auf das Testen von gedruckten Schaltkreisen, die Forscher bei den AT&T Bell-Laboratorien in Murray Hill (New Jersey) entdeckt haben. Einzelheiten müssen einer späteren Folge vorbehalten bleiben. Diesen Monat werde ich Ihnen zunächst etwas über Landkarten, Reiche und Graphen erzählen.

Eine Landkarte im mathematischen Sinne ist eine Zusammensetzung von Gebieten in der Ebene oder einer anderen Fläche, zum Beispiel einer Kugeloberfläche. Jedes Gebiet besteht aus einem einzigen, zusammenhängenden Teil der Fläche und grenzt entlang gewisser Kurven an andere Gebiete.

Ein Graph ist ein Diagramm aus Punkten, den sogenannten Knoten oder Ecken des Graphen, die durch Linien, die Kanten des Graphen, miteinander verbunden sind. Wo genau in der Ebene die Knoten und die Kanten liegen, ist für die Graphentheorie nicht relevant.

Graphen sind einfacher, aber auch abstrakter als Landkarten. Jede Landkarte läßt sich durch einen Graphen repräsentieren, indem man jedem Land eine Ecke zuordnet und zwei solche Ecken genau dann durch eine Kante verbindet, wenn die zugehörigen Länder ein Stück Grenze gemeinsam haben (Bild 1). Nehmen Sie als seine Knoten die Hauptstädte der Länder und als seine Kanten Straßen, welche die Hauptstädte benachbarter Länder miteinander verbinden und dabei die gemeinsame Grenze kreuzen. Das ist der Kartengraph. Er zeigt, welche Länder aneinandergrenzen, aber nicht deren Gestalt – und auf die kommt es beim Einfärben auch gar nicht an.

Ein Graph heißt planar, wenn man ihn – die Knoten geeignet anordnend – in der Ebene zeichnen kann, ohne daß sich irgendwelche Kanten kreuzen. Der Kartengraph einer Landkarte in der Ebene ist offenbar planar. Das gilt überraschenderweise auch für eine Landkarte auf einer Kugel oder auf mehreren unverbundenen Kugeln und Ebenen, wie beim Erde-Mond-Problem. Wieso?

Aus einer Landkarte auf der Kugel kann man auf die übliche Weise einen Kartengraph machen, der seinerseits kreuzungsfrei auf die Kugeloberfläche gezeichnet werden kann. Stellen wir uns diese jetzt als Luftballon vor, schneiden ein kleines Loch hinein, das keine Ecke oder Kante des Graphen trifft, und erweitern das Loch, indem wir die Gummihaut immer weiter dehnen, bis sie platt auf dem Tisch liegt. Den Graphen haben wir dabei mitgenommen und so kreuzungsfrei in die Ebene gebracht.

Wenn sich die Karte auf mehrere Kugeloberflächen verteilt, schaffen wir jeden Teil auf diese Weise in die Ebene, und zwar so, daß die Teile sich nicht überlappen. Der so entstehende ebene Graph ist dann nicht zusammenhängend – er besteht aus mehreren unverbundenen Teilgraphen, einer von jeder Kugelfläche –, aber das kommt bei Graphen häufiger vor.

Ein besonders wichtiger Graph ist der vollständige Graph Kn. Er hat n Ecken, und je zwei Ecken sind durch eine Kante miteinander verbunden. Wenn n gleich 5 oder größer ist, dann ist Kn nicht planar (Bild 2).

Eine Landkarte – in der Ebene, auf einer Kugel, mehreren Kugeln oder beliebigen Flächen – heißt k-färbbar, wenn man ihre Gebiete mit höchstens k Farben so färben kann, daß benachbarte Gebiete – das heißt solche mit einer gemeinsamen Grenze – verschiedene Farben erhalten. (Gebiete, die nur in einem oder endlich vielen Punkten aneinandergrenzen, gelten nicht als benachbart.) Die entsprechende Eigenschaft für Graphen ist analog definiert: Ein Graph heißt k-färbbar, wenn sich seine Ecken mit höchstens k Farben so färben lassen, daß durch eine Kante verbundene Ecken stets verschiedenfarbig sind.

Man sieht leicht, daß eine Landkarte genau dann k-färbbar ist, wenn ihr Kartengraph k-färbbar ist. Man versieht einfach jede Hauptstadt, also jede Ecke des Graphen, mit der Farbe des zugehörigen Landes. Die kleinste Zahl k an Farben, mit der sich das bewerkstelligen läßt, nennt man die chromatische Zahl des Graphen. Der Vierfarbensatz läßt sich also folgendermaßen formulieren: Die chromatische Zahl jedes planaren Graphen ist höchstens 4. Offenbar ist die chromatische Zahl des Graphen Kn gleich n: Da jede Ecke mit jeder anderen verbunden ist, können keine zwei Ecken die gleiche Farbe tragen.

Eine mit dem Erde-Mond-Problem verwandte Frage hat 1890 der britische Mathematiker Percy John Heawood (1861 bis 1955) gestellt. Dabei spielt sich alles nur auf der Erde ab, aber jedes Land gehört zu einem Kolonialreich aus höchstens m Ländern, und alle zu einem Reich gehörenden Länder müssen dieselbe Farbe bekommen. Aneinandergrenzende Länder müssen wieder verschieden gefärbt werden; man nimmt an, daß nie zwei benachbarte Länder zum selben Reich gehören. Eine solche Karte heißt eine m-Reichskarte (der englische Name "m-pire" ist ein Sprachspiel mit empire, Reich). Heawood bewies, daß sich jede m-Reichskarte für mž2 mit höchstens 6m Farben färben läßt, einerlei wie viele Reiche die Welt enthält.

Zu einer m-Reichskarte gibt es – wie zu jeder Landkarte – den zugehörigen Kartengraphen, der für jedes Land eine Ecke enthält. Nur läßt sich nicht mehr jede zulässige Färbung dieses Graphen in eine Färbung der m-Reichskarte verwandeln; die Bedingung, daß zum selben Reich gehörende Ecken dieselbe Farbe erhalten, könnte ja verletzt sein. Mit dieser Zusatzbedingung ist bei Graphen nur schwer umzugehen. Man ändert statt dessen lieber die Konstruktion des Graphen ab, so daß die Färbungsregeln automatisch das richtige Ergebnis liefern.

Und das geht so: Der m-Reichsgraph zu einer m-Reichskarte hat nicht mehr für jedes Land eine Ecke, sondern nur noch für jedes Reich. Nicht mehr jede Provinzhauptstadt, sondern nur noch jede Reichshauptstadt ergibt einen Knoten. Zwei von ihnen werden genau dann durch eine Kante verbunden, wenn irgendwo in den zugehörigen Reichen zwei Länder aneinandergrenzen. Der m-Reichsgraph ist also so etwas wie ein Konfliktgraph: ein Knoten für jeden Kaiser und eine Kante zu jedem anderen Kaiser, mit dem er in Gebietsstreitigkeiten geraten könnte.

Der m-Reichsgraph entsteht aus dem gewöhnlichen Kartengraphen, indem man alle zu einem Reich gehörenden Knoten miteinander identifiziert, das heißt an dieselbe Stelle zeichnet. Dabei ergeben sich oft mehrere Kanten zwischen denselben zwei Knoten, von denen man alle bis auf eine wegläßt. Alle so miteinander identifizierten Knoten müssen dieselbe Farbe erhalten; also ist die zur Färbung eines m-Reichs benötigte Anzahl von Farben gleich der chromatischen Zahl des zugehörigen m-Reichsgraphen.

Im Jahre 1983 haben Bradley W. Jackson von der Staatsuniversität in San Jose und Gerhard Ringel von der Universität von Kalifornien in Santa Cruz auf diesem Wege bewiesen, daß sich die Zahl 6m in Heawoods Satz nicht verkleinern läßt. Dazu zeigten sie, daß man für jedes m eine Welt aus m-Reichen konstruieren kann, deren zugehöriger Reichsgraph der vollständige Graph K6m ist. Da man für K6m mit Sicherheit 6m Farben braucht, gibt es eine m-Reichskarte, die sich nicht mit weniger als 6m Farben färben läßt.

Die eingangs angesprochene Erde-Mond-Karte ist eine spezielle 2-Reichskarte mit einer merkwürdigen Geometrie: Sie zerfällt in zwei Teile – Erde und Mond –, und diese Trennung zerschneidet zugleich jedes der 2-Reiche. Entsprechend ist der zugehörige 2-Reichsgraph aus zwei disjunkten planaren Graphen zusammengesetzt (Bild 3; die rundliche Form hat nichts mit Erde und Mond zu tun, sie läßt sich nur einfacher zeichnen).

Dieser Graph (Bild 3c) muß nun nicht mehr planar sein. Er ist allerdings fast planar, denn nach Konstruktion lassen sich seine Kanten in zwei Klassen zerlegen, deren jede einen planaren Graphen auf der ursprünglichen Knotenmenge bildet – nämlich den Graphen der Erd- beziehungsweise der Mondkarte.

Man sagt, ein solcher Graph habe die Dicke 2. Allgemein schreibt man einem Graphen die Dicke d zu, wenn seine Kanten sich in d – aber nicht weniger – Teilmengen gruppieren lassen, die jede einen planaren Graphen bilden.

Da jede Erde-Mond-Karte aus zwei planaren Karten besteht – eine für den Mond und eine für die Erde –, hat der zugehörige Graph die Dicke 2. Umgekehrt läßt sich jeder Graph der Dicke 2 durch eine Erde-Mond-Karte realisieren (wobei es Gebiete geben kann, die von keinem Reich beansprucht werden).

Jeder Erde-Mond-Graph ist insbesondere ein 2-Reichsgraph; also ist er nach dem Satz von Heawood mit höchstens 12 Farben färbbar. Es könnten allerdings auch weniger Farben ausreichen, denn es handelt sich um sehr spezielle 2-Reiche, so daß das Argument von Jackson und Ringel möglicherweise nicht zutrifft. Nicht jede 2-Reichskarte läßt sich als Erde-Mond-Karte realisieren: Man könnte beispielsweise gezwungen sein, zwei Länder eines 2-Reichs auf die Erde zu legen.

Tatsächlich läßt sich keiner der bekannten 2-Reichsgraphen, für die man 12 Farben braucht, als Erde-Mond-Karte darstellen. Es besteht also die Möglichkeit, daß man jeden Erde-Mond-Graphen mit weniger als 12 Farben färben kann. Beispielsweise sind die vollständigen Graphen K9, K10, K11 und K12 sämtlich 2-Reichsgraphen, aber alle haben Dicke 3 und können folglich keine Erde-Mond-Graphen sein. Die Dicke des Kn beträgt 3 für n=9 und 10, in allen anderen Fällen (n+7)/6, nach unten auf ganze Zahlen gerundet.

Der Graph in Bild 3c ist der vollständige Graph K8. Da er als Erde-Mond-Graph darstellbar ist (vergleiche Bild 3), braucht man für das Erde-Mond-Problem mindestens acht Farben. Rolf Sulanke von der Humboldt-Universität Berlin hat die untere Grenze auf 9 verbessert, indem er zeigte, daß der Graph in Bild 4 Dicke 2 und chromatische Zahl 9 hat. Im übrigen ist die Lösung des Erde-Mond-Problems noch offen: Man weiß nur, daß 9, 10, 11 oder 12 die richtige Antwort ist.

Nun wollen Sie vielleicht über Erde-Mond-Mars-Karten nachdenken, bei denen jedes Reich aus drei Ländern besteht, eins auf jedem Himmelskörper. Solche Karten sind Sonderfälle von 3-Reichskarten, und 3-Reichsgraphen haben stets Dicke 3.

Das war bis jetzt vielleicht ganz lustig, hatte aber keine erkennbare praktische Relevanz. Die – mit Anwendung auf das Testen elektrischer Schaltkreise – folgt im nächsten Heft.

Literaturhinweis

Coloring Ordinary Maps, Maps of Empires, and Maps of the Moon. Von Joan P. Hutchinson in: Mathematics Magazine, Band 66, Heft 4, Seiten 211 bis 225, Oktober 1993


Aus: Spektrum der Wissenschaft 5 / 1998, Seite 12
© Spektrum der Wissenschaft Verlagsgesellschaft mbH