Study on Hyper-Graphs and Directed Hyper-Graphs

 

Yogeesh N1*, Dr. P.K. Chenniappan2

1Research Scholar and Assistant Professor of Mathematics, Government First Grade College, Badavanahalli, Tumkur, Karnataka, Calorx Teacher's University, Ahmedabad, Gujarat, India

Email: yogeesh.r@gmail.com

2 Research Guide, Professor & Head, Department of Mathematics, Calorx Teacher's University, Ahmedabad, Gujarat, India

Abstract - A graph is often thought of as an abstract structure that represents the pairwise connections between collections of objects known as vertices. Two vertices may be linked by an edge or can exist independently of one another. Allowing an edge to link an arbitrary number of vertices is one method to broaden this notion. Hyperedges are subsets of the vertex set, and they are referred to as such. A hyper-graph is made up of a set of vertices and a family of hyperedges. Hyper-graphs are more abstract than graphs, having less structure. Hyper-graphs, rather than graphs, are better suited as a modelling paradigm in certain situations. Hyper-graphs are used to simulate tram lines in [Karbstein, 2012]) and railway vehicle coupling in [Borndörfer et al., 2012] in the area of transportation planning. See [Eiter and Gottlob, 1995] for examples of hyper-graphs in the fields of logic and artificial intelligence. In addition, both directed and undirected hyper-graphs are effectively employed in the area of biological networks analysis; for a brief review, see [Klamt et al., 2009]. Protein interactions, for example, often include more than one protein, therefore hyperedges rather than edges may be utilised to simulate them more correctly.

Keywords: Hyper-graphs, Directed hyper-graphs

INTRODUCTION

Hyper-graphs, a generalization of graphs, were broadly and deeply studied in Berge (1973,1984, 1989), and quite often have proved to be a a hit device to represent and model concepts and structures in diverse areas of Computer Science and Discrete Mathematics. The advancement of graph theory paved the way for discovering answers to real-world issues including finding the shortest route, reducing costs, and scheduling in numerous sectors, among others. Many networking issues benefit from graph theoretical techniques. Hyper-graphs are graphs that have been generalised. The key conceptual distinction between standard graph and hyper-graph theory is that in a graph, a particular edge connects two nodes, but in a hyper-graph, the so-called hyper-edges may connect more than two vertices. Hyper-graph's more flexible representational approach led to new concepts in a variety of disciplines of computer science and informatics requiring large-scale composite systems. As a result, hyper-graphs have gained new application areas and momentum.

Definition The dual of a hyper-graph

where  and  is a hyper-graph  with vertex set and edge set  where .

Definition For any hyper-graph , two vertices v and  are adjacent if there exists an edge that contains both v and , Otherwise, they are not adjacent. In graphs, it's the same as supposing that a set doesn't have any edges or that any two of its vertices aren't near. However, in hyper-graphs, the first requirement is weaker than the second.

HYPER-GRAPHS

Graphs are considered with the possibility of loops and parallel edges, and the same approach is used for hyper-graphs. A hyper-graph is denoted as where V is the set of nodes and  is the set of hyper-edges. Hyper-edges are considered to be multisets. To a hyper-edge  we associate the characteristic function equals the node 's multiplicity in the hyper-edge . When discussing the relationship between a hyper-edge e and a set X, several specific notations will be used:

 means that ,  ,   ,   

means that  The hyper-edge  is defined as

The hyper-edge   is defined as

The hyper-edge  is defined as

For the hyperedge  is defined as

For a hyper-edge set is the smallest subset X of V for which  for every

A –hyper-edge is a hyper-edge  with  for a positive integer v. A hyper-graph is -uniform if every hyperedge has the same cardinality. The cardinality of a hyper-graph's greatest hyper-edge is the rank of the hyper-graph. A hyper-edge e (hyper-edge e) is a kind of edge that   is induced by a subset X of V if e ⊆ X. The number of hyper-edges induced by X is denoted by  The degree of a nodeis

In a hyper-graph H, a path between nodes s and t is an alternating sequence of distinct nodes and hyper-edges  such that , for all  Figure 1.1 shows an example of a path between two nodes. H is connected if there is a path between any two distinct nodes. A hyperedge e enters a set  if and . It is easy to see that H is connected if and only if every non-empty proper subset of V is entered by at least one hyper-edge of H.

For a hyper-graph, we define, and . Note thatbecause hyper-edges are multisets, they might be distinct. In the case of subsets  let be the number of hyper-edges with e ⊆ X ∪ Y,  . Every hyper-graph has the following properties:

………(1.1)

……(1.2)

It is well known that Theorem 1.1 of Menger can be generalized for hyper-graphs:

