An example of an undirected hypergraph, with and. This hypergraph has order 7 and size 4. Here, edges do not just connect two vertices but several, and are represented by colors.Alternative representation of the hypergraph reported in the figure above, called PAOH.[1] Edges are vertical lines connecting vertices. V7 is an isolated vertex. Vertices are aligned to the left. The legend on the right shows the names of the edges.An example of a directed hypergraph, with and
Inmathematics, ahypergraph is a generalization of agraph in which anedge can join any number ofvertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, adirected hypergraph is a pair, where is a set of elements callednodes,vertices,points, orelements and is a set of pairs of subsets of. Each of these pairs is called anedge orhyperedge; the vertex subset is known as itstail ordomain, and as itshead orcodomain.
Theorder of a hypergraph is the number of vertices in. Thesize of the hypergraph is the number of edges in. Theorder of an edge in a directed hypergraph is: that is, the number of vertices in its tail followed by the number of vertices in its head.
The definition above generalizes from adirected graph to a directed hypergraph by defining the head or tail of each edge as a set of vertices ( or) rather than as a single vertex. A graph is then the special case where each of these sets contains only one element. Hence any standard graph theoretic concept that is independent of the edge orders will generalize to hypergraph theory.
Anundirected hypergraph is an undirected graph whose edges connect not just two vertices, but an arbitrary number.[2] An undirected hypergraph is also called aset system or afamily of sets drawn from the set of elements.
Hypergraphs can be viewed asincidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, everybipartite graph can be regarded as the incidence graph of a hypergraph when it is 2-colored and it is indicated which color class corresponds to hypergraph vertices and which to hypergraph edges.
Hypergraphs have many other names. Incomputational geometry, an undirected hypergraph may sometimes be called arange space and then the hyperedges are calledranges.[3]Incooperative game theory, hypergraphs are calledsimple games (voting games); this notion is applied to solve problems insocial choice theory. In some literature edges are referred to ashyperlinks orconnectors.[4]
Undirected hypergraphs are useful in modelling such things as satisfiability problems,[5] databases,[6] machine learning,[7] andSteiner tree problems.[8] They have been extensively used inmachine learning tasks as the data model and classifierregularization.[9] The applications includerecommender system (communities as hyperedges),[10][11]image retrieval (correlations as hyperedges),[12] andbioinformatics (biochemical interactions as hyperedges).[13] Representative hypergraph learning techniques include hypergraphspectral clustering that extends thespectral graph theory with hypergraph Laplacian,[14] and hypergraphsemi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results.[15] For large scale hypergraphs, a distributed framework[7] built usingApache Spark is also available. It can be desirable to study hypergraphs where all hyperedges have the same cardinality; ak-uniform hypergraph is a hypergraph such that all its hyperedges have sizek. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connectingk nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on.
Directed hypergraphs can be used to model things including telephony applications,[16] detectingmoney laundering,[17] operations research,[18] and transportation planning. They can also be used to modelHorn-satisfiability.[19]
Thiscircuit diagram can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.
In one possible visual representation for hypergraphs, similar to the standardgraph drawing style in which curves in the plane are used to depict graph edges, a hypergraph's vertices are depicted as points, disks, or boxes, and its hyperedges are depicted as trees that have the vertices as their leaves.[20][21] If the vertices are represented as points, the hyperedges may also be shown as smooth curves that connect sets of points, or assimple closed curves that enclose sets of points.[22][23][24]
An order-4 Venn diagram, which can be interpreted as a subdivision drawing of a hypergraph with 15 vertices (the 15 colored regions) and 4 hyperedges (the 4 ellipses)
In another style of hypergraph visualization, the subdivision model of hypergraph drawing,[25] the plane is subdivided into regions, each of which represents a single vertex of the hypergraph. The hyperedges of the hypergraph are represented by contiguous subsets of these regions, which may be indicated by coloring, by drawing outlines around them, or both. An order-nVenn diagram, for instance, may be viewed as a subdivision drawing of a hypergraph withn hyperedges (the curves defining the diagram) and 2n − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition ofplanar graphs, it isNP-complete to determine whether a hypergraph has a planar subdivision drawing,[26] but the existence of a drawing of this type may be tested efficiently when the adjacency pattern of the regions is constrained to be a path, cycle, or tree.[27]
An alternative representation of the hypergraph called PAOH[1] is shown in the figure on top of this article. Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges. It has been designed for dynamic hypergraphs but can be used for simple hypergraphs as well.
Classic hypergraph coloring is assigning one of the colors from set to every vertex of a hypergraph in such a way that each hyperedge contains at least two vertices of distinct colors. In other words, there must be no monochromatic hyperedge with cardinality at least 2. In this sense it is a direct generalization of graph coloring. The minimum number of used distinct colors over all colorings is called the chromatic number of a hypergraph.
Hypergraphs for which there exists a coloring using up tok colors are referred to ask-colorable. The 2-colorable hypergraphs are exactly the bipartite ones.
There are many generalizations of classic hypergraph coloring. One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed. Some mixed hypergraphs are uncolorable for any number of colors. A general criterion for uncolorability is unknown. When a mixed hypergraph is colorable, then the minimum and maximum number of used colors are called the lower and upper chromatic numbers respectively.[28]
A hypergraph can have various properties, such as:
Empty - has no edges.
Non-simple(ormultiple) - has loops (hyperedges with a single vertex) or repeated edges, which means there can be two or more edges containing the same set of vertices.
Simple - has no loops and no repeated edges.
-regular - every vertex has degree, i.e., contained in exactly hyperedges.
2-colorable - its vertices can be partitioned into two classesU andV in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. An alternative term isProperty B.
-uniform - each hyperedge contains precisely vertices.
-partite - the vertices are partitioned into parts, and each hyperedge contains precisely one vertex of each type.
Every-partite hypergraph (for) is both-uniform and bipartite (and 2-colorable).
Reduced:[29] no hyperedge is a strict subset of another hyperedge; equivalently, every hyperedge is maximal for inclusion. Thereduction of a hypergraph is the reduced hypergraph obtained by removing every hyperedge which is included in another hyperedge.
Downward-closed - every subset of an undirected hypergraph's edges is a hyperedge too. A downward-closed hypergraph is usually called anabstract simplicial complex. It is generally not reduced, unless all hyperedges have cardinality 1.
An abstract simplicial complex with theaugmentation property is called amatroid.
Laminar: for any two hyperedges, either they are disjoint, or one is included in the other. In other words, the set of hyperedges forms alaminar set family.
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, calledsubhypergraphs,partial hypergraphs andsection hypergraphs.
Let be the hypergraph consisting of vertices
and havingedge set
where and are theindex sets of the vertices and edges respectively.
Asubhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph induced by is defined as
An alternative term is therestriction ofH toA.[30]: 468
Anextension of a subhypergraph is a hypergraph where each hyperedge of which is partially contained in the subhypergraph is fully contained in the extension. Formally
with and.
Thepartial hypergraph is a hypergraph with some edges removed.[30]: 468 Given a subset of the edge index set, the partial hypergraph generated by is the hypergraph
Given a subset, thesection hypergraph is the partial hypergraph
Thedual of is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by and whose edges are given by where
When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is aninvolution, i.e.,
Aconnected graphG with the same vertex set as a connected hypergraphH is ahost graph forH if every hyperedge ofHinduces a connected subgraph inG. For a disconnected hypergraphH,G is a host graph if there is a bijection between theconnected components ofG and ofH, such that each connected componentG' ofG is a host of the correspondingH'.
The2-section (orclique graph,representing graph,primal graph,Gaifman graph) of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.
Thetranspose of theincidence matrix defines a hypergraph called thedual of, where is anm-element set and is ann-element set of subsets of. For andif and only if.
For a directed hypergraph, the heads and tails of each hyperedge are denoted by and respectively.[19] where
A hypergraphH may be represented by abipartite graphBG as follows: the setsX andE are the parts ofBG, and (x1,e1) are connected with an edge if and only if vertexx1 is contained in edgee1 inH.
Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also calledincidence graph.
A parallel for the adjacency matrix of a hypergraph can be drawn from theadjacency matrix of a graph. In the case of a graph, the adjacency matrix is a square matrix which indicates whether pairs of vertices areadjacent. Likewise, we can define the adjacency matrix for a hypergraph in general where the hyperedgeshave real weights with
In contrast with ordinary undirected graphs for which there is a single natural notion ofcycles andacyclic graphs. For hypergraphs, there are multiple natural non-equivalent definitions of cycles which collapse to the ordinary notion of cycle when the graph case is considered.
A first notion of cycle was introduced byClaude Berge.[31] ABerge cycle in a hypergraph is an alternating sequence of distinct vertices and edges, where and are both in for each (with indices taken modulo).
Under this definition a hypergraph isacyclic if and only if itsincidence graph (thebipartite graph defined above) is acyclic. Thus Berge-cyclicity can obviously be tested inlinear time by an exploration of the incidence graph.
This definition is particularly used for-uniform hypergraphs, where all hyperedges are of size. Atight cycle of length in a hypergraph is a sequence of distinct vertices such that every consecutive-tuple (indices modulo) forms a hyperedge in. This notion was introduced by Katona and Kierstead[32] and has since garnered considerable attention, particularly in the study of Hamiltonicity in extremal combinatorics.[33][34]
Rödl, Szemerédi, and Ruciński showed that every-vertex-uniform hypergraph in which every-subset of vertices is contained in at least hyperedges contains a Hamilton cycle. This corresponds to an approximate hypergraph-extension of the celebratedDirac's theorem about Hamilton cycles in graphs.[35]
The maximum number of hyperedges in a (tightly) acyclic-uniform hypergraph remains unknown. The best known bounds, obtained by Sudakov and Tomon,[36] show that every-vertex-uniform hypergraph with at least hyperedges must contain a tight cycle. This bound is optimal up to the error term.
An-cycle generalizes the notion of a tight cycle.It consists in a sequence of vertices and hyperedges where each consists of consecutive vertices in the sequence and for every. Since every edge of the-cycle contains exactly vertices which are not contained in the previous edge, must be divisible by. Note that recovers the definition of a tight cycle.
The definition of Berge-acyclicity might seem to be very restrictive: for instance, if a hypergraph has some pair of vertices and some pair of hyperedges such that and, then it is Berge-cyclic.
We can define a weaker notion of hypergraph acyclicity,[6] later termed α-acyclicity. This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph beingchordal; it is also equivalent to reducibility to the empty graph through theGYO algorithm[37][38] (also known as Graham's algorithm), aconfluent iterative process which removes hyperedges using a generalized definition ofears. In the domain ofdatabase theory, it is known that adatabase schema enjoys certain desirable properties if its underlying hypergraph is α-acyclic.[39] Besides, α-acyclicity is also related to the expressiveness of theguarded fragment offirst-order logic.
Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming,Ronald Fagin[41] defined the stronger notions of β-acyclicity and γ-acyclicity. We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent[41] to an earlier definition by Graham.[38] The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related toBachman diagrams. Both β-acyclicity and γ-acyclicity can be tested inpolynomial time.
Those four notions of acyclicity are comparable: γ-acyclicity which implies β-acyclicity which implies α-acyclicity. Moreover, Berge-acyclicity implies all of them. None of the reverse implications hold including the Berge one. In other words, these four notions are different.[41]
The bijection is then called theisomorphism of the graphs. Note that
if and only if.
When the edges of a hypergraph are explicitly labeled, one has the additional notion ofstrong isomorphism. One says that isstrongly isomorphic to if the permutation is the identity. One then writes. Note that all strongly isomorphic graphs are isomorphic, but not vice versa.
When the vertices of a hypergraph are explicitly labeled, one has the notions ofequivalence, and also ofequality. One says that isequivalent to, and writes if the isomorphism has
and
Note that
if and only if
If, in addition, the permutation is the identity, one says that equals, and writes. Note that, with this definition of equality, graphs are self-dual:
A hypergraphautomorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraphH (= (X, E)) is agroup under composition, called theautomorphism group of the hypergraph and written Aut(H).
Therank of a hypergraph is the maximum cardinality of any of the edges in the hypergraph. If all edges have the same cardinalityk, the hypergraph is said to beuniform ork-uniform, or is called ak-hypergraph. A graph is just a 2-uniform hypergraph.
The degreed(v) of a vertexv is the number of edges that contain it.H isk-regular if every vertex has degreek.
The dual of a uniform hypergraph is regular and vice versa.
Two verticesx andy ofH are calledsymmetric if there exists an automorphism such that. Two edges and are said to besymmetric if there exists an automorphism such that.
A hypergraph is said to bevertex-transitive (orvertex-symmetric) if all of its vertices are symmetric. Similarly, a hypergraph isedge-transitive if all edges are symmetric. If a hypergraph is both edge- and vertex-symmetric, then the hypergraph is simplytransitive.
Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity.
One possible generalization of a hypergraph is to allow edges to point at other edges.[47] There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so onad infinitum. In essence, every edge is just an internal node of a tree ordirected acyclic graph, and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees).[48][49] Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughoutcomputer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well.[50] So, for example, this generalization arises naturally as a model ofterm algebra; edges correspond toterms and vertices correspond to constants or variables.[51]
For such a hypergraph, set membership then provides an ordering, but the ordering is neither apartial order nor apreorder, since it is not transitive.[52] The graph corresponding to the Levi graph of this generalization is adirected acyclic graph.[53] Consider, for example, the generalized hypergraph whose vertex set is and whose edges are and. Then, although and, it is not true that. However, thetransitive closure of set membership for such hypergraphs does induce apartial order, and "flattens" the hypergraph into apartially ordered set.[54]
Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs.[47][48] This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges and, and zero vertices, so that and. As this loop is infinitely recursive, sets that are the edges violate theaxiom of foundation.[48] In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longerbipartite, but is rather just some generaldirected graph.[55]
The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges.[56] Thus, for the above example, theincidence matrix is simply
^Feige, Uriel; Kim, Jeong Han; Ofek, Eran (2006). "Witnesses for non-satisfiability of dense random 3CNF formulas".2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE. pp. 497–508.doi:10.1109/FOCS.2006.78.ISBN0-7695-2720-5.
^Tian, Ze; Hwang, TaeHyun; Kuang, Rui (2009), "A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge",Bioinformatics,25 (21):2831–2838,doi:10.1093/bioinformatics/btp467,PMID19648139
^Naheed Anjum, Arafat; Bressan, Stéphane (2017), "Hypergraph Drawing by Force-Directed Placement",Database and Expert Systems Applications, Lecture Notes in Computer Science, vol. 10439, Springer International Publishing, pp. 387–394,doi:10.1007/978-3-319-64471-4_31,ISBN978-3-319-64470-7.
^Tarjan, R. E.;Yannakakis, M. (1984). "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs".SIAM Journal on Computing.13 (3):566–579.doi:10.1137/0213035.
^Harary, F. (2018) [1969].Graph Theory. CRC Press. p. 172.ISBN978-0-429-96231-8.Archived from the original on 2023-02-04. Retrieved2021-06-12.We next state a theorem due to Elayne Dauber whose corollaries describe properties of line-symmetric graphs. Note the obvious but important observation that every line-symmetric graph is line-regular.
^Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (March 1999), "Multilevel hypergraph partitioning: applications in VLSI domain",IEEE Transactions on Very Large Scale Integration (VLSI) Systems,7 (1):69–79,Bibcode:1999ITVL....7...69K,CiteSeerX10.1.1.553.2367,doi:10.1109/92.748202.{{citation}}: CS1 maint: multiple names: authors list (link)
^Catalyurek, U.V.; Aykanat, C. (1995).A Hypergraph Model for Mapping Repeated Sparse Matrix–Vector Product Computations onto Multicomputers. Proc. International Conference on Hi Performance Computing (HiPC'95).
^abcDevlin, Keith (1993). "Chapter 7. Non-Well-Founded Set Theory".The Joy of Sets: Fundamentals of Contemporary Set Theory (2nd ed.). pp. 143–184.doi:10.1007/978-1-4612-0903-4_7.
