Topologische Landkarte

Topologische Landkarte i​st ein Terminus a​us dem mathematischen Teilgebiet d​er Topologischen Graphentheorie. Der Terminus h​at Bedeutung insbesondere i​m Zusammenhang m​it Untersuchungen z​u Färbungsproblemen u​nd hier n​icht zuletzt i​m Zusammenhang m​it dem Vier-Farben-Satz u​nd verwandten mathematischen Lehrsätzen.

Definitionen und Bezeichnungen

• Eine topologische Landkarte ${\displaystyle {\mathfrak {K}}}$ auf einer Fläche ${\displaystyle F\subset \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 2)}$ ist ein Tripel ${\displaystyle {\mathfrak {K}}=({\mathfrak {L}},{\mathfrak {G}},E)}$, wobei ${\displaystyle {\mathfrak {L}}}$ und ${\displaystyle {\mathfrak {G}}}$ zwei endliche Mengensysteme von Teilmengen von ${\displaystyle F}$ sind und ${\displaystyle E\subset F}$ ebenfalls eine endliche Menge darstellt.
  • Dabei ist ${\displaystyle {\mathfrak {G}}}$ die Kantenmenge eines topologischen Graphen in ${\displaystyle F}$ und ${\displaystyle E}$ ist die zugehörige Knotenmenge.
  • ${\displaystyle E}$ besteht genau aus denjenigen Punkten von ${\displaystyle F}$, welche für eine der Jordankurven ${\displaystyle g\in {\mathfrak {G}}}$ als Anfangs- oder Endpunkt auftreten.
  • Das Mengensystem ${\displaystyle {\mathfrak {L}}}$ besteht genau aus den Wegzusammenhangskomponenten der Komplementmenge ${\displaystyle F\setminus \bigcup {\mathfrak {G}}}$.
• Man bezeichnet hierbei jedes Element von ${\displaystyle {\mathfrak {L}}}$ als Land, jedes Element von ${\displaystyle {\mathfrak {G}}}$ als Grenzlinie und jedes Element von ${\displaystyle E}$ als Ecke der topologischen Landkarte ${\displaystyle {\mathfrak {K}}}$.
• Ein Punkt ${\displaystyle x\in \mathbb {R} ^{d}}$ ist Randpunkt eines zu der Landkarte gehörenden Landes ${\displaystyle L}$, wenn er dem relativen topologischen Abschluss ${\displaystyle {\overline {L}}\cap F}$ von ${\displaystyle L}$ in ${\displaystyle F}$ angehört.
• Zwei Länder ${\displaystyle L_{1}}$ und ${\displaystyle L_{2}}$ von ${\displaystyle {\mathfrak {K}}}$ heißen benachbart oder Nachbarländer, wenn unter den Grenzlinien von ${\displaystyle {\mathfrak {K}}}$ eine vorkommt, welcher ganz aus Randpunkten sowohl von ${\displaystyle L_{1}}$ als auch von ${\displaystyle L_{2}}$ besteht.
• Eine zu einer ganzen Zahl ${\displaystyle n>0}$ gegebene Abbildung ${\displaystyle f\colon \,{\mathfrak {L}}\to \{1,\ldots ,n\}}$ nennt man ${\displaystyle n}$-Färbung.
  • Die Elemente von ${\displaystyle \{1,\ldots ,n\}}$ bezeichnet man (in Einklang mit den Gepflogenheiten der Graphentheorie) als Farben.
  • Eine ${\displaystyle n}$-Färbung ${\displaystyle f\colon \,{\mathfrak {L}}\to \{1,\ldots ,n\}}$ heißt zulässig, wenn je zwei benachbarten Ländern vermöge ${\displaystyle f}$ stets zwei verschiedene Farben zugeordnet sind.
  • Gestattet eine topologischen Landkarte ${\displaystyle {\mathfrak {K}}}$ auf ${\displaystyle F}$ für eine ganze Zahl ${\displaystyle n>0}$ eine zulässige ${\displaystyle n}$-Färbung, jedoch keine zulässige Färbung mit weniger als ${\displaystyle n}$ Farben, so nennt man diese ganze Zahl ${\displaystyle n}$ die chromatische Zahl von ${\displaystyle {\mathfrak {K}}}$ und bezeichnet sie mit ${\displaystyle \chi ({\mathfrak {K}})}$.
  • Bildet man über alle topologischen Landkarten auf ${\displaystyle F}$ das Supremum   ${\displaystyle \sup\{\chi ({\mathfrak {K}}):{\mathfrak {K}}\;{\text{topologische Landkarte auf F}}\}}$   aller zugehörigen chromatischen Zahlen und ist diese ganze Zahl ${\displaystyle <\infty }$, so ist dies die chromatische Zahl von ${\displaystyle F}$. Sie wird mit ${\displaystyle \chi (F)}$ bezeichnet.[1]

