Hypergraph theory. An introduction (Q1944094): Difference between revisions

In the past 20 years, hypergraph theory and its applications has been developed rapidly and has been an extremely useful tool for solving problems in many areas such as Combinatorics, Computer Science, Optimization, Operation Research, Algebra, Number Theory, etc. The aim of this book is to introduce the basic concepts of hypergraphs, to present the knowledge of the theory and applications of hypergraphs in other fields. More precisely, the book proceeds as follows. In Chapter 1, basic definitions on hypergraphs are given from graph generalization point of view. Algebraic definitions for hypergraphs such as hypergraph entropy, similarity function, metric on hypergraphs and hypergraph morphism are presented. Chapter 2 is devoted to the study of Helly property and König property on hypergraphs. In Chapter 3, colorings of hypergraphs are discussed. Some particular colorings like strong coloring, equitable coloring, good coloring and uniform coloring are introduced. Some results on bicolorable hypergraphs are given and finally algorithms for coloring of graphs and hypergraphs are presented. Chapter 4 begins with introducing some nice families of hypergraphs which have very nice properties and have useful applications. These, include interval hypergraphs, unimodular hypergraphs, balanced hypergraphs, normal hypergraphs, acyclic hypergraphs and Arboreal hypergraphs. In the sequel, hypertree decomposition is discussed, which has many applications in Computer Science. This chapter ends with planar hypergraphs, which are useful in areas such as VLSI design and databases. In Chapter 5, some reduction algorithms for hypergraphs are introduced. The theory of reduction corresponds a reduced hypergraph to any hypergraph, which has less complexity and preserves many nice properties of the hypergraph. Chapter 6, is devoted to the study of directed hypergraphs. After stating basic concepts, Eulerian dirhypergraphs and algebraic representation of dirhypergraphs are discussed. Chapter 7 presents some applications and possible uses of hypergraph theory in applied sciences, such as System Modeling, Parallel Data Structures, Database Schemes and many more. This book is useful for anyone who wants to understand the basics of hypergraph theory. It is mainly for math and computer science majors, but it may also be useful for other fields which use the theory. The book is almost self-contained and no previous knowledge in hypergraph theory is required and it is appropriate for both researchers and graduate students. It is very well-written and proofs are stated in a clear manner. Another good reference for hypergraph theory is the book [\textit{C. Berge}, Hypergraphs: combinatorics of finite sets. North-Holland Mathematical Library, 43. Amsterdam etc.: North-Holland. (1989; Zbl 0674.05001)].