Reinhard Diestel

Graphentheorie

Besprechung aus: Bulletin der DGOR


Man kann versuchen, die Theorie der Graphen zum Gesprächsgegenstand im Freundeskreis zu machen. Da wird man mit Verwunderung und Nichtverstehen bedacht. Diesen wiederum kann man mit der Anregung begegnen, über die Durchlässigkeit eines Straßensystems oder das Telefonnetz diskutieren zu wollen. Das sind dann gängige Themen. Und man redet zugleich über Probleme, für die sich auch die Graphentheorie interessiert.

Die Graphentheorie zählt zu den mathematischen Zweigen, deren Praxisbezug einem Laien in wenigen Minuten exemplarisch zu erläutern ist. Allerdings kann solche Eigenheit nicht die Sicht darauf verstellen, daß die Graphentheorie in den vergangenen Jahren eine Reihe tiefliegender Fragen aufgeworfen und in wichtigen Teilen beantwortet hat - man denke an Ramseytheorie, Baumzerlegungen, an extremale oder topologische Graphentheorie, an Verallgemeinerungen von Färbungsproblemen. Darunter befindet sich manch spektakuläres Resultat, etwa der Minorensatz mit bemerkenswerten Konsequenzen für die Komplexität gewisser Graphenprobleme. Weiterhin verbindet die Graphentheorie verstärkt Resultate zu Strukturen mit der Konstruktion von Methoden. Schließlich hat die Graphentheorie eine neue Qualität bei der Ausarbeitung von Verfahren erreicht, dokumentiert beispielsweise in probabilistischen Algorithmen.

Mithin gibt es genügend Motive, die Reihe der Lehrbücher zur Graphentheorie mit einem Buch zu verlängern, das sich stützt auf die Besichtigung, Bearbeitung und Beurteilung wesentlicher neuer Entwicklungsrichtungen. Ein solches liegt mit dem hier zu besprechenden Werk vor.

Ein erster Blick in den von R. Diestel vorgelegten Band gilt der Themenliste. Ihr Vergleich mit den Inhaltsverzeichnissen solch wichtiger Darstellungen der Graphentheorie wie denen von B. Bollobás, C. Berge, H. Sachs oder W.T. Tutte zeigt die neuen Wege, die R. Diestel dem Leser anbietet: Originelle Fragenkreise, beispielsweise topologische Minoren oder Listenfärbungen, werden bearbeitet. Kapitel wie Färbungen, Flüsse, Ramseytheorie, Hamiltonkreise, Zufallsgraphen oder Minoren-Bäume-Wohlquasiordnung präsentieren fundamentale Problemfelder. Weiterhin findet der Leser wesentliche klassische Resultate nach Überschriften wie Paarungen, Zusammenhang, Graphen in der Ebene. Solch getrennte Aufzählung von klassisch oder fundamental neu muß oberflächlich bleiben, zeigt doch der Autor gerade eindrucksvoll, wie sich die Entwicklungen zu tiefliegenden aktuellen Fragen vollzogen haben.

Das vorliegende Buch behandelt grundlegende Strukturen der Graphentheorie. Algorithmen werden dort vorgestellt, wo sie unmittelbar zum Gang der Darstellung gehören - zum Beispiel als konstruktives Beweisprinzip. So finden sich die Bestimmung eines Maximalflusses oder der Greedy-Technik bei der Eckenfärbung. Hingegen fehlen Verfahren wie die Realisierung des Greedy-Prinzips von Dijkstra (kürzeste Wege) oder von Kruskal (Minimalgerüste).

Damit ist ein zweiter Aspekt dieses Werkes angesprochen, sein Anwendungsbezug. Hier gilt: Zwar erwähnt der Autor gängige Operations-Research-Modelle nur selten. Mit der dadurch möglichen Konzentration auf Strukturen leistet er sehr viel dafür, dem Leser Grundlagen zur Modellanalyse und Verfahrensentwicklung bereitzustellen. Dieses Ziel erreicht der Autor, indem der einführende Charakter des Werkes vereint wird mit tiefliegender Betrachtung wesentlicher graphentheoretischer Resultate.

Also widmen wir den dritten Blick der von R. Diestel gewählten Darstellung. Dazu bemerkt der Autor: `Die Zeit scheint reif zu sein für eine Neubesinnung: was sind heute die Grundpfeiler der Graphentheorie, die einer einführenden und doch in die Tiefe zielenden Vorlesung das Fundament geben können? Dieses Buch möchte Material für eine solche Vorlesung anbieten.' Seine Absicht befördert der Autor dadurch, daß er sowohl die Grundtatsachen jedes Problemkreises darstellt als auch wenigstens eine der relevanten tiefliegenden Fragen im Detail anspricht, mit denen sich die heutige Graphentheorie auseinandersetzt. Das führt zu exemplarischer Vorgehensweise. Jedoch darf der Leser der Führung durch den Autor vertrauen: Es wird ein eindrucksvolles Bild der Graphentheorie gezeichnet. Neue Sichten und Zusammenhänge ergeben sich. Minutiös aufgezeichnet werden graphentheoretische Prinzipien und Techniken. Kurz: Das vorliegende Lehrbuch bietet dem angestrengt mit ihm arbeitenden Leser jegliche Gelegenheit, von der Lebendigkeit der Graphentheorie zu erfahren. Und dieser Leser wird feststellen, dieses Buch schärft auch seinen Blick für manches Problem des Operations Research.

Liebe des Autors zum Gegenstand drückt sich in vielen Details des Buches aus. Jedem Resultat werden - gestalterisch hervorgehoben - wesentliche der Ergebnisse beigefügt, auf die es sich stützt. Übungen ergänzen und vertiefen, überraschen mit originellen Fragen. Notizen, jedem Kapitel beigefügt, diskutieren die zugehörige Literatur, charakterisieren aktuelle Entwicklungen, zeigen auf wichtige Forschungsrichtungen. Da bleibt lediglich Erstaunen darüber, daß der Autor auf ein eigenständiges Literaturverzeichnis verzichtet.

Wer also Graphentheorie zum Gesprächsgegenstand mit Studenten machen will, der sollte zum Diestel greifen.

J. Köhler
Bulletin Deutschen Gesellschaft für Operations Research


Rezensions-Überblick
Zurück zur Hauptseite