Anmerkung

• Die untersuchten Flächen sind in aller Regel Flächen ${\displaystyle F\subset \mathbb {R} ^{d}\;(d=2,3,4)}$ .

Bedeutende Lehrsätze

• Satz von Weiske: Ist ${\displaystyle F}$ der ${\displaystyle \mathbb {R} ^{2}}$ oder die Einheitssphäre ${\displaystyle S^{2}}$, so gibt es keine Landkarte mit fünf paarweise benachbarten Ländern.[2]
• Zweifarbensatz: Ist ${\displaystyle F}$ ein Rechteck und sind darüber hinaus die Grenzlinien einer gegebenen topologischen Landkarte ${\displaystyle {\mathfrak {K}}}$ so beschaffen, dass jede von ihnen nur zwischen Randpunkten des Rechtecks verläuft oder eine innerhalb des Rechtecks verlaufene geschlossene Jordankurve darstellt, so existiert zu einer solchen topologischen Landkarte ${\displaystyle {\mathfrak {K}}}$ stets eine zulässige ${\displaystyle 2}$-Färbung.[3]
• Vier-Farben-Satz: Ist ${\displaystyle F}$ der ${\displaystyle \mathbb {R} ^{2}}$ oder die Einheitssphäre ${\displaystyle S^{2}}$, so existiert zu jeder topologischen Landkarte auf ${\displaystyle F}$ eine zulässige ${\displaystyle 4}$-Färbung.
• Fünf-Farben-Satz: Ist ${\displaystyle M}$ der ${\displaystyle \mathbb {R} ^{2}}$ oder die Einheitssphäre ${\displaystyle S^{2}}$, so existiert zu jeder topologischen Landkarte auf ${\displaystyle F}$ eine zulässige ${\displaystyle 5}$-Färbung.
• Sechsfarbensatz für das Möbiusband: Das Möbiusband ${\displaystyle M}$ hat die chromatische Zahl ${\displaystyle {\chi }(M)=6}$ und es besitzt auf ihm jede topologische Landkarte eine zulässige ${\displaystyle 6}$-Färbung, wobei es unter diesen auch mindestens eine gibt, die nicht mit fünf Farben auskommt.[4]
• Heawoodsche Ungleichung: Ist für eine ganze Zahl ${\displaystyle p>0}$   ${\displaystyle H_{p}}$ eine geschlossene orientierbare Fläche vom Geschlecht ${\displaystyle p}$ und ist dabei ${\displaystyle m_{p}=\lfloor {\frac {7+{\sqrt {1+48p}}}{2}}\rfloor }$,[5] so existiert zu jeder topologischen Landkarte auf ${\displaystyle H_{p}}$ eine zulässige ${\displaystyle m_{p}}$-Färbung. Mit anderen Worten: Für jede derartige Fläche ${\displaystyle H_{p}}$ erfüllt die chromatische Zahl ${\displaystyle {\chi }(H_{p})}$ die Ungleichung ${\displaystyle {\chi }(H_{p})\leq m_{p}}$.[6]
  • Es gilt sogar für ein solches ${\displaystyle H_{p}}$ stets die Identitätsgleichung ${\displaystyle {\chi }(H_{p})=m_{p}}$.[7]
  • Insbesondere hat der Volltorus ${\displaystyle H_{1}}$ die chromatische Zahl ${\displaystyle {\chi }(H_{1})=7}$ und es besitzt auf ihm jede topologische Landkarte eine zulässige ${\displaystyle 7}$-Färbung, wobei unter diesen auch solche vorkommen, die nicht mit sechs Farben auskommen.

Anmerkungen zu den Lehrsätzen

• Der Satz von Weiske geht auf den Philologen Benjamin Gotthold Weiske (1783–1836), einen Freund des Mathematikers August Ferdinand Möbius, zurück. Die Urheberschaft für dieses Resultat wurde von dem Geometer Richard Baltzer bei Durchsicht des Nachlasses von Möbius herausgefunden. Als Baltzer über den Satz von Weiske und seine Geschichte in einem Vortrag im Jahre 1885 berichtete, setzte er dann jedoch den Irrtum in die Welt, dass sich mit Weiskes Satz bereits der Vierfarbensatz als leichte Folgerung ergibt. Richtig ist dagegen, dass im Gegensatz zu der Darstellung von Baltzer Weiskes Satz allein eine leichte Herleitung des Fünffarbensatzes ermöglicht. Der Irrtum von Baltzer wurde erst im Jahre 1959 von dem Geometer Harold Scott MacDonald Coxeter abschließend beseitigt.[2]
• Der Vierfarbensatz wird heute zwar von vielen, jedoch keineswegs von allen Mathematikern als bewiesen angesehen.[8]
• Dass in der heawoodschen Ungleichung sogar das Gleichheitszeichen zu gelten hat, wurde schon von Percy John Heawood vermutet und konnte dann im Jahre 1968 von den beiden Mathematikern Gerhard Ringel und John William Theodore Youngs abschließend bewiesen werden.[7]

