Graph Theory

# Hypergraph Theory: An Introduction by Alain Bretto

By Alain Bretto

This booklet presents an creation to hypergraphs, its objective being to beat the shortcoming of contemporary manuscripts in this concept. within the literature hypergraphs have many different names corresponding to set structures and households of units. This paintings offers the idea of hypergraphs in its most unusual features, whereas additionally introducing and assessing the most recent thoughts on hypergraphs. the range of issues, their originality and novelty are meant to aid readers larger comprehend the hypergraphs in all their range to be able to understand their worth and gear as mathematical instruments. This publication could be an excellent asset to upper-level undergraduate and graduate scholars in desktop technological know-how and arithmetic. it's been the topic of an annual Master's path for a few years, making it additionally best to Master's scholars in laptop technological know-how, arithmetic, bioinformatics, engineering, chemistry, and lots of different fields. it is going to additionally profit scientists, engineers and an individual else who desires to comprehend hypergraphs theory.

Cover

Hypergraph conception - An Introduction

ISBN 9783319000794 ISBN 9783319000800

Preface

Acknowledgments

Contents

1 Hypergraphs: uncomplicated Concepts

1.1 First Definitions
1.2 instance of Hypergraph
1.2.1 uncomplicated relief Hypergraph Algorithm
1.3 Algebraic Definitions for Hypergraphs
1.3.1 Matrices, Hypergraphs and Entropy
1.3.2 Similarity and Metric on Hypergraphs
1.3.3 Hypergraph Morphism; teams and Symmetries
1.4 Generalization of Hypergraphs
References

2 Hypergraphs: First Properties

2.1 Graphs as opposed to Hypergraphs
2.1.1 Graphs
2.1.2 Graphs and Hypergraphs
2.2 Intersecting households, Helly Property
2.2.1 Intersecting Families
2.2.2 Helly Property
2.3 Subtree Hypergraphs
2.4 Conformal Hypergraphs
2.5 strong (or Independent), Transversal and Matching
2.5.1 Examples:
2.6 K�nig estate and twin K�nig Property
2.7 linear Spaces
References

3 Hypergraph Colorings

3.1 Coloring
3.2 specific Colorings
3.2.1 powerful Coloring
3.2.2 Equitable Coloring
3.2.3 sturdy Coloring
3.2.4 Uniform Coloring
3.2.5 Hyperedge Coloring
3.2.6 Bicolorable Hypergraphs
3.3 Graph and Hypergraph Coloring Algorithm
References

4 a few specific Hypergraphs

4.1 period Hypergraphs
4.2 Unimodular Hypergraphs
4.2.1 Unimodular Hypergraphs and Discrepancy of Hypergraphs
4.3 Balanced Hypergraphs
4.4 common Hypergraphs
4.5 Arboreal Hypergraphs, Acyclicity and Hypertree Decomposition
4.5.1 Acyclic Hypergraph
4.5.2 Arboreal and Co-Arboreal Hypergraphs
4.5.3 Tree and Hypertree Decomposition
4.6 Planar Hypergraphs
References

5 Reduction-Contraction of Hypergraph

5.1 Introduction
5.2 relief Algorithms
5.2.1 A everyday Algorithm
5.2.2 A minimal Spanning Tree set of rules (HR-MST)
References

6 Dirhypergraphs: simple Concepts

6.1 simple Definitions
6.2 uncomplicated homes of Directed Hypergraphs
6.3 Hypercycles in a Dirhypergraph
6.4 Algebraic illustration of Dirhypergraphs
6.4.1 Dirhypergraphs Isomorphism
6.4.2 Algebraic illustration: Definition
6.4.3 Algebraic illustration Isomorphism
References

7 purposes of Hypergraph idea: a short Overview

7.1 Hypergraph idea and process Modeling for Engineering
7.1.1 Chemical Hypergraph Theory
7.1.2 Hypergraph thought for Telecomunmications
7.1.3 Hypergraph idea and Parallel info Structures
7.1.4 Hypergraphs and Constraint pride Problems
7.1.5 Hypergraphs and Database Schemes
7.1.6 Hypergraphs and photograph Processing
7.1.7 different Applications
References

Index

Best graph theory books

Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems)

In disbursed Algorithms, Nancy Lynch presents a blueprint for designing, enforcing, and examining allotted algorithms. She directs her ebook at a large viewers, together with scholars, programmers, approach designers, and researchers.

Distributed Algorithms comprises the main major algorithms and impossibility leads to the world, all in an easy automata-theoretic environment. The algorithms are proved right, and their complexity is analyzed in keeping with accurately outlined complexity measures. the issues coated comprise source allocation, conversation, consensus between disbursed methods, facts consistency, impasse detection, chief election, international snapshots, and lots of others.

The fabric is prepared in keeping with the method model―first through the timing version after which by means of the interprocess verbal exchange mechanism. the cloth on approach types is remoted in separate chapters for simple reference.

The presentation is totally rigorous, but is intuitive adequate for fast comprehension. This booklet familiarizes readers with vital difficulties, algorithms, and impossibility ends up in the world: readers can then realize the issues after they come up in perform, follow the algorithms to unravel them, and use the impossibility effects to figure out no matter if difficulties are unsolvable. The ebook additionally presents readers with the fundamental mathematical instruments for designing new algorithms and proving new impossibility effects. furthermore, it teaches readers tips on how to cause rigorously approximately disbursed algorithms―to version them officially, devise detailed necessities for his or her required habit, turn out their correctness, and review their functionality with sensible measures.

Topics in Graph Automorphisms and Reconstruction

This in-depth assurance of significant parts of graph thought keeps a spotlight on symmetry homes of graphs. regular issues on graph automorphisms are offered early on, whereas in later chapters extra specialized themes are tackled, similar to graphical usual representations and pseudosimilarity. the ultimate 4 chapters are dedicated to the reconstruction challenge, and right here detailed emphasis is given to these effects that contain the symmetry of graphs, lots of which aren't to be present in different books.

Extra info for Hypergraph Theory: An Introduction

Sample text

The definition of duality implies that xi and x j belong to e1 and e2 (the hyperedges of H standing for the vertices e1 , e2 of H ∗ respectively) so H is not linear. Contradiction (Fig. 6). We have seen several methods to associate a graph to a hypergraph, the converse can be done also. Indeed, let Γ = (V ; E) be a graph, we can associate a hypergraph called neighborhood hypergraph to this graph (Fig. 7): HΓ = (V, (ex = {x} ∪ Γ (x))x∈V ). We can also associate a hypergraph without repeated hyperedge called without repeated hyperedge neighborhood hypergraph: HΓ = (V, {ex = {x} ∪ Γ (x) : x ∈ V }).

The proof of the following theorem can be found in [Déf08]. 3 If the hypergraph H has no Sterboul cycle then it is bicolorable. 4 Let H = (V ; E) be a hypergraph without isolated vertex. If H is hyperedge-transitive then there exists a partition (V1 , V2 , . . , Vk ) such that: k (i) t=1 r (H (Vt )) = r (H ), (ii) H (Vt ) is transitive for all t. e. |ei | = l, for all i ∈ {1, 2, 3, . . , m}.

J. Assoc. Comput. Mach. 30, 514–550 (1983) Chapter 3 Hypergraph Colorings he main problems in combinatorics are often related in the concept of coloring [GGL95a, GGL95b]. 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 2colorable is NP-hard even for 3-uniform hypergraph.