Berge C. Graphs and Hypergraphs

Издательство North Holland, 1976, -546 pp.Graph theory has had an unusual development. Problems involving graphs first appeared in the mathematical folklore as puzzles (e.g. Königsberg bridge problem). Later, graphs appeared in electrical engineering (Kirchhof’s Law), chemistry, psychology and economics before becoming aI unified field of study. Today, graph theory is one of the most flourishing branches of modern algebra with wide applications to combinatorial problems and to classical algebraic problems (Group Theory, with Cayley, Ore, Frucht, Sabidussi. etc.; Category Theory, with Pultr, Hedrlln, 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 König and by Menger.
The second area was the theory of alternating chains which started with Petersen sixty years earlier, but which appeared in optimiation 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. König, P. Erdös, P. Turán. T. Gallai, G. Hajós, 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 graph. 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.One - Graphs
Basic Concepts
Cyclomatic Number
Trees and Arborescences
Paths, Centres and Diameters
Flow Problems
Degrees and Demi-Degrees
Matchings
e-Matchlngs
Connectivity
Hamiltonlan Cycles
Covering Edges with Chains
Stability Number
Kernels and Grundy Functions
Chromatic Number
Perfect Graphs
Two - Hypergraphs
Hypergraphs and their Duals
Transversals
Chromatic Number of a Hypergraph
Balanced Hypergraphs and Unimodular Hypergraphs
Matroids