×

zbMATH — the first resource for mathematics

Map-colour theorem. (English) JFM 22.0562.02
Das “Map-colour theorem” betrifft die den Kartographen erfahrungsgemäss geläufige Thatsache, dass genau vier Farben hinreichend und notwendig sind, um eine Gebietseinteilung einer Ebene so zu färben, dass zwei verschiedene Gebiete, die in einer Linie an einander grenzen, von verschiedener Farbe sind.
In Bd. II S. 193 des American Journ. (vergl. auch Baltzer, Leipz. Ber. 1885, F. d. M. XVII. 518. Red., JFM 17.0518.01) hat B. Kempe einen Beweis des Theorems mitgeteilt, der sich auf folgende Momente stützt. 1) In jeder mit vier Farben hergestellten Landkarte bilden die an einander grenzenden Gebiete, die nur zwei Farben zeigen, z. B. rot und grün, eine oder mehrere geschlossene Regionen. Vertauscht man in irgend einer dieser Regionen die Farben grün und rot, so entspricht die neue Färbung der Landkarte noch immer den Anforderungen des Satzes. 2) Stossen in einem Punkte vier oder fünf Gebiete an einander, – mehr als fünf zusammenstossende Gebiete brauchen nicht berücksichtigt zu werden –, so kann man durch die eben genannten Vertauschungsprocesse eine solche Färbung der Landkarte erzielen, dass in diesen Gebieten nur drei verschiedene Farben auftreten. Bei vier zusammenstossenden Gebieten genügt eine Vertauschung, bei fünf dagegen sind in manchen Fällen zwei nötig, die zugleich vorgenommen werden müssen.
Der Verfasser führt ein Beispiel an, in dem das Kempe’sche Verfahren nicht zum Ziele führt. Es beruht darauf, dass die gleichzeitige Ausführung von zwei Farbenvertauschungen, von denen jede einzeln für sich zulässig ist, nicht immer möglich zu sein braucht.
Es wird dann weiter auch der Fall mehrfach zusammenhängender Flächen untersucht, sowie der Fall, dass die einzelnen Gebiete aus verschiedenen Teilen bestehen können. Ist \(n\) die Zahl der Gebiete, \(A_n\) die Durchschnittszahl der Grenzlinien für jedes Gebiet, so besteht im einfachen Fall die Gleichung \[ A_n = 6 - \frac{12}{n}\cdot \] Hierfür tritt, wenn jedes Gebiet in \(r\) getrennte Teile zerfällt, die Gleichung \[ rA_n = 6r \left( 1 - \frac 2n \right) \] ein, und wenn es sich um eine \(k\)-fach zusammenhängende Fläche handelt, so ergeben sich die Gleichungen \[ A_n = 6 \left( 1+ \frac kn \right) \quad \text{resp.} \quad rA_n = 6r \left( 1 + \frac kn \right). \] Aus diesen Formeln lässt sich eine obere resp. untere Grenze für die Durchschnittszahl herleiten. Es findet sich, dass beide Zahlen – vom einfachen Fall abgesehen – identisch werden. Im einfachen Fall ergeben sich zunächst die Zahlen 4 und 6, die sich aber sofort durch 4 und 5 ersetzen lassen. Ob 4 wirklich die ausreichende Zahl, lässt der Verfasser in der Schwebe.

PDF BibTeX XML Cite