Hypergraph Theory

An Introduction

verfasst von: Alain Bretto

Verlag: Springer International Publishing

Buchreihe : Mathematical Engineering

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book provides an introduction to hypergraphs, its aim being to overcome the lack of recent manuscripts on this theory. In the literature hypergraphs have many other names such as set systems and families of sets. This work presents the theory of hypergraphs in its most original aspects, while also introducing and assessing the latest concepts on hypergraphs. The variety of topics, their originality and novelty are intended to help readers better understand the hypergraphs in all their diversity in order to perceive their value and power as mathematical tools. This book will be a great asset to upper-level undergraduate and graduate students in computer science and mathematics. It has been the subject of an annual Master's course for many years, making it also ideally suited to Master's students in computer science, mathematics, bioinformatics, engineering, chemistry, and many other fields. It will also benefit scientists, engineers and anyone else who wants to understand hypergraphs theory.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Hypergraphs: Basic Concepts

Abstract

View the significant developments of combinatoric thanks to computer science [And89, LW01], hypergraphs are increasingly important in science and engineering. Hypergraphs are a generalization of graphs, hence many of the definitions of graphs carry verbatim to hypergraphs. In this chapter we introduce basic notions about hypergraphs. Most of the vocabulary used in this book is given here and most of this one is a generalization of graphs languages [LvGCWS12].

Alain Bretto

Chapter 2. Hypergraphs: First Properties

Abstract

In the first chapter we saw that hypergraphs generalize standard graphs by defining edges between multiple vertices instead of only two vertices. Hence some properties must be a generalization of graph properties In this chapter, we introduce some basic properties of hypergraphs which will be used throughout this book.

Alain Bretto

Chapter 3. Hypergraph Colorings

Abstract

The main problems in combinatorics are often related in the concept of coloring [CGL95a, CGL95b]. Hypergraph colorings is a well studied problem in the literature in combinatorics [Lov73]. Colorations have many applications in telecommunication, computer science and engineering. Unlike the graphs where we can tested in linear time if a graph is 2-colorable, testing if a given hypergraph is 2- colorable is NP-hard even for 3-uniform hypergraph. In this chapter, we present some results about coloring concepts. Some examples are given to illustrate the particular types of colorings.

Alain Bretto

Chapter 4. Some Particular Hypergraphs

Abstract

Roughly speaking we introduced the more important concepts about hypergraphs, we will see a little bit more in the next chapters, but there are very important classes of hypergraphs. This chapter introduces some particular hypergraphs which either have good properties, or are very important for applications of the theory. In the sequel we will suppose most of the time that hypergraph are without repeated hyperedge.

Alain Bretto

Chapter 5. Reduction-Contraction of Hypergraph

Abstract

In many human activities we must first model. The choice of a good model is essential in order to be able to deal with the complexity of the phenomena we need to understand. The objects we want to represent use increasingly more data: large databases, satellite images, large clusters, ...

Alain Bretto

Chapter 6. Dirhypergraphs: Basic Concepts

Abstract

Outside the classical theory of hypergraphs, there is a beginning of theory which is not yet stabilized, it is the theory of directed hypergraphs. This chapter investigates the notion of directed hypergraph (dirhypergraph). We try to clarify its vocabulary.

Alain Bretto

Chapter 7. Applications of Hypergraph Theory: A Brief Overview

Abstract

Like in most fruitful mathematical theories, the theory of hypergraphs has many applications. Hypergraphs model many practical problems in many different sciences. it makes very little time (20 years) that the theory of hypergraphs is used to model situations in the applied sciences. We find this theory in psychology, genetics, \(\ldots \) but also in various human activities. Hypergraphs have shown their power as a tool to understand problems in a wide variety of scientific field. Moreover it well known now that hypergraph theory is a very useful tool to resolve optimization problems such as scheduling problems, location problems and so on. This chapter shows some possible uses of hypergraphs in Applied Sciences.

Alain Bretto

Backmatter

Titel: Hypergraph Theory
verfasst von: Alain Bretto
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-00080-0
Print ISBN: 978-3-319-00079-4
DOI: https://doi.org/10.1007/978-3-319-00080-0