Study on Hypergraphs and Directed Hypergraphs

Hypergraphs, 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 hypergraph theory is that in a graph, a particular edge connects two nodes, but in a hypergraph, the so-called hyper-edges may connect more than two vertices. Hypergraph'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, hypergraphs have gained new application areas and momentum. Definition The dual of a hypergraph where and is a hypergraph with vertex set and edge set where . Definition For any hypergraph , 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 hypergraphs, the first requirement is weaker than the second.

Graphs are considered with the possibility of loops and parallel edges, and the same approach is used for hypergraphs. A hypergraph 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 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 hypergraph is -uniform if every hyperedge has the same cardinality. The cardinality of a hypergraph's greatest hyper-edge is the rank of the hypergraph. 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 hypergraph 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 hypergraph , 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 hypergraph has the following properties: It is well known that Theorem 1.1 of Menger can be generalized for hypergraphs: 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 hypergraph ,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 hypergraph 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 .

A directed hypergraph 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 hypergraph is as a hypergraph's orientation. , i.e., a head node is designated for every hyperedge . The underlying hypergraph of a directed hypergraph D is the one obtained by considering each hyperarc as a hyperedge.

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 hypergraph we define and . For subsets let be the number of hyperarcs with, , . The following is true for every directed hypergraph D and subsets :

Proposition 1.1 In a directed hypergraph , there exist k edge-disjoint paths from node s to node t

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 . , 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 hypergraph 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 hypergraph 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 .

1. To learn more about fuzzy hypergraphs and intuitive fuzzy hypergraphs. 2. To use intuitionistic fuzzy hypergraph knowledge in real-world applications.

Berge [2008] developed the notion of hypergraphs, which has since been regarded as a valuable tool for analysing system structure and representing partitioning, covering, and clustering. Although hypergraphs are not as prevalent as graphs, they do appear in a variety of applications. Database schemata and hypergraphs have a natural correspondence in relational databases, with characteristics matching to vertices and relations to hyper-edges. Hypergraphs are used in VLSI design to visualise circuits, as well as in computational biology and social networks. Directed hypergraphs (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.)[74], 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.). BF-graph are examples of subfamilies. A digraph is an example of a BF-graph. A hypergraph's visual depiction is just as significant as that of graphs and digraphs. Makinen proposed the subset standard and the edge standard, two hypergraph drawing concepts based on techniques for defining hypergraphs. The first one takes use of the fact that a hypergraph 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 hypergraphs. 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 hypergraphs, 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 hypergraphs 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 hypergraphs 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 hypergraphs, unfortunately. The fundamental reason for this is because hypergraphs' reachability relations do not have the same structure.

hypergraph's visual depiction is just as significant as that of graphs and digraphs. Makinen proposed the subset standard and the edge standard, two hypergraph drawing concepts based on techniques for defining hypergraphs. The first one takes use of the fact that a hypergraph 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 hypergraphs. 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 hypergraphs, 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 hypergraph, and showed how the

[1] P. Bhattacharya (1987). Some remarks on fuzzy graphs, Patteren Recognition Let-ters, 6 (5), pp. 297-302. [2] P. Bhattacharya and F. Suraweera (1991). An Algorithm to compute the max-min powers and a property of fuzzy graphs, Patteren Recognition Letters, 12 (7), pp. 413-420. [3] K. R. Bhutani (1989). On auto-morphisms of fuzzy graphs, Pattern recognition letters, 9 (3), pp. 159-162. [4] K. R. Bhutani and A. Rosenfeld (2003). Fuzzy end nodes in fuzzy graphs, Information Sciences, 152, pp. 323-326. [5] K. R. Bhutani and A. Rosenfeld (2003). Strong arcs in fuzzy graphs, Information Sciences, 152, pp. 319-322. [6] G. Bortolan and R. Degani (1985). A review of some methods for ranking fuzzy subsets, Fuzzy Sets and Systems, 15 (1), pp. 1-19. [7] M. Brinkmeier, J. Werner and S. Recknagel (2007). Communities in graphs and hypergraphs, Proceedings of the 16TH ACM conference on Conference on In-formation and Knowledge Management, pp. 869-872. [8] P. Burillo, H. Bustince and V. Mohedano (1994). Some definitions of intuitionistic fuzzy number, Proceedings of the 1ST Workshop on Fuzzy Based Expert Systems, D. Lakov, Ed., Sofia, Bulgaria, pp. 53-55. [9] H. Bustine and P. Burillo (1996). Vague sets are intuitionistic fuzzy sets, Fuzzy Sets and Systems, 79 (3), pp. 403-405. [10] W. Chang (1981). Ranking of fuzzy utilities with triangular membership functions, Proceedings of the International Conference on Policy Analysis and Information Systems, pp. 263-272. [11] S. Chawla, J. Davis and G. Pandy (2004). On local pruning of association rules using directed hypergraphs, ICDE’04 - Proceedings of the 20TH IEEE International Conference on Data Engineering, pp. 832. [12] S. Chen (1985). Ranking fuzzy numbers with maximizing set and minimizing set, Fuzzy Sets and Systems, 17 (2), pp. 113-129.

Springer-Verlag, Berlin Heidelberg.

Research Scholar, Assistant Professor of Mathematics, Government First Grade College, Badavanahalli, Madhugiri Tq, Tumkur, Karnataka, India yogeesh.r@gmail.com