Theorem Let  be a hyper-graph with different nodes  and  Between  and , the maximum number of edge-disjoint pathways is

As for graphs The local edge-connectivity between  and  is defined as the greatest number of edge-disjoint pathways between  and . If k is a positive integer, then a hyper-graph  ,If the following comparable criteria apply, it is referred to as k-edge-connected:

(i) , for every pair  of distinct nodes.

(ii) , holds for every non-empty proper subset X of V .

(iii) To break down H into two halves, at least k hyper-edges must be removed.

(iv) If we remove  1 hyper-edge from H, it stays linked. If  for all X V, a hyper-graph H is said to cover a set function p. As a result, if we define the set function pk as follows:

, then H is k-edge-connected if and only if it covers .

Directed Hyper-graphs

A directed hyper-graph is defined as a pair , where V denotes a finite ground set and A denotes a finite collection of so-called hyperarcs (possibly with repetition). A hyperarc an is a hyper-edge (which we will also refer to as an if this creates any confusion) with a predefined head node ,  and the remainder of its nodes marked by t. (a). As a result, the function of head and tails is asymmetric:  is a node, but t(a) is a multiset. A natural way to think about a directed hyper-graph is as a hyper-graph's orientation. , i.e., a head node  is designated for every hyperedge . The underlying hyper-graph of a directed hyper-graph D is the one obtained by considering each hyperarc as a hyperedge.

An hyperarc is a hyperarc that has r tail-nodes. If every hyperarc is a -hyperarc,  is -uniform. If an X, a hyperarc an of D is produced by a subset . The number of D hyperarcs caused by X is given by . The indegree of a node  is |. The out-degree of  is  .

A hyperarc a enters a set  and . For a directed hyper-graph  we define

   and      .

For subsets  let be the number of hyperarcs  with, , . The following is true for every directed hyper-graph D and subsets :

                                        (1.4)

                         (1.5)

Theorem 1.2 Extends naturally to directed hyper-graphs:

Proposition 1.1 In a directed hyper-graph , there exist k edge-disjoint paths from node s to node t if and only if   for every  .

Proof. Suppose that  for every . To reduce the problem to the digraph case, a new node   is added to V for every hyperarc , and the hyperarc a is replaced by edges   for every , and an edge  be the obtained digraph. There is a one-to-one correspondence between the paths from s to t in D and the paths from s to t in , and the disjointness of the edges is kept The largest number of edge-disjoint pathways from s to t, according to Theorem 1.2, is

.

for such an , let ; then .

As a result, local edge-connectivity may be defined in the same way as digraphs: for nodes that are distinct  , From  to , is the maximum number of edge-disjoint pathways. In terms of global connectedness, the following is true:

Proposition 1.2. For a directed hyper-graph  and a positive integer , the following are equivalent:

(i)   , for every pair  of distinct nodes.

(ii)  Holds for every non-empty proper subset X of V.

(iii) D remains strongly connected if we delete any  edges.

A hyper-graph that is directed, if the above holds for D, D is referred to be k-edge-connected. If D is k-edge-connected from S to T given S, T, and V, it is said to be k-edge-connected from S to T,   for every distinct  and .

OBJECTIVES

  1. To learn more about fuzzy hyper-graphs and intuitive fuzzy hyper-graphs.
  2. To use intuitionistic fuzzy hyper-graph knowledge in real-world applications.

REVIEW OF LITERATURE

Berge [2008] developed the notion of hyper-graphs, which has since been regarded as a valuable tool for analysing system structure and representing partitioning, covering, and clustering.

Although hyper-graphs are not as prevalent as graphs, they do appear in a variety of applications. Database schemata and hyper-graphs have a natural correspondence in relational databases, with characteristics matching to vertices and relations to hyper-edges. Hyper-graphs are used in VLSI design to visualise circuits, as well as in computational biology and social networks. Directed hyper-graphs (Ausiello et al.,; Gallo et al.,) are an extension of directed graphs (digraphs) that may represent binary relationships between subsets of a given set. Database systems (Ausiello et al. ), expert systems (Ramaswamy et al. ), parallel programming (Nguyen et al.), Scheduling (Lin and Sarra fzadeh, Gallo and Scutella), routing in dynamic networks (Pretolani), data mining (Chawla et al.) and bio informatics all have similar linkages (Krishnamurthy et al.).

Gallo et aldefinitions .'s of directed hyper-graph subfamilies may be linked to older definitions such as the one offered by Ausilo et al. B-graph, F-graph, and BF-graph are examples of subfamilies. A digraph is an example of a BF-graph.

