By Alain Bretto

ISBN-10: 3319000799

ISBN-13: 9783319000794

This ebook offers an creation to hypergraphs, its goal being to beat the inability of contemporary manuscripts in this conception. within the literature hypergraphs have many different names resembling set structures and households of units. This paintings provides the speculation of hypergraphs in its most unique features, whereas additionally introducing and assessing the newest innovations on hypergraphs. the diversity of subject matters, their originality and novelty are meant to assist readers greater comprehend the hypergraphs in all their variety on the way to understand their price and tool as mathematical instruments. This ebook can be a very good asset to upper-level undergraduate and graduate scholars in machine technology and arithmetic. it's been the topic of an annual Master's direction for a few years, making it additionally splendid to Master's scholars in laptop technological know-how, arithmetic, bioinformatics, engineering, chemistry, and lots of different fields. it's going to additionally gain scientists, engineers and a person else who desires to comprehend hypergraphs theory.

Table of Contents


Hypergraph idea - An Introduction

ISBN 9783319000794 ISBN 9783319000800




1 Hypergraphs: uncomplicated Concepts

1.1 First Definitions
1.2 instance of Hypergraph
1.2.1 easy 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

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

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

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 basic 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

5 Reduction-Contraction of Hypergraph

5.1 Introduction
5.2 aid Algorithms
5.2.1 A popular Algorithm
5.2.2 A minimal Spanning Tree set of rules (HR-MST)

6 Dirhypergraphs: simple Concepts

6.1 uncomplicated 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

7 purposes of Hypergraph concept: a short Overview

7.1 Hypergraph thought and approach Modeling for Engineering
7.1.1 Chemical Hypergraph Theory
7.1.2 Hypergraph thought for Telecomunmications
7.1.3 Hypergraph thought and Parallel information Structures
7.1.4 Hypergraphs and Constraint delight Problems
7.1.5 Hypergraphs and Database Schemes
7.1.6 Hypergraphs and snapshot Processing
7.1.7 different Applications


Show description

Read Online or Download Hypergraph Theory: An Introduction PDF

Best graph theory books

Download e-book for iPad: Graphs and Networks: Transfinite and Nonstandard by Armen H. Zemanian

This self-contained booklet examines effects on transfinite graphs and networks accomplished via a continual examine attempt in past times a number of years. those new effects, masking the mathematical thought of electric circuits, are various from these offered in formerly released books through the writer, Transfiniteness for Graphs, electric Networks, and Random Walks and Pristine Transfinite Graphs and Permissive electric Networks.

Algorithmic Graph Theory and Perfect Graphs - download pdf or read online

Algorithmic Graph conception and ideal Graphs, first released in 1980, has develop into the vintage creation to the sector. This new Annals variation maintains to show the message that intersection graph versions are an important and significant instrument for fixing real-world difficulties. It continues to be a stepping stone from which the reader may well embark on one of the attention-grabbing learn trails.

Steven Roman's An Introduction to Catalan Numbers PDF

This textbook offers an creation to the Catalan numbers and their extraordinary homes, in addition to their a number of purposes in combinatorics. Intended to be obtainable to scholars new to the topic, the publication starts with extra easy issues ahead of progressing to extra mathematically refined themes.

Additional info for Hypergraph Theory: An Introduction

Sample text

We have: s(e, e )=1− | f (e) ∩ f (e )| | f (e) ∪ f (e )|−| f (e) ∩ f (e )| | f (e) f (e )| = = , | f (e) ∪ f (e )| | f (e) ∪ f (e )| | f (e) ∪ f (e )| where A B is symmetric difference between 2 subsets of a set X . It is well known that the map d : P(X ) × P(X ) → R+ defined by d(A, B) = | A B| is a metric. Indeed we have just to show the third axiom, the first and the second are easy. let x ∈ A C and x ∈ C B. Assume that x ∈ A, hence x ∈ C, consequently x ∈ B, and x ∈ A B. So, if x ∈ A B then x ∈ A C or x ∈ C B.

K} and X is a star in H ∗ . Conversely, assume that H ∗ has the Helly property. Let K k be a maximal clique of [H ]2 . By definition of the 2-section, for all xi , x j ∈ K k there is a hyperedge which contains these two vertices. So the set of vertices of K k stands for an intersecting family X of H ∗ which is included into a star since H has the Helly property. Hence there is a vertex of H ∗ which is common to any element of X . But this vertex stands for a hyperedge of H which contains any vertex of K k .

If |E| = |E | then L(H ) L(H ) ({x} is not a hyperedge of H and all hyperedges containing x contain the neighbor y of x in Γ ) and L(H ) is chordal. If |E| = |E | then {x} ∈ E and |E| > |E |. 3 Subtree Hypergraphs 35 It is easy to show that the neighborhood of {x} in L(H ) is a clique (this neighborhood stand for the hyperedges containing x (excepted {x}) ). So any cycle passing through {x} is chordal in L(H ) and so L(H ) is chordal. 2 The hypergraph H is a subtree hypergraph if and only if H has the Helly property and its line graph is chordal.

Download PDF sample

Hypergraph Theory: An Introduction by Alain Bretto

by James

Rated 4.81 of 5 – based on 6 votes