Direkt zum Inhalt

Lexikon der Mathematik: Landkarte

ein ebener Graph zusammen mit seinen Ländern.

Eine Färbung einer Landkarte mit k Farben ist eine Abbildung f der Menge aller Länder der Landkarte in die Menge {1, 2,…,k}, der Menge der Farben, so, daß je zwei benachbarte Länder L1 und L2 verschiedene Farben erhalten, d. h. f(L1) ≠ f(L2).

Zwei Länder müssen also lediglich dann verschiedene Farben erhalten, wenn eine Kante des Graphen ganz zu ihren beiden Rändern gehört, und nicht, wenn die Ränder nur eine Ecke gemeinsam haben. Mit den Färbungen von Landkarten befaßt sich der Vier-Farben-Satz.

Der Begriff der Landkarte läßt sich analog auch für kreuzungsfreie Einbettungen (Einbettung eines Graphen) in orientierbare und nichtorientierbare Flächen beliebigen Geschlechts definieren.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte