Издательство 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 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, 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 alteating 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.
Keels 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.
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 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, 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 alteating 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.
Keels 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.