Direkt zum Inhalt

Lexikon der Mathematik: Topologische Graphentheorie

Schaut man in ein Lehrbuch der Graphentheorie, dann fällt sofort auf, daß es viele Bilder und Darstellungen enthält, und daß die gegebenen Beweise oft mittels einer Skizze erläutert und veranschaulicht werden. Derjenige, der einen graphentheoretischen Sachverhalt erklären möchte, wird ebenfalls mit hoher Wahrscheinlichkeit die bildliche Darstellung eines Graphen verwenden und anhand dieser mit oft recht intuitiven Worten argumentieren.

Betrachtet man nun aber die rein mengentheoretische Definition eines Graphen, dann sind die oben genannten Beobachtungen zunächst nur schwer einsichtig.

Warum beschreibt man in der Regel einen Graphen nicht durch das Aufzählen seiner Ecken- und Kantenmengen, sondern bevorzugt Bilder?

Die Antwort darauf lautet, daß die in der Graphentheorie untersuchten und exakt definierten Begriffe oft anschauliche Entsprechungen haben, was sich auch an ihren Namen wie Baum, Kreis, Weg, Färbung, Landkarte, etc. zeigt.

In der topologischen Graphentheorie werden nun die o.g. bildlichen Darstellungen genauer untersucht und verallgemeinert. Dies führt zu den für dieses Gebiet zentralen Begriffen des planaren Graphen und der Einbettung eines Graphen in einen allgemeinen topologischen Raum. Damit wird eine Brücke zwischen der Graphentheorie und der Topologie geschlagen, und wie oft in der Mathematik ist es hier gerade die Verbindung zweier scheinbar getrennter Gebiete, die zu interessanten und sehr tiefen Erkenntnissen führt.

Leonhard Euler, der bereits 1736 die erste ‚graphentheoretische Arbeit‘ geschrieben hatte (Wurzeln der Graphentheorie), war es auch, der 1750 mit der Eulerschen Polyederformel die erste und sehr wichtige Aussage der topologischen Graphentheorie bewies. Seitdem haben sich besonders ab der zweiten Hälfte des neunzehnten Jahrhunderts viele der heute klassischen Fragen und einige der schwierigsten Sätze der Graphentheorie, wie z. B. das Heawoodsche Map-Color-Theorem oder der Vier-Farben-Satz, aus der topologischen Graphentheorie heraus entwickelt.

Ihr zentrales Anliegen ist das Studium planarer Graphen. Anschaulich beschrieben nennt man einen Graphen planar, wenn man ihn so auf ein Blatt Papier – also ggf. auch in die Ebene ℝ2 – zeichnen kann, daß sich seine Kanten nur in den Ecken schneiden. Die Sätze von Kuratowski undMacLane geben wertvolle Charakterisierungen dieser Graphenklasse an, die rein kombinatorisch bzw. algebraisch sind und erstaunlicherweise keinen Bezug auf topologische Eigenschaften des ℝ2 nehmen.

Oft ist es so, daß Sätze der topologischen Graphentheorie ein tieferes Verständnis der kombinatorischen Eigenschaften von topologischen Räumen liefern. Beispiele hierfür sind im Fall der orientierbaren und nicht-orientierbaren Flächen beliebigen Geschlechts das bereits erwähnte Heawoodsche Map-Color-Theorem oder auch die Euler-Poincarésche Formel, die eine Verallgemeinerung der Eulerschen Polyederformel darstellt.

Aus der topologischen Graphentheorie und besonders aus den oftmals vergeblichen Versuchen, den berühmten Vier-Farben-Satz zu beweisen, sind viele andere Bereiche der Graphentheorie entstanden. Ein gutes Beispiel dafür liefert der Satz von Tait, der einen möglichen Zugang zum Vier-Farben-Satz über Kantenfärbungen von Graphen aufzeigt.

Gerade in jüngerer Zeit haben sich Teile der Graphentheorie besonders eindrucksvoll entwickelt, die sich oft explizit auf die topologische Graphentheorie beziehen und dort bewiesene Aussagen beispielhaft als Prototypen für viele ihrer Sätze zitieren. So führt z. B. ein direkter Weg vom Satz von Kuratowski über Wagners Charakterisierung von Graphen ohne K5 als Minor zur Charakterisierung anderer Grapheneigenschaften mittels verbotener Minoren und zum systematischen Studium von Minoren an sich (‚Graph-Minor-Project‘).

Literatur

[1] Bonnington, C.P.; Little, C.H.C.: The foundations of topological graph theory. Springer-Verlag New York, 1995.

[2] Gross, J.L.; Tucker, T.W.: Topological graph theory. John Wiley & Sons. New York, 1987.

[3] Mohar, B. und Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, 1999.

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

Partnervideos