Издательство North Holland, 1989, -424 pp.
Graph theory has had an unusual development. Problems involving graphs first appeared in the mathematical folklore as puzzles (e.g. Konigsberg bridge problem). Later, graphs appeared in electrical engineering (Kirchhof's Law), chemistry, psychology and economics before becoming a unified field of study. Today, graph theory is one of the most flourishing branches of mode algebra with wide applications to combinatorial problems and to classical algebraic problems (Group Theory, with Cayley, Ore, Frucht, Sabidussi, etc.; Category Theory, with Pultr, Hedrlin, etc.).
Graph theory as a separate entity has had its development shaped largely by operational researchers preoccupied with practical problems. It was with these practical problems in mind that we wrote our first book Theorie des graphes et ses applications published by Dunod in January 1958. This text hoped to unify the various results then scattered through the literature. For this purpose, we emphasized two major areas.
The first of these areas was the network flow theory of Ford and Fulkerson which was beginning to transcend analytic techniques. This theory gave new proofs for more than a dozen graph theory results including some famous theorems by Konig and by Menger.
The second area was the theory of alteating chains which started with Petersen sixty years earlier, but which appeared in optimization problems only in 1957.
These two areas had many curious similarities; however, the integer linear programs that they solved did not overlap. Now, more than ever, we believe that these two areas should form the foundation of graph theory.
The first mathematicians to work in graph theory (in particular the thriving Hungarian school with D. Konig, P. Erdos, P. Tunin, T. Gallai, G. Hajos, etc.) considered mainly undirected graphs, and this could lead students to believe that there are two theories-one for directed graphs and one for undirected graphs. This book is written with the viewpoint that there is only one kind of graph (directed) and only one theory for graphs. This is reasonable because a result for an undirected graph can be interpreted as a result for a directed graph in which the direction of the arcs does not matter. Conversely, a result for a directed graph can be interpreted for an undirected graph by replacing each edge of the undirected graph with two oppositely directed arcs with the same endpoints.
Since 1957, research in graph theory has assumed astonishing proportions. Results have appeared from all over the world, and some of the conjectures of our first book have been solved notably by our students in Paris from 1959 to 1964 (in particular, the late Alain Ghouila-Houri, whose work frequently appears in this text) and by Soviet mathematicians (in particular, A. A. Zykov, V. G. Vizing, L. M. Vitaver, M. K. Goldberg, L. P. Varvak, etc. following the Russian edition of our first text). Thus, because of this embarrassment of riches, this book is vastly more extensive, but still cannot treat very specific applications.
The concept of a matroid due to H. Whitney and developed by W. Tutte has made possible an axiomatic study of cycles and trees. However, we cannot treat this algebraic aspect of graph theory too extensively without straying from our purpose. Similarly, new techniques have appeared for topological graphs, but these would also take us astray. Such strictly topological problems will be the subject of a future work.
On the other hand, this book intends to present a systematic study of the theory of hypergraphs. A hypergraph is defined to be a family of hyperedges which are sets of vertices of cardinality .not necessarily 2 (as for graphs). Given a graph, a hypergraph can be defined by its cliques, or by its spanning trees or by its cycles. Thus, the theory of hypergraphs can generate simultaneously several results for graphs.
The formulation of combinatorial problems in terms of hypergraphs often gives surprisingly simple results that will look very familiar to graph theorists. At the Balatonfilred Conference (1969), P. Erdos and A. Hajnal asked us why we would use hypergraphs for problems that can be also formulated in terms of graphs. The answer is that by using hypergraphs, one deals with generalizations of familiar concepts. Thus, hypergraphs can be used to simplify as well as to generalize.
This English edition contains some results that appeared too late for the original French edition, especially the Chvatal existence theorem for Hamiltonian cycles (Chapter 10) and the Lovasz proof for the first perfect graph conjecture (Chapter 20).
An index of all definitions is given at the end of the text so that the .reader can pass over chapters without much loss of continuity. Theorems are appended with the name of their first discoverer and the year of discovery. Sometimes, an old or fundamental result is treated as a corollary, and the theorem from which it is derived is attributed to a recent author. This is done purely for didactic purposes and is not intended in any way to diminish the importance of results that have been generalized. A bibliography arranged according to chapters is also found at the end of the book.
Basic Concepts.
Cyclomatic Number.
Trees and Arborescences.
Paths, Centres and Diameters.
Flow Problems.
Degrees and Demi-Degrees.
Matchings.
C-Matchings.
Connectivity.
Hamiltonian Cycles.
Covering Edges with Chains.
Chromatic Index.
Stability Number.
Keels and Grundy Functions.
Chromatic Number.
Perfect Graphs.
Graph theory has had an unusual development. Problems involving graphs first appeared in the mathematical folklore as puzzles (e.g. Konigsberg bridge problem). Later, graphs appeared in electrical engineering (Kirchhof's Law), chemistry, psychology and economics before becoming a unified field of study. Today, graph theory is one of the most flourishing branches of mode algebra with wide applications to combinatorial problems and to classical algebraic problems (Group Theory, with Cayley, Ore, Frucht, Sabidussi, etc.; Category Theory, with Pultr, Hedrlin, etc.).
Graph theory as a separate entity has had its development shaped largely by operational researchers preoccupied with practical problems. It was with these practical problems in mind that we wrote our first book Theorie des graphes et ses applications published by Dunod in January 1958. This text hoped to unify the various results then scattered through the literature. For this purpose, we emphasized two major areas.
The first of these areas was the network flow theory of Ford and Fulkerson which was beginning to transcend analytic techniques. This theory gave new proofs for more than a dozen graph theory results including some famous theorems by Konig and by Menger.
The second area was the theory of alteating chains which started with Petersen sixty years earlier, but which appeared in optimization problems only in 1957.
These two areas had many curious similarities; however, the integer linear programs that they solved did not overlap. Now, more than ever, we believe that these two areas should form the foundation of graph theory.
The first mathematicians to work in graph theory (in particular the thriving Hungarian school with D. Konig, P. Erdos, P. Tunin, T. Gallai, G. Hajos, etc.) considered mainly undirected graphs, and this could lead students to believe that there are two theories-one for directed graphs and one for undirected graphs. This book is written with the viewpoint that there is only one kind of graph (directed) and only one theory for graphs. This is reasonable because a result for an undirected graph can be interpreted as a result for a directed graph in which the direction of the arcs does not matter. Conversely, a result for a directed graph can be interpreted for an undirected graph by replacing each edge of the undirected graph with two oppositely directed arcs with the same endpoints.
Since 1957, research in graph theory has assumed astonishing proportions. Results have appeared from all over the world, and some of the conjectures of our first book have been solved notably by our students in Paris from 1959 to 1964 (in particular, the late Alain Ghouila-Houri, whose work frequently appears in this text) and by Soviet mathematicians (in particular, A. A. Zykov, V. G. Vizing, L. M. Vitaver, M. K. Goldberg, L. P. Varvak, etc. following the Russian edition of our first text). Thus, because of this embarrassment of riches, this book is vastly more extensive, but still cannot treat very specific applications.
The concept of a matroid due to H. Whitney and developed by W. Tutte has made possible an axiomatic study of cycles and trees. However, we cannot treat this algebraic aspect of graph theory too extensively without straying from our purpose. Similarly, new techniques have appeared for topological graphs, but these would also take us astray. Such strictly topological problems will be the subject of a future work.
On the other hand, this book intends to present a systematic study of the theory of hypergraphs. A hypergraph is defined to be a family of hyperedges which are sets of vertices of cardinality .not necessarily 2 (as for graphs). Given a graph, a hypergraph can be defined by its cliques, or by its spanning trees or by its cycles. Thus, the theory of hypergraphs can generate simultaneously several results for graphs.
The formulation of combinatorial problems in terms of hypergraphs often gives surprisingly simple results that will look very familiar to graph theorists. At the Balatonfilred Conference (1969), P. Erdos and A. Hajnal asked us why we would use hypergraphs for problems that can be also formulated in terms of graphs. The answer is that by using hypergraphs, one deals with generalizations of familiar concepts. Thus, hypergraphs can be used to simplify as well as to generalize.
This English edition contains some results that appeared too late for the original French edition, especially the Chvatal existence theorem for Hamiltonian cycles (Chapter 10) and the Lovasz proof for the first perfect graph conjecture (Chapter 20).
An index of all definitions is given at the end of the text so that the .reader can pass over chapters without much loss of continuity. Theorems are appended with the name of their first discoverer and the year of discovery. Sometimes, an old or fundamental result is treated as a corollary, and the theorem from which it is derived is attributed to a recent author. This is done purely for didactic purposes and is not intended in any way to diminish the importance of results that have been generalized. A bibliography arranged according to chapters is also found at the end of the book.
Basic Concepts.
Cyclomatic Number.
Trees and Arborescences.
Paths, Centres and Diameters.
Flow Problems.
Degrees and Demi-Degrees.
Matchings.
C-Matchings.
Connectivity.
Hamiltonian Cycles.
Covering Edges with Chains.
Chromatic Index.
Stability Number.
Keels and Grundy Functions.
Chromatic Number.
Perfect Graphs.