Einträge mit dem Tag ‘Landkarten’

Es wird Zeit, sich noch einmal mit Landkarten zu beschäftigen. Wir haben bereits gesehen, daß ein Tuschekasten für Kartographen mindestens vier Farben enthalten muß. Außerdem braucht man dann, wenn für jedes Land eine Liste von Farben gebildet werden soll, höchstens mehr, niemals aber weniger Farben.
Noch offen ist aber die Frage, ob ich einen Tuschekasten zusammenstellen kann, mit dem jeder Kartograph für alle Karten auskommt.

Behauptung

Ich behaupte: ja, das geht. Fünf Farben reichen aus.
Mehr noch: es genügt sogar, wenn für jedes Land eine Liste mit fünf Farben zur Verfügung steht. (Wir hatten ja gesehen, daß das ein schwierigeres Problem ist.)

Induziert

Wie beweist man das am besten? Das Verfahren der vollständigen Induktion bietet sich hier an: Eine Karte mit nicht mehr als fünf Ländern kann ich natürlich immer mit fünf Farben zeichnen (Induktionsanfang). Wenn ich jetzt aus einer Karte mit n Ländern auf geschickte Weise ein Land eliminieren könnte, wäre ich schon am Ziel. Aber wie stellt man das an?
Als erstes greifen wir tief in die Trickkiste und fördern etwas zutage, das sich Warum einfach, wenn's auch kompliziert geht? nennt: wir beweisen schlichtweg etwas, das schwieriger (stärker) ist, und machen uns die Arbeit dadurch einfacher. Das hört sich seltsam an; der Grund liegt aber darin, daß wir uns sozusagen auf der Leiter von Sprosse zu Sprosse hangeln. Wenn wir alle Sprossen etwas höher einbauen, müssen wir zwar mit jedem Schritt etwas höher hinauf als bei unserer Originalleiter, aber wir starten ja auch jeden Schritt von einer höheren Sprosse aus.

Wirklich schwieriger wird nur die erste Sprosse; die ist aber bei Induktionsbeweisen kein wirkliches Problem. Zugegeben, ein bißchen hinkt die Analogie schon: wenn ich die Behauptung stärker mache, so kann der Beweis tatsächlich gleich schwer bleiben (wie bei der Leiter), er kann aber auch schwieriger oder einfacher werden. Hier wird er erfreulicherweise einfacher.

Weiter im Text

Weiter wollen wir annehmen, daß es höchstens Drei-Länder-Ecke gibt — aber keine Vier-, Fünf-, oder Noch-mehr-Länder-Ecke.

Wenn wir es doch einmal mit einer solchen Karte zu tun haben sollten, wollen wir einfach die Grenzen ein bißchen verschieben. Das ist nicht schlimm, weil das Problem dadurch nur schwieriger wird, die neue Lösung also auf jeden Fall auch Lösung des ursprünglichen Problems ist.

Behaupten kann man viel

Sehen wir uns eine Karte an, dann gibt es dort immer einen Ring von äußeren Ländern; hier sind es z.B. Washington, Oregon, Kalifornien, Arizona, New Mexico, Texas und so weiter.
Staaten der USA
Seien nun zwei benachbarte Länder dieses Rings bereits eingefärbt; jedes weitere Land auf dem Ring stelle eine Liste mit (mindestens) drei Farben bereit; jedes Land aus dem Inneren stelle eine Liste mit mindestens fünf Farben bereit.
Dann — so unsere Behauptung — können wir die gesamte Karte unter Benutzung dieser Listen einfärben.

Stärke

Diese Behauptung hat mit unserem ursprünglichen Ziel — der Einfärbung der Karte unter Benutzung von Fünfer-Farblisten — nicht mehr viel zu tun. Sie ist aber stärker: Wir behaupten jetzt, daß nur die inneren Länder noch Fünfer-Listen bereitstellen sollen; die Länder auf dem Ring liefern nur noch Dreier-Listen, zwei geben ihre Farbe sogar fest vor. Wenn wir die Karte unter diesen Bedingungen färben können, kommen wir mit Fünfer-Listen auf jeden Fall hin.

