Hypergraph Theory An Introduction.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.87M 资料格式：pdf 举报版权申诉

第1页 / 共129页

第2页 / 共129页

第3页 / 共129页

第4页 / 共129页

第5页 / 共129页

第6页 / 共129页

第7页 / 共129页

第8页 / 共129页

Cover

Hypergraph Theory

Preface

Acknowledgments

Contents

1 Hypergraphs: Basic Concepts

1.1 First Definitions

1.2 Example of Hypergraph

1.2.1 Simple Reduction 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; Groups and Symmetries

1.4 Generalization of Hypergraphs

References

2 Hypergraphs: First Properties

2.1 Graphs versus Hypergraphs

2.1.1 Graphs

2.1.2 Graphs and Hypergraphs

2.2 Intersecting Families, Helly Property

2.2.1 Intersecting Families

2.2.2 Helly Property

2.3 Subtree Hypergraphs

2.4 Conformal Hypergraphs

2.5 Stable (or Independent), Transversal and Matching

2.5.1 Examples:

2.6 König Property and Dual König Property

2.7 linear Spaces

References

3 Hypergraph Colorings

3.1 Coloring

3.2 Particular Colorings

3.2.1 Strong Coloring

3.2.2 Equitable Coloring

3.2.3 Good 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 Some Particular Hypergraphs

4.1 Interval Hypergraphs

4.2 Unimodular Hypergraphs

4.2.1 Unimodular Hypergraphs and Discrepancy of Hypergraphs

4.3 Balanced Hypergraphs

4.4 Normal 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 Reduction Algorithms

5.2.1 A Generic Algorithm

5.2.2 A Minimum Spanning Tree Algorithm (HR-MST)

References

6 Dirhypergraphs: Basic Concepts

6.1 Basic Definitions

6.2 Basic Properties of Directed Hypergraphs

6.3 Hypercycles in a Dirhypergraph

6.4 Algebraic Representation of Dirhypergraphs

6.4.1 Dirhypergraphs Isomorphism

6.4.2 Algebraic Representation: Definition

6.4.3 Algebraic Representation Isomorphism

References

7 Applications of Hypergraph Theory: A Brief Overview

7.1 Hypergraph Theory and System Modeling for Engineering

7.1.1 Chemical Hypergraph Theory

7.1.2 Hypergraph Theory for Telecomunmications

7.1.3 Hypergraph Theory and Parallel Data Structures

7.1.4 Hypergraphs and Constraint Satisfaction Problems

7.1.5 Hypergraphs and Database Schemes

7.1.6 Hypergraphs and Image Processing

7.1.7 Other Applications

References

Index

Mathematical Engineering For further volumes: http://www.springer.com/series/8445

Alain Bretto Hypergraph Theory An Introduction 123

Alain Bretto Computer Science Department Universite de Caen Caen France ISSN 2192-4732 ISBN 978-3-319-00079-4 DOI 10.1007/978-3-319-00080-0 Springer Cham Heidelberg New York Dordrecht London ISSN 2192-4740 (electronic) ISBN 978-3-319-00080-0 (eBook) Library of Congress Control Number: 2013932774 Ó Springer International Publishing Switzerland 2013 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, speciﬁcally the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microﬁlms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied speciﬁcally for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a speciﬁc statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)

Do not worry if you have difﬁculties in math, I can assure you mine are far greater Albert Einstein

Preface Hypergraphs are systems of ﬁnite sets and form, probably, the most general concept in discrete mathematics. This branch of mathematics has developed very rapidly during the latter part of the twentieth century, inﬂuenced by the advent of computer science. Many theorems on set systems were already known at the beginning of the twentieth century, but these results did not form a mathematical ﬁeld in itself. It was only in the early 1960s that hypergraphs become an inde- pendent theory. Hence, hypergraph theory is a recent theory. It was mostly developed in Hungary and France under the leadership of mathematicians like Paul Erdös, László Lovász, Paul Turán,… but also by C. Berge, for the French school. Originally, developed in France by Claude Berge in 1960, it is a generalization of graph theory. The basic idea consists in considering sets as generalized edges and then in calling hypergraph the family of these edges (hyperedges). As extension of graphs, many results on trees, cycles, coverings, and colorings of hypergraphs will be seen in this book. Hypergraphs model more general types of relations than graphs do. In the past decades, the theory of hypergraphs has proved to be of a major interest in appli- cations to real-world problems. These mathematical tools can be used to model networks, biology networks, data structures, process scheduling, computations and a variety of other systems where complex relationships between the objects in the system play a dominant role. From a theoretical point of view, hypergraphs allow to generalize certain theorems on graphs, even to replace several theorems on graphs by a single theorem of hypergraphs. For instance, the Berge’s weak perfect graph conjecture, which says that a graph is perfect if and only if its complement is perfect, was proved thanks to the concept of normal hypergraph. From a practical point of view, they are now increasingly preferred to graphs. In this book, we give a general and nonstandard presentation of the theory of hypergraphs, although many paragraphs deal with the traditional elements of this theory. In Chap. 1, we introduce the basic language of hypergraphs. The last para- graphs are devoted to more original concepts such as entropy of hypergraph. Similarities and kernels are also discussed. This chapter could be useful to engi- neers and anyone interested in applied science. vii

viii Preface Chapter 2 provides the ﬁrst properties such as the Helly property, the König property, and so on. Standard invariants of hypergraphs are also discussed. In Chap. 3, the classical notions of colorings are addressed. In the early 1980s, scientists information theory introduced decomposition-join approaches into the design and study of databases with large size. A decomposi- tion of a relation induces a database scheme, that is a hypergraph on the attributer set. So tree and hypertree decompositions are introduced at the end of Chap. 4, as well as the concept of acyclicities which are important in computer science. The ﬁrst paragraphs are devoted to speciﬁc classical hypergraphs. The last paragraph introduces planarity. With the emergence of information sciences and life science, the sizes of the systems we deal with are becoming bigger and bigger. Hence Chap. 5 is devoted to the reduction of hypergraphs. These reductions make it possible to preserve good topological, combinatorial, and geometrical properties such as connexity, color- ings, planarity, and so on. Thus, to solve a problem on hypergraph, we can develop algorithms on its reduced hypergraph. Chapter 6 deals with directed hypergraphs. We give some of their basic properties, then we study the cycles in a directed hypergraph. We also introduce the notion a algebraic representation of a dirhypergraph. Chapter 7 gives some applications, not exhaustive and some prospective on hypergraphs. To summarize, this book can be divided into three, ﬁve, seven chapters or levels. Three chapters represent learning, ﬁve chapters represent the knowledge of the theory, seven chapters represent the culmination of everything the reader has worked in the three and ﬁve levels. Paris, December 2012 Alain Bretto

Acknowledgments I make a point of cordially thanking all those who helped me in preparing this book especially: • Alain Faisant (Associate Professor to Université de Saint-Étienne), • Francois Hennercart (Professor to Université de Saint-Étienne), • Thierry Vallée. ix

分享到：

赞收藏

资料库

Hypergraph Theory An Introduction.pdf

相关推荐

课程资源

热门标签

最新资料