Издательство North Holland, 1989, -267 pp.
For the past forty years, Graph Theory has proved to be an extremely useful tool for solving combinatorial problems, in areas as diverse as Geometry, Algebra, Number Theory, Topology, Operations Research and Optimization. It was thus natural to try and generalise the concept of a graph, in order to attack additional combinatorial problems.
The idea of looking at a family of sets from this standpoint took shape around
1060. In regarding each set as a "generalised edge" and in calling the family itself a "hypergraph", the initial idea was to try to extend certain classical results of Graph Theory such as the theorems of Tur?n and K?nig. Next, it was noticed that this generalisation often led to simplification; moreover, one single statement, sometimes remarkably simple, could unify several theorems on graphs. It is with this motivation that we have tried in this book to present what has seemed to us to be the most significant work on hypergraphs.
In addition, the theory of hypergraphs is seen to be a very useful tool for the solution of integer optimization problems when the matrix has certain special properties. Thus the reader will come across scheduling problems (Chapter 4), location problems (Chapter 5), etc., which when formulated in terms of hypergraphs, lead to general algorithms. In this way specialists in operations research and mathematical programming have also been kept in mind by emphasizing the applications of the theory.
For pure mathematicians, we have also included several general results on set systems which do not arise from Graph Theory; graphical concepts nevertheless provide an elegant framework for such results, which become easier to visualize.
For students in pure or applied mathematics, we have thought it worthwhile to add at the end of each chapter a collection of related problems. Some are still open but many are straight forward applications of the theory to combinatorial designs, directed graphs, matroids, etc., such consequences being too numerous to include in the text itself.
General concepts.
Transversal sets and matchings.
Fractional transversals.
Colourings.
Hypergraphs generalising bipartite graphs.
Matchings and colourings in matroids.
For the past forty years, Graph Theory has proved to be an extremely useful tool for solving combinatorial problems, in areas as diverse as Geometry, Algebra, Number Theory, Topology, Operations Research and Optimization. It was thus natural to try and generalise the concept of a graph, in order to attack additional combinatorial problems.
The idea of looking at a family of sets from this standpoint took shape around
1060. In regarding each set as a "generalised edge" and in calling the family itself a "hypergraph", the initial idea was to try to extend certain classical results of Graph Theory such as the theorems of Tur?n and K?nig. Next, it was noticed that this generalisation often led to simplification; moreover, one single statement, sometimes remarkably simple, could unify several theorems on graphs. It is with this motivation that we have tried in this book to present what has seemed to us to be the most significant work on hypergraphs.
In addition, the theory of hypergraphs is seen to be a very useful tool for the solution of integer optimization problems when the matrix has certain special properties. Thus the reader will come across scheduling problems (Chapter 4), location problems (Chapter 5), etc., which when formulated in terms of hypergraphs, lead to general algorithms. In this way specialists in operations research and mathematical programming have also been kept in mind by emphasizing the applications of the theory.
For pure mathematicians, we have also included several general results on set systems which do not arise from Graph Theory; graphical concepts nevertheless provide an elegant framework for such results, which become easier to visualize.
For students in pure or applied mathematics, we have thought it worthwhile to add at the end of each chapter a collection of related problems. Some are still open but many are straight forward applications of the theory to combinatorial designs, directed graphs, matroids, etc., such consequences being too numerous to include in the text itself.
General concepts.
Transversal sets and matchings.
Fractional transversals.
Colourings.
Hypergraphs generalising bipartite graphs.
Matchings and colourings in matroids.