Aller Anfang ist leicht

Wenn nur drei Länder auf der Karte sind, so reichen uns die Farben auf jeden Fall: zweie sind ja schon gefärbt, und das dritte bietet uns eine Liste mit drei Farben an; egal, welche Farben durch die beiden Nachbarn belegt sind, eine bleibt immer frei.

Ein kleiner Schritt für einen Kartographen

Erinnern wir uns an die Vorgehensweise beim Induktionsschritt: wir müssen die Behauptung für eine Karte mit n Ländern beweisen, dürfen aber annehmen, sie sei für n-1 Länder, ja sogar für alle möglichen Karten mit weniger als n Ländern bereits bewiesen. Wir müssen also unsere große Karte auf eine (oder zwei) kleinere Karten zurückführen.
Nehmen wir nun an, zwei Länder aus dem äußeren Ring haben eine gemeinsame Grenze, die aber selbst nicht nach außen stößt; der Ring hat dann die Form einer Acht. Zaire und der Sudan sind ein Beispiel.
Zaire und Sudan
Jetzt können wir die Karte in zwei Teile zerlegen: die eine enthält Zaire, den Sudan, und alle weiter nördlich gelegenen Länder; die andere enthält ebenfalls Zaire und den Sudan, dazu aber die südlicheren Länder. Für Zaire und den Sudan vergeben wir jetzt je eine Farbe fest (etwa grün und rot); alle anderen Länder auf dem alten Ring haben Listen mit drei Farben, die inneren Länder deren fünf — so war ja die Voraussetzung. Dann gilt das aber auch für jede der beiden neuen "halben" Karten. Da diese kleiner sind, dürfen wir die Behauptung als bereits bewiesen ansehen. Beide kleinen Karten sind also mit den vorgegebenen Farben einfärbbar, und damit auch die gesamte Karte.
Das war es auch schon — mehr hatten wir gar nicht behauptet.

Unachtsam

Was nun, wenn der äußere Ring nicht die Form einer Acht hat?
Dann müssen wir die Zahl der Länder eben auf andere Art verringern. Nehmen wir die Karte der USA von oben, dann hat der äußere Ring dort nicht die Form einer Acht.
Staaten der USA
Angenommen, Washington sei bereits blau gefärbt. Auf dem Ring hat dieser Staat zwei Nachbarn: Idaho und Kalifornien. Angenommen, Idaho sei ebenfalls gefärbt (nach Annahme muß es ein Nachbar Washingtons auf dem Ring sein; es bleiben also nur CA oder ID). Dann entfernen wir jetzt probehalber Kalifornien von der Karte. Dadurch wird Nevada neu in den äußeren Ring aufgenommen — bei einer anderen Karte könnte natürlich auch eine ganze Reihe von Staaten dazukommen.
Nach Annahme hat Kalifornien (mindestens) eine Liste von drei Farben zur Verfügung gestellt; davon müssen mindestens zwei von Blau verschieden sein (sagen wir, Rot und Gelb). Diese beiden Farben streichen wir jetzt von der Farbliste Nevadas. Da die Liste vorher mindestens fünf Farben enthielt, bleiben also jetzt noch drei. Das heißt aber, daß die neue Karte (ohne Kalifornien) alle Voraussetzungen erfüllt, um vorschriftsmäßig gefärbt zu werden. Wenn wir jetzt noch eine Farbe für Kalifornien finden, sind wir fertig. Das ist aber leicht:
Nevada kann weder rot noch gelb sein, da wir diese Farben von der Liste gestrichen haben. Washington ist schon blau, und Arizona kann entweder Rot oder Gelb (oder eine andere Farbe) erhalten, aber nicht beide; deswegen bleibt eine der beiden Farben Rot und Gelb für Kalifornien.

Das war's, die Karte ist gefärbt!

Und sonst?

Im Falle der Farblisten ist Fünf tatsächlich die kleinste Zahl, die man finden kann. Margit Voigt hat ein Beispiel gefunden für eine Karte, die sich mit Vierer-Farblisten nicht immer einfärben läßt. Sie hat 238 Länder eingezeichnet.

