Archiv vom Januar 20th, 2006

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

Heute in der Mensaschlange:

Sie hat zum erstenmal Käsefondue machen wollen — einen großen Topf mit Fett, und sich gewundert, daß der Käse schlecht schmeckt.

Mjam.

Kommentare deaktiviert für Käsefondue