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 $G$ versteht man einen Graphenisomorphismus von diesem auf einen Graphen $G^{\text{'}}$, für den folgende Bedingungen erfüllt sind:

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

Bezeichnungen und Sprechweisen

• Einen Graphen $G^{\text{'}}$ der genannten Art nennt man einen topologischen Graphen.
• Liegt ein Graphenisomorphismus wie oben vor, so spricht man von einer Einbettung des Graphen $G$ in den topologischen Raum $X^{\text{'}}$.
• Verkürzend spricht man in Bezug auf $G^{\text{'}}$ ebenfalls von der Darstellung des Graphen $G$ und sagt dann auch, dass $G^{\text{'}}$ den gegebenen Graphen $G$ realisiere bzw. repräsentiere (o. ä.).
• Den oben genannten Unterraum bezeichnet man in der Regel auch mit $G^{\text{'}}$.
• Ist $G^{\text{'}}\subset {ℝ}^d(d\text{ ganzzahlig},d\ge 1)$ und sind dabei sämtliche Kanten von $G^{\text{'}}$ Strecken, die sich zudem gar nicht oder höchstens in einem einzigen Punkt von $G^{\text{'}}$ schneiden, so nennt man $G^{\text{'}}$ eine geradlinige Darstellung von $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. $G$ ist ein endlicher schlichter Graph.
2. Der topologische Raum $X^{\text{'}}$ ist eine Fläche im d-dimensionalen euklidischen Raum ${ℝ}^d(d\text{ ganzzahlig},d\ge 2)$ . Dabei liegt in aller Regel der ${ℝ}^d(d=2,3,4)$ vor.
3. Die Kanten der Darstellung $G^{\text{'}}$ sind einfache Jordankurven in $X^{\text{'}}$ .
4. $G^{\text{'}}$ ist ein wegzusammenhängender Raum.
5. Die Knotenmenge von $G^{\text{'}}$ hat mit jeder einzelnen Kante von $G^{\text{'}}$ genau deren Anfangs- und Endpunkt gemeinsam.
6. Zwei verschiedene Kanten von $G^{\text{'}}$ schneiden sich entweder gar nicht oder höchstens in einem einzigen Knoten von $G^{\text{'}}$.
7. Die zu $G^{\text{'}}$ 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 $G^{\text{'}}$ sogar ein ebener Graph, also $G^{\text{'}}\subset X^{\text{'}}={ℝ}^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 $X^{\text{'}}$ lässt sich ein gegebener Graph $G$ einbetten und welche sind deren Merkmale?
  • Speziell: In welche Flächen $F^{\text{'}}\subseteq {ℝ}^d$ lässt sich ein gegebener Graph einbetten und welche sind deren Merkmale (etwa Geschlecht, Orientierbarkeit)?
    • Frage der Plättbarkeit: Für welche Graphen $G$ lässt sich eine ebene Darstellung $G^{\text{'}}$ finden und wie lassen sich diese – etwa kombinatorisch oder gruppentheoretrisch – beschreiben,?
• In welche euklidischen Räume ${ℝ}^d$ lässt sich ein gegebener Graph $G$ mit geradliniger Darstellung $G^{\text{'}}\subset {ℝ}^d$ einbetten?
  • Speziell: Welche Graphen $G$ haben eine geradlinige Darstellung als $d$-dimensionaler Polytopgraph, lassen sich also mit einem Streckengraphen $G^{\text{'}}$ realisieren, dessen Knoten und Kanten exakt aus den Ecken und Kanten eines konvexen Polytops im ${ℝ}^d$ bestehen?
    • Speziell: Welche Graphen $G$ haben eine geradlinige Darstellung als $3$-dimensionaler Polyedergraph, lassen sich also mit einem Streckengraphen $G^{\text{'}}$ realisieren, dessen Knoten und Kanten exakt aus den Ecken und Kanten eines konvexen Polyeders im ${ℝ}^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:

• Jeder endliche schlichte Graph besitzt eine geradlinige Darstellung im ${ℝ}^3$.

Literatur

• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur
• Vorlage:Literatur MR0780555