Wenn es nur um den Tuschekasten geht, reichen dagegen sogar vier Farben. Der Beweis dafür ist allerdings leider viel zu lang und kompliziert für dieses Blog.

Der obige Beweis folgt übrigens dem Buch von Martin Aigner und Günther Ziegler, in dem sich — etwa auf Vordiplomniveau — eine ganze Reihe schöner Beweise findet.

Kommentare deaktiviert für Bunte Karten III

Beim letzten Mal haben wir gesehen, daß es Landkarten gibt, die mit weniger als vier Farben nicht gezeichnet werden können. Mit anderen Worten: wenn es eine Zahl n gibt, so daß mit n Farben beliebige Landkarten gezeichnet werden können, dann muß n≥4 sein.

Befindlichkeiten

Bevor wir nun untersuchen, ob wir auch eine obere Schranke für n finden können, wollen wir uns noch um einen anderen Aspekt kümmern: Wenn der kaiserliche Kartograph die Farben für die Karte aussucht, dann kann es vorkommen, daß die Landesfürsten mit den ihnen zugedachten Farben nicht zufrieden sind. Der eine hätte lieber Grün als Rot, dem anderen ist das Blau zu dunkel, und so weiter. Stattdessen die Fürsten ihre Farben aussuchen zu lassen, ist aber auch keine gute Idee: nachher müssen alle Länder in Gold dargestellt werden, und man erkennt überhaupt nichts mehr.
Deswegen hat sich der Kartograph folgende Regel ausgedacht: Jeder Landesfürst soll eine Liste mit k Farben, die ihm genehm sind, zusammenstellen. Die endgültige Auswahl der Farben aus diesen Listen nimmt der Kartograph dann selbst vor. Wie muß der Kartograph nun k wählen, damit er die Karte auf jeden Fall zeichnen kann? Wichtig ist dabei natürlich, daß k schon feststehen muß, bevor die Fürsten ihre Farben ausgesucht haben — unabhängig von deren Wahl muß die Karte machbar sein.

Mit und ohne Liste

Klar ist, daß k nicht kleiner als m sein kann, wenn für die vorliegende Karte mindestens m Farben benötigt werden; es wäre ja möglich, daß alle Fürsten zufällig die gleichen Listen abliefern — dann können nicht plötzlich weniger Farben als bei freier Farbwahl (für den Kartographen) nötig sein. Nun liegt der Verdacht nahe, daß k=m sein muß. Wenn alle Fürsten die gleiche Farbauswahl treffen, ist das naheliegend; anderenfalls kommen ja nur noch mehr Farben hinzu. Sechs Listen mit je zwei Farben enthalten zum Beispiel mindestens zwei Farben, es könnten aber auch mehr sein. Und wenn ich die Karte mit (beispielsweise) zwei Farben zeichnen kann, dann sollten sechs Listen mit je zwei Farben ja kein Problem sein. Wie gut, daß der Kartograph noch den kaiserlichen Mathematiker aufgesucht hat, bevor er die Boten zum Einsammeln der Farblisten ausschickte.

Weil unser Kartograph zu den Zeiten lebte, in denen noch gezaubert wurde, kann ich Euch leider keine echten Karten zeigen: sie sind alle durch die lange Zeit und die schädlichen Einflüsse der Zaubersprüche zerfallen. Stattdessen habe ich eine Karte von Obervolta, der Elfenbeinküste, Ghana, Togo, Benin und Atlantis ausgesucht. Na gut, Atlantis hat die Zaubersprüche auch nicht überstanden, da ist jetzt nur noch der Ozean. Das ändert aber an dem Problem nichts. Eine weitere Besonderheit von damals können wir heute nicht mehr sehen: die vier Länder in der Mitte hatten keine gemeinsamen Grenzen, weil die Zauberer für bodenlose Gräben zwischen ihnen gesorgt hatten. Deshalb können wir die Karte ganz einfach mit nur zwei Farben zeichnen:
Atlantis mit vier weiteren Länder
Atlantis und Obervolta werden blau, die anderen vier Länder weiß.

