Study On Directed Hypergraph Theory And Its Directed Sum Labeling

In many projects like large super-network research, database systems research, timing research, circuit design research and so on, directed hypergraph models can represent relationships between elements there. Due to its good application background, directed hypergraph theory has become a rapidly developing subject in the field of graph theory.Firstly, we summarize the current research on non-directed hypergraph and related basic concepts, and unify the definition of directed hypergraph in different literatures. Based on cardinalities of directed hyperedge, we difine different types of directed hypergraph. The different types of directed hypergraph can transform each other through symmetric image and adding a dummy points, and hence we can define underlying hypergraph of directed hypergraph and bipartite digraph. Secondly, we study the properties of directed hypergraph including the relationship between path and hyperpath, and defined connected and super connected vertex pairs. A effective algorithms is presented to solve shortest problem of non-directed and directed hypergraph, and discussed the problem of shortest hyperpath. By introducing of structure digraph of directed hypergraph, judging planarity of a directed hypergraph equals to judging planarity of its structure digraph, judging planarity of a directed BF-hypergraph equals to judging Zykov planarity of its underlying hypergraph which can be done in linear time. Thirdly, we study application of directed hypergraph, one of the emphases of the thesis. The different kinds of special labelings for non-directed hypergraph suggest directed sum labeling, that is a new labeling for directed hypergraph. In directed sum labeling, each vertex has a integer label such that the sum of the head points labels to a hyperedge equals the sum of the tail points labels. Based on the definition, we give a necessary and sufficient condition for the existence of directed sum labeling, transform the judging existence of directed sum labeling into solving a system of linear equations which determined by the incident matrix, bring forward several necessary conditions of the existence of directed sum labeling, and explore an algorithm for directed sum labeling and general steps to label. Specifically, the thesis contains some discussion of labelings for B-hypergraph and directed star, provides the bound of directed sum S for directed B-hypergraph, and discusses labelings for different types of directed star. Finally, we provide two new research directions: labeling after adding...