Topologische Graphentheorie

(Weitergeleitet von Streckengraph)

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

Bearbeiten

Definition

Bearbeiten

Unter einer Darstellung eines gegebenen Graphen   versteht man einen Graphenisomorphismus von diesem auf einen Graphen  , für den folgende Bedingungen erfüllt sind:

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

Bezeichnungen und Sprechweisen

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

Topologische Graphentheorie im engeren Sinne

Bearbeiten

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

  1.   ist ein endlicher schlichter Graph.
  2. Der topologische Raum   ist eine Fläche im d-dimensionalen euklidischen Raum   . Dabei liegt in aller Regel der   vor.
  3. Die Kanten der Darstellung   sind einfache Jordankurven in   .
  4.   ist ein wegzusammenhängender Raum.
  5. Die Knotenmenge von   hat mit jeder einzelnen Kante von   genau deren Anfangs- und Endpunkt gemeinsam.
  6. Zwei verschiedene Kanten von   schneiden sich entweder gar nicht oder höchstens in einem einzigen Knoten von  .
  7. Die zu   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   sogar ein ebener Graph, also    , so spricht man von einer ebenen Darstellung.

Zentrale Fragen der Topologischen Graphentheorie

Bearbeiten

In der Topologischen Graphentheorie werden die folgenden Fragen behandelt:

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

Bedeutende Sätze der Topologischen Graphentheorie

Bearbeiten

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  .

Literatur

Bearbeiten
  • 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

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