Wie wir — und der kaiserliche Kartograph — oben angenommen haben, sollte es also ausreichen, wenn jeder Landesfürst zwei Farben zur Auswahl angibt. Was aber, wenn das Ergebnis so aussieht?
Listenfärbung für Atlantis
Obervolta will Rot oder Grün, Atlantis Gelb oder Blau, und so weiter. Jetzt haben wir ein Problem: Wir könnten Obervolta rot und Atlantis blau zeichnen, aber dann bleibt für die Elfenbeinküste keine Farbe übrig. Wenn Obervolta grün und Atlantis gelb wird, gibt es das gleiche Problem mit Benin. Die anderen beiden Kombinationen gehen auch nicht, weil dann entweder für Ghana oder Togo keine Farbe mehr bleibt.

Facit

Unsere Vermutung war also falsch: es gibt Karten, die sich mit m Farben vom Kartographen zeichnen lassen, nicht aber dann, wenn jeder Landesfürst eine Liste von m Farben zur Auswahl stellt, obwohl dann ja insgesamt mehr Farben zur Verfügung stehen. Umgekehrt ist aber jede Karte, die mit Farblisten zu je k Einträgen zu zeichnen ist, auch mit k Farben vom Kartographen zu zeichnen.

Kommentare deaktiviert für Bunte Karten II

Auf politischen Landkarten verwendet man gerne Farben, um die einzelnen Staaten voneinander abzugrenzen. Wie viele verschiedene Farben man dafür braucht, hängt natürlich von der Karte, die man zeichnen möchte, ab.
Was aber, wenn ich einen Tuschekasten für Kartographen zusammenstellen möchte? Kann ich so viele Farben in den Kasten packen, daß meine Kunden damit auf jeden Fall auskommen — gleich, welche Karte sie zeichnen wollen?

Wenn zwei Länder schon dann unterschiedliche Farben erhalten sollen, wenn sie nur einen einzigen Punkt gemeinsam haben, dann ist die Antwort nein: im Reich des Tortenkaisers haben alle Königreiche einen Punkt gemeinsam, und deshalb brauchen die kaiserlichen Kartographen immer so viele Farben, wie es Könige gibt:
Tortenland
Wenn unterschiedliche Farben aber nur für solche Länder nötig sind, die tatsächlich ein Stück Grenze gemeinsam haben — vielleicht nur ein paar Meter — dann kann die Sache schon anders aussehen.

Wir haben jetzt zwei Aufgaben vor uns: zum einen wollen wir eine obere Schranke bestimmen, also eine Zahl von Farben, mit der wir auf jeden Fall auskommen; im Moment ist zwar nicht klar, ob so eine Zahl überhaupt existiert, aber davon lassen wir uns natürlich nicht aufhalten.
Zum anderen suchen wir auch eine Zahl von Farben, die (für zumindest eine denkbare Karte) zu klein ist. Diese Zahlen sollen natürlich so dicht wie möglich beieinander liegen, damit wir die kleinste Zahl von Farben, die auf jeden Fall ausreicht, gut eingrenzen können, und nicht übermäßig viele Farben in den Kasten packen.

Für heute soll der einfachere Teil genügen:

Untere Schranke

Um zu zeigen, daß n Farben zu wenig sind (und unser Tuschekasten also mindestens n+1 Farben enthalten muß), genügt es, eine Karte zu finden, die mit n Farben nicht mehr den Regeln entsprechend gezeichnet werden kann. Betrachten wir diese Karte von Luxemburg,
Luxemburg zwischen Belgien, Deutschland und Frankreich
so stellen wir fest, daß wir hier vier Farben benötigen — jedes der vier abgebildeten Länder ist jedem anderen benachbart, und so braucht jedes auch seine eigene Farbe.

Einen Kasten mit nur drei Farben können wir also nicht verkaufen; festzustellen, ob es einen ausreichenden Kasten gibt, und wie groß dieser sein müßte, ist etwas schwieriger; deshalb hat das noch ein paar Tage Zeit.

Kommentare deaktiviert für Bunte Karten I