Topologische Graphentheorie

Die Topologische Graphentheorie ist ein Teilgebiet der Mathematik, welches an der Nahtstelle zwischen der Graphentheorie und Topologie gelegen ist und dabei beeinflusst wird durch verwandte Gebiete wie Geometrische Graphentheorie, Geometrie, Knotentheorie und Gruppentheorie. Sie behandelt Problemstellungen im Zusammenhang mit der Frage der Darstellung von Graphen in topologische Räumen. Die Entwicklung der Topologischen Graphentheorie wurde maßgeblich bestimmt und vorangetrieben durch das Vier-Farben-Problem.

Begriff der Darstellung

Definition

Unter einer Darstellung eines gegebenen Graphen ${\displaystyle G}$ versteht man einen Graphenisomorphismus von diesem auf einen Graphen ${\displaystyle G^{'}}$, für den folgende Bedingungen erfüllt sind:

1. Die Vereinigungsmenge aus Knoten- und Kantenmenge von ${\displaystyle G^{'}}$ ist als Unterraum in einem topologischen Raum ${\displaystyle X^{'}}$ enthalten.
2. Jede Kante von ${\displaystyle G^{'}}$ ist eine Jordan-Kurve in ${\displaystyle X^{'}}$  .
3. In ${\displaystyle G}$ sind ein Knoten ${\displaystyle v}$ und eine Kante ${\displaystyle e}$ dann und nur dann inzident, wenn in ${\displaystyle G^{'}}$ der zu ${\displaystyle v}$ gehörige Punkt ${\displaystyle v^{'}}$ Anfangs- oder Endpunkt der zu ${\displaystyle e}$ gehörigen Jordankurve ${\displaystyle e^{'}}$ ist.
4. In ${\displaystyle G}$ sind zwei Knoten ${\displaystyle v_{1}}$ und ${\displaystyle v_{2}}$ genau dann adjazent, wenn diejenigen ${\displaystyle G^{'}}$-Jordankurven, welche ${\displaystyle {v_{1}}^{'}}$ und ${\displaystyle {v_{2}}^{'}}$ miteinander verbinden, exakt den mit ${\displaystyle v_{1}}$ und ${\displaystyle v_{2}}$ inzidenten ${\displaystyle G}$-Kanten zugehören.

Bezeichnungen und Sprechweisen

• Einen Graphen ${\displaystyle G^{'}}$ der genannten Art nennt man einen topologischen Graphen.
• Liegt ein Graphenisomorphismus wie oben vor, so spricht man von einer Einbettung des Graphen ${\displaystyle G}$ in den topologischen Raum ${\displaystyle X^{'}}$.
• Verkürzend spricht man in Bezug auf ${\displaystyle G^{'}}$ ebenfalls von der Darstellung des Graphen ${\displaystyle G}$ und sagt dann auch, dass ${\displaystyle G^{'}}$ den gegebenen Graphen ${\displaystyle G}$ realisiere bzw. repräsentiere (o. ä.).
• Den oben genannten Unterraum bezeichnet man in der Regel auch mit ${\displaystyle G^{'}}$.
• Ist ${\displaystyle G^{'}\subset \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 1)}$ und sind dabei sämtliche Kanten von ${\displaystyle G^{'}}$ Strecken, die sich zudem gar nicht oder höchstens in einem einzigen Punkt von ${\displaystyle G^{'}}$ schneiden, so nennt man ${\displaystyle G^{'}}$ eine geradlinige Darstellung von ${\displaystyle G}$ . Eine derartige geradlinige Darstellung bezeichnet man als auch als Streckengraphen.

Topologische Graphentheorie im engeren Sinne

Im engeren Sinne und in der Hauptsache finden die Untersuchungen der Topologischen Graphentheorie in der folgenden Ausgangssituation statt:

1. ${\displaystyle G}$ ist ein endlicher schlichter Graph.
2. Der topologische Raum ${\displaystyle X^{'}}$ ist eine Fläche im d-dimensionalen euklidischen Raum ${\displaystyle \mathbb {R} ^{d}\;(d{\text{ ganzzahlig}}\;,\;d\geq 2)}$ . Dabei liegt in aller Regel der ${\displaystyle \mathbb {R} ^{d}\;(d=2,3,4)}$ vor.
3. Die Kanten der Darstellung ${\displaystyle G^{'}}$ sind einfache Jordankurven in ${\displaystyle X^{'}}$ .
4. ${\displaystyle G^{'}}$ ist ein wegzusammenhängender Raum.
5. Die Knotenmenge von ${\displaystyle G^{'}}$ hat mit jeder einzelnen Kante von ${\displaystyle G^{'}}$ genau deren Anfangs- und Endpunkt gemeinsam.
6. Zwei verschiedene Kanten von ${\displaystyle G^{'}}$ schneiden sich entweder gar nicht oder höchstens in einem einzigen Knoten von ${\displaystyle G^{'}}$.
7. Die zu ${\displaystyle G^{'}}$ gehörige topologische Landkarte besitzt nur endlich viele Länder, von denen entweder gar keines oder nur ein einziges unbeschränkt ist.

Ist unter den genannten Bedingungen ${\displaystyle G^{'}}$ sogar ein ebener Graph, also ${\displaystyle G^{'}\subset X^{'}=\mathbb {R} ^{2}}$  , so spricht man von einer ebenen Darstellung.

Zentrale Fragen der Topologischen Graphentheorie

In der Topologischen Graphentheorie werden die folgenden Fragen behandelt:

• In welche topologischen Räume ${\displaystyle X^{'}}$ lässt sich ein gegebener Graph ${\displaystyle G}$ einbetten und welche sind deren Merkmale?
  • Speziell: In welche Flächen ${\displaystyle F^{'}\subseteq \mathbb {R} ^{d}}$ lässt sich ein gegebener Graph einbetten und welche sind deren Merkmale (etwa Geschlecht, Orientierbarkeit)?
    • Frage der Plättbarkeit: Für welche Graphen ${\displaystyle G}$ lässt sich eine ebene Darstellung ${\displaystyle G^{'}}$ finden und wie lassen sich diese – etwa kombinatorisch oder gruppentheoretrisch – beschreiben,?
• In welche euklidischen Räume ${\displaystyle \mathbb {R} ^{d}}$ lässt sich ein gegebener Graph ${\displaystyle G}$ mit geradliniger Darstellung ${\displaystyle G^{'}\subset \mathbb {R} ^{d}}$ einbetten?
  • Speziell: Welche Graphen ${\displaystyle G}$ haben eine geradlinige Darstellung als ${\displaystyle d}$-dimensionaler Polytopgraph, lassen sich also mit einem Streckengraphen ${\displaystyle G^{'}}$ realisieren, dessen Knoten und Kanten exakt aus den Ecken und Kanten eines konvexen Polytops im ${\displaystyle \mathbb {R} ^{d}}$ bestehen?
    • Speziell: Welche Graphen ${\displaystyle G}$ haben eine geradlinige Darstellung als ${\displaystyle 3}$-dimensionaler Polyedergraph, lassen sich also mit einem Streckengraphen ${\displaystyle G^{'}}$ realisieren, dessen Knoten und Kanten exakt aus den Ecken und Kanten eines konvexen Polyeders im ${\displaystyle \mathbb {R} ^{3}}$ bestehen?

Bedeutende Sätze der Topologischen Graphentheorie

Die Topologische Graphentheorie umfasst eine Fülle von bedeutenden Sätzen, von denen an erster Stelle der eulersche Polyedersatz, der Satz von Kuratowski sowie der Vier-Farben-Satz und seine ihm verwandten bedeutenden Sätze über Topologische Landkarten zu nennen sind. Hervorzuheben sind auch drei weitere klassische Theoreme der Topologischen Graphentheorie, nämlich der steinitzsche Fundamentalsatz der konvexen Typen, der Dreifarbensatz von Grötzsch und der tuttesche Satz zum Hamiltonkreisproblem.

In den Zusammenhang mit dem Vierfarbensatz lässt sich auch der Satz von Wagner und Fáry bringen, welcher grundlegend für dessen Beweis ist, da durch ihn erst die geradlinige Darstellung plättbarer Graph gesichert wird. Im gleichen Zusammenhang erwähnenswert ist ein anderer Satz, der die entsprechende Frage der räumlichen geradlinigen Darstellung in Bezug auf alle endlichen schlichten Graphen anspricht und diese umfassend und positiv beantwortet. Der Satz besagt nämlich:^[1]

• Jeder endliche schlichte Graph besitzt eine geradlinige Darstellung im ${\displaystyle \mathbb {R} ^{3}}$.

Literatur

• Lowell W. Beineke, Robin J. Wilson (Hrsg.): Graph Connections. Relationships between Graph Theory and other Areas of Mathematics (= Oxford Lecture Series in Mathematics and its Applications. Band 5). Clarendon Press, Oxford 1997, ISBN 0-19-851497-2 (MR1634542).
• Lowell W. Beineke, Robin J. Wilson (Hrsg.): Topics in Topological Graph Theory (= Encyclopedia of Mathematics and its Applications. Band 128). Cambridge University Press, Cambridge 2009, ISBN 978-0-521-80230-7 (MR2581536).
• 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).
• Jonathan L. Gross, Thomas W. Tucker: Topological Graph Theory (= Wiley Interscience Series in Discrete Mathematics and Optimization). John Wiley & Sons, New York 1987, ISBN 0-471-04926-3, S. 201–224 (MR0898434).
• Jonathan L. Gross, Jay Yellen (Hrsg.): Handbook of Graph Theory (= Discrete Mathematics and its Applications). CRC Press, Boca Raton (u. a.) 2004, ISBN 1-58488-090-2, S. 610–786.
• Branko Grünbaum: Polytopal Graphs in: Studies in Graph Theory. Part II (Hrsg. D. R. Fulkerson) (= Studies in Mathematics. Band 12). Mathematical Association of America, Washington, DC 1975, ISBN 0-88385-112-1, S. 201–224 (MR0406868 MR0392630).
• Rudolf Halin: Graphentheorie I (= Erträge der Forschung. Band 138). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 (MR0586234).
• Nora Hartsfield, Gerhard Ringel: Pearls in Graph Theory. A Comprehensive Introduction. Academic Press, Boston (u. a.) 1990, ISBN 0-12-328552-6 (MR1069559).
• Dénes König: Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Akademische Verlagsgesellschaft, Leipzig 1936.
• Gerhard Ringel: Map Color Theorem (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Band 209). Springer Verlag, Berlin / Heidelberg / New York 1974 (MR0349461).
• H. Sachs: Kommentierender Anhang (Teil 12) in: D. Kőnig: Theorie der endlichen und unendlichen Graphen (Hrsg. H. Sachs) (= Teubner-Archiv zur Mathematik. Band 6). BSB B. G. Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4, S. 326–327 (MR0886676).
• 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.
• Arthur T. White: Graphs, Groups and Surfaces (= North-Holland Mathematics Studies. Band 8). 2. Auflage. North-Holland Publishing Company, Amsterdam 1984, ISBN 0-444-87643-X. MR0780555

Einzelnachweise

1. Rudolf Halin: Graphentheorie I . 1980, S. 39