The Cyclicity Of Hypergraphs

Hypergraph is an important mathematical structure arising from natural science and mathematics. It has wide applications in many fields, such as database structure, artificial intelligence, computational biology, social science and so on. The cyclicity of a hypergraph or the acyclicity of a hypergraph is an important way to describe the tree-likeness of the hypergraphs. Various tree-likeness parameters turn out to be the key parameters controlling the complexity of most combinatorial optimization problems and have led to a lot of researches.The join graph of a hypgergraph is an important tool in researching the acyclicity of hypergraphs. The join graph of a hypgergraph is a graph G = ( E ( H ), L),satisfying: 1. ?e 1 , e2∈E ( H), e1 ,e2 is connected by a path containing e1∩e2; 2. | L | is minimal. The acyclicity of the join graph of a hypergraph corresponds with the acyclicity of the hypergraph, and the cyclicity of the join graph of a simple hypergraph equals the cyclicity of the hypergraph. The join graph of a hypergraph is not unique, different join graphs show parts of the adjacent relation of hyperedges, but if we can find all join graphs of a hypergraph, we can obtain the whole adjacent relation of hyperedges of the hypergraph.In this paper, we firstly discuss the concept of anα-cycle introduced by Philippe in [17] and the discrimination method of decidingα-acyclic. We study the basic properties ofα-cycle. Furthermore, based on Philippe's research, we obtain our result that when a simple hypergraph isα-acyclic, the number of the edges of the corresponding minimal intergraph is | E ( H ) | ?1 , where | E ( H ) | is the number of hyperedges of the hypergraph. Secondly, we discuss the definition of acyclicity introduced by France Dacar in [10]. We introduce the join-invariant in hypergraph, the cyclicity of a hypergraph and some related theorems and properties and we make a comparison between the cyclicity and the cyclomatic number of a hypergraph. Furthermore, we obtain the result that when a hypergraph is notα-acyclic, the cyclicity of the hypergraph is bigger or equal than 1. After that, we point out that there is equivalence between theα-acyclicity introduced by Philippe and the acyclicty introduced by France Dacar. And the minimal intergraph and join graph of a hypergraph are also equivalent. And then we design an algrithm to construct the join graph of a hypergraph by the construction of join-graphs. At last, we calculate the number of different join graphs of a simple hypergraph using Cayley's formula.