Das Fadenproblem

Das Fadenproblem besteht i​n der Frage n​ach der Lösung folgender Aufgabe:

Es soll - wenn möglich - für eine gegebene natürliche Zahl ${\displaystyle m\geq 3}$ diejenige kleinste natürliche Zahl ${\displaystyle \gamma (m)}$ bestimmt werden, für welche auf einer geschlossenen orientierbaren Fläche ${\displaystyle H_{\gamma (m)}}$ des Geschlechtes ${\displaystyle \gamma (m)}$ beliebig ausgewählte unterschiedliche Punkte ${\displaystyle p_{1},p_{2},\ldots ,p_{m}\in H_{\gamma (m)}}$ immer paarweise durch einfache Jordankurven in der Weise verbunden werden können, dass all diese Jordankurven einander nie überkreuzen und höchstens in den ausgewählten Punkten ${\displaystyle p_{1},p_{2},\ldots ,p_{m}}$ treffen.[9]

Wie s​ich zeigt, i​st das Fadenproblem lösbar u​nd dabei ergibt s​ich die Formel

${\displaystyle \gamma (m)=\lceil {\frac {(m-3)(m-4)}{12}}\rceil \;(m\in \mathbb {N} \;,\;m\geq 3)}$.[10]

Dabei zeigt sich weiter, dass die Gültigkeit dieser Formel auch die Gültigkeit der heawoodschen Identitätsgleichung ${\displaystyle {\chi }(H_{p})=m_{p}\;(p\in \mathbb {N} \;,\;p>0)}$ nach sich zieht.[11]

Literatur

• Rudolf Fritsch: Der Vierfarbensatz. Geschichte, topologische Grundlagen und Beweisidee. Unter Mitarbeit von Gerda Fritsch. BI Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zürich 1994, ISBN 3-411-15141-2 (MR1270673).
• Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik (= de Gruyter Lehrbuch). 2., völlig neu bearbeitete und erweiterte Auflage. de Gruyter, Berlin (u. a.) 2004, ISBN 3-11-016727-1.
• K. P. Müller, H. Wölpert: Anschauliche Topologie. Eine Einführung in die elementare Topologie und Graphentheorie (= Mathematik für die Lehrerausbildung). B. G. Teubner Verlag, Stuttgart 1976, ISBN 3-519-02709-7.
• Gerhard Ringel: Das Kartenfärbungsproblem. In: Konrad Jacobs (Hrsg.): Selecta Mathematica III (= Heidelberger Taschenbücher. Band 86). Springer Verlag, Berlin, Heidelberg, New York 1971, ISBN 3-540-05333-6 (MR0543809).
• Lutz Volkmann: Fundamente der Graphentheorie. Springer Verlag, Wien, New York 1996, ISBN 3-211-82774-9 (MR1392955).
• Klaus Wagner: Graphentheorie (= BI-Hochschultaschenbücher. 248/248a). Bibliographisches Institut, Mannheim (u. a.) 1970, ISBN 3-411-00248-4.

Einzelnachweise

1. Die chromatische Zahl ${\displaystyle \chi (F)}$ ist zu unterscheiden von der Euler-Charakteristik von ${\displaystyle F}$, obwohl für beide Zahlen derselbe griechische Buchstabe als Bezeichner auftritt.
2. Rudolf Fritsch: Der Vierfarbensatz. 1994, S. 25–26, 128
3. K. P. Müller, H. Wölpert: Anschauliche Topologie. 1976, S. 67
4. Müller, Wölpert, op. cit., S. 148–149
5. ${\displaystyle \lfloor {\cdot }\rfloor }$ ist die Gaußklammerfunktion.
6. Gerhard Ringel: Das Kartenfärbungsproblem. in: Selecta Mathematica III 1971, S. 30 ff., 45–47
7. Ringel, op. cit., S. 31
8. Siehe Vier-Farben-Satz#Kritik!
9. Ringel, op. cit., S. 32
10. ${\displaystyle \lceil \cdot \rceil }$ ist die Aufrundungsfunktion.
11. Ringel, op. cit., S. 32–33