Graphes et hypergraphes. (French) Zbl 0213.25702

Berge, Claude

Monographies universitaires de mathématiques. 37. Paris: Dunod. xviii, 502 p. (1970).

In den letzten zehn bis fünfzehn Jahren hat die graphentheoretische Forschung einen außerordentlichen Aufschwung genommen; dies ist nicht zuletzt ein Verdienst des 1958 erschienenen und seitdem in zahlreichen Sprachen übersetzten Standardwerkes “Théorie des graphes et ses applications” des Autors [Paris: Dunod (1958; Zbl 0088.15404)], der – nach dem 1936 veröffentlichtem Buche von D. König “Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe” [Leipzig: Akademische Verlagsgesellschaft (1936; Zbl 0013.22803)] – ersten Monographie über dieses Gebiet. Ein Vergleich des 12 Jahre später erschienenen hier zu referierenden Buches mit dem genannten Vorgänger ist von Interesse.
Das spätere Werk weist in der Grundkonzeption, in der Setzung der Schwerpunkte sowie in dem bewährten Stil der Darstellung eine Verwandtschaft mit dem ersten auf. Hier wie dort dienen als tragende Hauptsäulen im Aufbau die Theorie der Netzwerke und die Theorie der alternierenden Kantenzüge. Trotzdem ist ein völlig neues Buch entstanden. Gegenüber dem Vorgänger weist es eine wesentliche Erweiterung und Vertiefung auf; zahlreiche durch das erste Werk mit angeregte Publikationen werden verwertet. Die Bereicherung zeigt sich schon rein äußerlich dadurch, daß sich die Seitenzahl nahezu verdoppelt hat. Dabei wurde manches aus dem ersten Buche kürzer gefaßt oder weggelassen. So entfällt die Theorie der unendlichen Graphen ganz. (Ref. findet es etwas bedauerlich, daß die graphentheoretischen Bücher der letzten Jahre sich stets auf endliche Graphen beschränken, da dadurch von vornherein ein großer Zweig der Theorie, der auch zahlreiche Anwendungen in der übrigen Mathematik verspricht, abgeschnitten wird.) Neu hinzugekommen ist ein Abriß der Theorie der “Hypergraphen” und Matroide (ein Hypergraph ist im Prinzip dasselbe wie ein endlicher Komplex, doch deutet der vom Verf. gewählte Name an, daß eine gänzlich andere Fragestellung zugrunde liegt als in der Topologie). Der Verf. trägt damit einer breiten Strömung in der Forschung Rechnung, die die Graphentheorie in einen größeren algebraischen und kombinatorischen Zusammenhang zu stellen sucht.
Eine Besonderheit des Buches ist, daß gerichtete und ungerichtete Graphen gemeinsam behandelt werden; zwischen beiden Arten sieht Verf. keine prinzipielle Trennung. Algorithmen und praktische Anwendungen, die ja viele der Untersuchungen angeregt haben, nehmen einen breiten Raum ein. Natürlich konnten nicht alle wichtigen Teilgebiete der Graphentheorie behandelt werden; so fehlen etwa die Beziehungen zwischen Gruppen und Graphen (Sätze von Frucht) völlig, und auch die Extremalprobleme (im Sinne der ungarischen Schule) sind nur durch den Satz von Turán in seiner komplementären Form vertreten. Manche Sätze, so etwa die Resultate über Graphen auf Flächen, sind ohne Beweis angegeben. Im großen und ganzen wird aber von der Möglichkeit, Ergebnisse nur zu zitieren, im Gegensatz zu der ”Graph Theory” von F. Harary [Reading, Mass. etc.: Addison-Wesley (1969; Zbl 0182.57702)], relativ selten Gebrauch gemacht. In den ausführlicher behandelten Gebieten erreicht das Buch große Tiefe und Aktualität. Ref. sieht in dem Werke die zur Zeit wichtigste systematische Darstellung der Graphentheorie.
Das Werk gliedert sich in zwei Teile mit insgesamt 21 Kapiteln; der erste Teil mit 16 Kapiteln ist den Graphen, der zweite, gut 100 Seiten umfassende, den Hypergraphen und Matroiden gewidmet.
Nach einer sorgfältigen Einführung der Grundbegriffe und verwendeten Symbole werden Zyklen und Kozyklen von Graphen (unter spezieller Berücksichtigung der planaren Graphen) behandelt. Es folgt ein Kapitel über Bäume, das sowohl das Studium der verschiedenen Zusammenhangsarten von gerichteten Graphen als auch Anzahlprobleme der Bäume verschiedenen Typs sowie den Matrix-Gerüst-Satz einschließt. Weiter werden Wege, Zentren, Durchmesser untersucht, dabei u.a. das Labyrinthenproblem und das Problem des kürzesten Weges behandelt; wichtige Resultate von Goldberg und Ghouila-Houri über den Durchmesser stark zusammenhängender Graphen gegebener Kanten- und Eckenzahlen schließen sich an. Es folgt ein Abriß der Theorie der Netzwerke von Ford und Fulkerson. Eine Anwendung hiervon wird dann auf die Charakterisierung der möglichen Gradsequenzen endlicher Graphen gegeben. Die beiden nächsten Kapitel sind Faktorproblemen gewidmet; u.a. werden die klassischen Resultate von Petersen, D. König und Tutte dargestellt. Zugrunde liegt die Methode der alternierenden Kantenzüge.
Kapitel 9 beschäftigt sich mit Problemen (höheren) Zusammenhangs; u.a. wird der Mengersche Satz aus dem Network-Flow-Theorem hergeleitet (übrigens ist auch die umgekehrte Herleitung leicht möglich). Es folgt eine Darstellung der Theorie der Hamiltonschen und Eulerschen Linien (einschließlich der grundlegenden Resultate von Ghouila-Houri und Pósa).
Die nächsten Kapitel behandeln “fundamentale Zahlen” der Graphentheorie: den chromatischen Index (mit Satz von Vizing), die chromatische Zahl (einschließlich kritischer Graphen, Satz von Brooks, Konstruktion von Hajós, Hadwiger-Vermutung, Heawood-Problem und chromatische Polynome), die innere und äußere Stabilitätszahl (mit den Sätzen von Turn und Zarankiewicz sowie Untersuchungen über Kerne und Grundy-Funktionen). Als Anwendungen ergeben sich bekannte Sätze von Rédei, Dilworth und Sperner. Vergleichbarkeits- und Intervallgraphen werden in diesem Rahmen mitbehandelt.
Der zweite Teil (über Hypergraphen) bringt zunächst eine Übertragung einiger graphentheoretischer Grundbegriffe, wie Wege, Kreise, Zusammenhang, auf Hypergraphen; “Clique-Graphen” und “Interchange-Graphen” werden in diesem Rahmen mitbehandelt. Alsdann werden Paarungs- und Färbungsprobleme auf Hypergraphen übertragen, wobei sich verschiedene Verallgemeinerungen der chromatischen Zahl von Graphen ergeben. Der bekannte kombinatorische Satz von Ramsey wird in der Sprache der Hypergraphen formuliert und bewiesen. Schließlich werden Hypergraphen im Gleichgewicht sowie unimodulare Hypergraphen betrachtet und Zusammenhänge mit der Theorie der total unimodularen und doppelt stochastischen Matrizen aufgewiesen.
Das Schlußkapitel gibt eine kurze Einführung in die Theorie der Matroide. Behandelt werden Sätze von R. Rado (zum Repräsentantenproblem), ein Überdeckungssatz von Edmonds und Nash-Williams sowie das Problem der Bestimmung einer optimalen gewichteten Basis.
In dem 20 Seiten umfassenden Literaturverzeichnis werden im wesentlichen nur die im Text verwerteten Arbeiten aufgeführt, von denen die weitaus überwiegende Mehrzahl nach 1960 erschienen ist.
Den Schluß des Bandes bildet ein Register der wichtigsten graphentheoretischen Begriffe mit englischer und deutscher Übersetzung. (Die deutschen Übersetzungen sind allerdings nicht sämtlich als glücklich zu bezeichnen; ein großer Teil von ihnen wird sich wohl kaum durchsetzen).

Reviewer: Rudolf Halin (Hamburg)

MSC:

05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05Cxx	Graph theory

Citations:

Zbl 0088.15404; Zbl 0013.22803; Zbl 0182.57702