A hyper-graph's visual depiction is just as significant as that of graphs and digraphs. Makinen proposed the subset standard and the edge standard, two hyper-graph drawing concepts based on techniques for defining hyper-graphs. The first one takes use of the fact that a hyper-graph is a set of subsets that can be shown as a Venn diagram. With this standard, Bertault and Eades [2012] proposed a drawing system that concentrates on the depiction of hyper-graphs. A hyperedge e is represented in the edge standard by connecting the points that represent the vertices that form e with curve lines that must cross at a single place, emphasising the image of a single edge. For directed hyper-graphs, the edge standard is the ideal option since the hyper-edges may be drawn as two sets linked by lines. In fact, practically every study on the topic has adopted this graphic portrayal.

Because hyper-edges naturally give a representation of implication dependencies, directed hyper-graphs have a wide range of uses. Among other things, they were used to answer a number of difficulties in propositional logic relating to satisfiability, particularly in relation to Horn formulae. They also show up in issues involving network checking, chemical reaction networks, and, more recently, convex polyhedral algorithmic in tropical algebra. Many algorithmic elements of directed hyper-graphs related to optimization have been explored, including calculating shortest pathways, maximum flows, least cardinality cuts, and minimal weighted hyperpaths. None of the directed graph techniques can be extended to directed hyper-graphs, unfortunately. The fundamental reason for this is because hyper-graphs' reachability relations do not have the same structure.

CONCLUSION

Hyper-graph's visual depiction is just as significant as that of graphs and digraphs. Makinen proposed the subset standard and the edge standard, two hyper-graph drawing concepts based on techniques for defining hyper-graphs. The first one takes use of the fact that a hyper-graph is a set of subsets that can be shown as a Venn diagram. With this standard, a drawing system that concentrates on the depiction of hyper-graphs. A hyperedge e is represented in the edge standard by connecting the points that represent the vertices that form e with curve lines that must cross at a single place, emphasising the image of a single edge. For directed hyper-graphs, the edge standard is the ideal option since the hyper-edges may be drawn as two sets linked by lines. In fact, practically every study on the topic has adopted this graphic portrayal. So standard network techniques are not ok in analyzing those networks. Consequently, they resorted to the concept of a hyper-graph, and showed how the concept of network centrality can be tailored to hyper-graphs.

REFERENCE

1.             Chirs Cornelis, Gad Deschrijver, Mike Nachtegael, Steven Schockaert and Yun Shi (Eds.), 35 years of fuzzy set theory, Springer-Verlag, Berlin Heidelberg, 2010.

2.             Daniele Pretolani, A directed hyper-graph model for random time dependent shortest paths, European Journal of Operational Research, 123 (2), 2000, 315 - 324.

3.             G.Bortolan and R. Degani, A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems, 15 (1), 1985, 1 - 19.

4.             H. Bustine and P. Burillo, Vague sets are intuitionistic fuzzy sets, Fuzzy Sets and Systems, 79 (3), 1996, 403 - 405.

5.             K. R. Bhutani and A. Rosenfeld, Fuzzy end nodes in fuzzy graphs, Information Sciences, 152, 2003, 323 - 326.

6.             K. R. Bhutani and A. Rosenfeld, Strong arcs in fuzzy graphs, Information Sciences, 152, 2003, 319 - 322.

7.             K. R. Bhutani, On auto-morphisms of fuzzy graphs, Pattern recognition letters, 9 (3), 1989, 159 - 162.

8.             M. Brinkmeier, J. Werner and S. Recknagel, Communities in graphs and hyper-graphs, Proceedings of the 16TH ACM conference on Conference on In-formation and Knowledge Management, 2007, 869 - 872.

9.             P. Bhattacharya and F. Suraweera, An Algorithm to compute the max-min powers and a property of fuzzy graphs, Patteren Recognition Letters, 12 (7), 1991, 413 - 420.

10.          P. Bhattacharya, Some remarks on fuzzy graphs, Patteren Recognition Let-ters, 6 (5), 1987, 297 - 302.

11.          P. Burillo, H. Bustince and V. Mohedano, Some definitions of intuitionistic fuzzy number, Proceedings of the 1ST Workshop on Fuzzy Based Expert Systems, D. Lakov, Ed., Sofia, Bulgaria, September 1994, 53 - 55.

12.          S. Chawla, J. Davis and G. Pandy, On local pruning of association rules using directed hyper-graphs, ICDE’04 - Proceedings of the 20TH IEEE International Conference on Data Engineering, 2004, 832.

13.          S. Chen, Ranking fuzzy numbers with maximizing set and minimizing set, Fuzzy Sets and Systems, 17 (2), 1985, 113 - 129.

14.          W. Chang, Ranking of fuzzy utilities with triangular membership functions, Proceedings of the International Conference on Policy Analysis and Information Systems, 1981, 263 - 272.