An example of a hypergraph, with X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\} and E = \{e_1,e_2,e_3,e_4\} = \{\{v_1, v_2, v_3\}, \{v_2,v_3\}, \{v_3,v_5,v_6\}, \{v_4\}\}.
In mathematics, a hypergraph is a generalization of a graph in which an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = (X,E) where X is a set of elements called nodes or vertices, and E is a set of nonempty subsets of X called hyperedges or edges. Therefore, E is a subset of \mathcal{P}(X) \setminus\{\emptyset\}, where \mathcal{P}(X) is the power set of X.
While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a kuniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting k nodes.) So a 2uniform hypergraph is a graph, a 3uniform hypergraph is a collection of unordered triples, and so on.
A hypergraph is also called a set system or a family of sets drawn from the universal set X. The difference between a set system and a hypergraph is in the questions being asked. Hypergraph theory tends to concern questions similar to those of graph theory, such as connectivity and colorability, while the theory of set systems tends to ask nongraphtheoretical questions, such as those of Sperner theory.
There are variant definitions; sometimes edges must not be empty, and sometimes multiple edges, with the same set of nodes, are allowed.
Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs.
Hypergraphs have many other names. In computational geometry, a hypergraph may sometimes be called a range space and then the hyperedges are called ranges.^{[1]} In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory. In some literature edges are referred to as hyperlinks or connectors.^{[2]}
Special kinds of hypergraphs include, besides kuniform ones, clutters, where no edge appears as a subset of another edge; and abstract simplicial complexes, which contain all subsets of every edge.
The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
Contents

Terminology 1

Bipartite graph model 2

Acyclicity 3

Isomorphism and equality 4

Symmetric hypergraphs 5

Transversals 6

Incidence matrix 7

Hypergraph coloring 8

Partitions 9

Theorems 10

Hypergraph drawing 11

Generalizations 12

See also 13

Notes 14

References 15
Terminology
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called subhypergraphs, partial hypergraphs and section hypergraphs.
Let H=(X,E) be the hypergraph consisting of vertices

X = \lbrace x_i  i \in I_v \rbrace,
and having edge set

E = \lbrace e_i  i\in I_e, e_i \subseteq X \rbrace,
where I_v and I_e are the index sets of the vertices and edges respectively.
A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph H_A induced by a subset A of X is defined as

H_A=\left(A, \lbrace e_i \cap A  e_i \cap A \neq \varnothing \rbrace \right).
The partial hypergraph is a hypergraph with some edges removed. Given a subset J \subset I_e of the edge index set, the partial hypergraph generated by J is the hypergraph

\left(X, \lbrace e_i  i\in J \rbrace \right).
Given a subset A\subseteq X, the section hypergraph is the partial hypergraph

H \times A = \left(A, \lbrace e_i  i\in I_e, e_i \subseteq A \rbrace \right).
The dual H^* of H is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by \lbrace e_i \rbrace and whose edges are given by \lbrace X_m \rbrace where

X_m = \lbrace e_i  x_m \in e_i \rbrace.
When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, i.e.,

\left(H^*\right)^* = H.
A connected graph G with the same vertex set as a connected hypergraph H is a host graph for H if every hyperedge of H induces a connected subgraph in G. For a disconnected hypergraph H, G is a host graph if there is a bijection between the connected components of G and of H, such that each connected component G' of G is a host of the corresponding H'.
A hypergraph is bipartite if and only if its vertices can be partitioned into two classes U and V in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes.
The 2section (or clique 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.
Bipartite graph model
A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the partitions of BG, and (x_{1}, e_{1}) are connected with an edge if and only if vertex x_{1} is contained in edge e_{1} in H. 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 called incidence graph.
Acyclicity
In contrast with ordinary undirected graphs for which there is a single natural notion of cycles and acyclic graphs, there are multiple natural nonequivalent definitions of acyclicity for hypergraphs which collapse to ordinary graph acyclicity for the special case of ordinary graphs.
A first definition of acyclicity for hypergraphs was given by Claude Berge:^{[3]} a hypergraph is Bergeacyclic if its incidence graph (the bipartite graph defined above) is acyclic. This definition is very restrictive: for instance, if a hypergraph has some pair v \neq v' of vertices and some pair f \neq f' of hyperedges such that v, v' \in f and v, v' \in f', then it is Bergecyclic. Bergecyclicity can obviously be tested in linear time by an exploration of the incidence graph.
We can define a weaker notion of hypergraph acyclicity,^{[4]} 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 being chordal; it is also equivalent to reducibility to the empty graph through the GYO algorithm^{[5]}^{[6]} (also known as Graham's algorithm), a confluent iterative process which removes hyperedges using a generalized definition of ears. In the domain of database theory, it is known that a database schema enjoys certain desirable properties if its underlying hypergraph is αacyclic.^{[7]} Besides, αacyclicity is also related to the expressiveness of the guarded fragment of firstorder logic.
We can test in linear time if a hypergraph is αacyclic.^{[8]}
Note that αacyclicity has the counterintuitive 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^{[9]} 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^{[9]} to an earlier definition by Graham.^{[6]} The notion of γacyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to Bachman diagrams. Both βacyclicity and γacyclicity can be tested in polynomial time.
Those four notions of acyclicity are comparable: Bergeacyclicity implies γacyclicity which implies βacyclicity which implies αacyclicity. However, none of the reverse implications hold, so those four notions are different.^{[9]}
Isomorphism and equality
A hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.
A hypergraph H=(X,E) is isomorphic to a hypergraph G=(Y,F), written as H \simeq G if there exists a bijection

\phi:X \to Y
and a permutation \pi of I such that

\phi(e_i) = f_{\pi(i)}
The bijection \phi is then called the isomorphism of the graphs. Note that

H \simeq G if and only if H^* \simeq G^*.
When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism. One says that H is strongly isomorphic to G if the permutation is the identity. One then writes H \cong G. 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 of equivalence, and also of equality. One says that H is equivalent to G, and writes H\equiv G if the isomorphism \phi has

\phi(x_n) = y_n
and

\phi(e_i) = f_{\pi(i)}
Note that

H\equiv G if and only if H^* \cong G^*
If, in addition, the permutation \pi is the identity, one says that H equals G, and writes H=G. Note that, with this definition of equality, graphs are selfdual:

\left(H^*\right) ^* = H
A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph H (= (X, E)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H).
Examples
Consider the hypergraph H with edges

H = \lbrace e_1 = \lbrace a,b \rbrace, e_2 = \lbrace b,c \rbrace, e_3 = \lbrace c,d \rbrace, e_4 = \lbrace d,a \rbrace, e_5 = \lbrace b,d \rbrace, e_6 = \lbrace a,c \rbrace \rbrace
and

G = \lbrace f_1 = \lbrace \alpha,\beta \rbrace, f_2 = \lbrace \beta,\gamma \rbrace, f_3 = \lbrace \gamma,\delta \rbrace, f_4 = \lbrace \delta,\alpha \rbrace, f_5 = \lbrace \alpha,\gamma \rbrace, f_6 = \lbrace \beta,\delta \rbrace \rbrace
Then clearly H and G are isomorphic (with \phi(a)=\alpha, etc.), but they are not strongly isomorphic. So, for example, in H, vertex a meets edges 1, 4 and 6, so that,

e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace
In graph G, there does not exist any vertex that meets edges 1, 4 and 6:

f_1 \cap f_4 \cap f_6 = \varnothing
In this example, H and G are equivalent, H\equiv G, and the duals are strongly isomorphic: H^*\cong G^*.
Symmetric hypergraphs
The rank r(H) of a hypergraph H is the maximum cardinality of any of the edges in the hypergraph. If all edges have the same cardinality k, the hypergraph is said to be uniform or kuniform, or is called a khypergraph. A graph is just a 2uniform hypergraph.
The degree d(v) of a vertex v is the number of edges that contain it. H is kregular if every vertex has degree k.
The dual of a uniform hypergraph is regular and vice versa.
Two vertices x and y of H are called symmetric if there exists an automorphism such that \phi(x)=y. Two edges e_i and e_j are said to be symmetric if there exists an automorphism such that \phi(e_i)=e_j.
A hypergraph is said to be vertextransitive (or vertexsymmetric) if all of its vertices are symmetric. Similarly, a hypergraph is edgetransitive if all edges are symmetric. If a hypergraph is both edge and vertexsymmetric, then the hypergraph is simply transitive.
Because of hypergraph duality, the study of edgetransitivity is identical to the study of vertextransitivity.
Transversals
A transversal (or "hitting set") of a hypergraph H = (X, E) is a set T\subseteq X that has nonempty intersection with every edge. A transversal T is called minimal if no proper subset of T is a transversal. The transversal hypergraph of H is the hypergraph (X, F) whose edge set F consists of all minimal transversals of H.
Computing the transversal hypergraph has applications in combinatorial optimization, in game theory, and in several fields of computer science such as machine learning, indexing of databases, the satisfiability problem, data mining, and computer program optimization.
Incidence matrix
Let V = \{v_1, v_2, ~\ldots, ~ v_n\} and E = \{e_1, e_2, ~ \ldots ~ e_m\}. Every hypergraph has an n \times m incidence matrix A = (a_{ij}) where

a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right.
The transpose A^t of the incidence matrix defines a hypergraph H^* = (V^*,\ E^*) called the dual of H, where V^* is an melement set and E^* is an nelement set of subsets of V^*. For v^*_j \in V^* and e^*_i \in E^*, ~ v^*_j \in e^*_i if and only if a_{ij} = 1.
Hypergraph coloring
Classic hypergraph coloring is assigning one of the colors from set \{1,2,3,...\lambda\} 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. 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 to k colors are referred to as kcolorable. The 2colorable hypergraphs are exactly the bipartite ones.
There are many generalizations of classic hypergraph coloring. One of them is the socalled 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. See http://spectrum.troy.edu/voloshin/mh.html for details.
Partitions
A partition theorem due to E. Dauber^{[10]} states that, for an edgetransitive hypergraph H=(X,E), there exists a partition

(X_1, X_2,\cdots,X_K)
of the vertex set X such that the subhypergraph H_{X_k} generated by X_k is transitive for each 1\le k \le K, and such that

\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)
where r(H) is the rank of H.
As a corollary, an edgetransitive hypergraph that is not vertextransitive is bicolorable.
Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design^{[11]} and parallel computing.^{[12]}^{[13]}^{[14]}
Theorems
Many theorems and concepts involving graphs also hold for hypergraphs. Ramsey's theorem and Line graph of a hypergraph are typical examples. Some methods for studying symmetries of graphs extend to hypergraphs.
Two prominent theorems are the Erdős–Ko–Rado theorem and the Kruskal–Katona theorem on uniform hypergraphs.
Hypergraph drawing
This
circuit 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 standard graph 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.^{[15]}^{[16]} If the vertices are represented as points, the hyperedges may also be shown as smooth curves that connect sets of points, or as simple closed curves that enclose sets of points.^{[17]}^{[18]}
An order4 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,^{[19]} 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 ordern Venn diagram, for instance, may be viewed as a subdivision drawing of a hypergraph with n hyperedges (the curves defining the diagram) and 2^{n} − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomialtime recognition of planar graphs, it is NPcomplete to determine whether a hypergraph has a planar subdivision drawing,^{[20]} 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.^{[21]}
Generalizations
One possible generalization of a hypergraph is to allow edges to point at other edges. 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, ad infinitum. In essence, every edge is just an internal node of a tree or directed acyclic graph, and vertexes 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). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout computer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of term algebra; edges correspond to terms and vertexes correspond to constants or variables.
For such a hypergraph, set membership then provides an ordering, but the ordering is neither a partial order nor a preorder, since it is not transitive. The graph corresponding to the Levi graph of this generalization is a directed acyclic graph. Consider, for example, the generalized hypergraph whose vertex set is V= \{a,b\} and whose edges are e_1=\{a,b\} and e_2=\{a,e_1\}. Then, although b\in e_1 and e_1\in e_2, it is not true that b\in e_2. However, the transitive closure of set membership for such hypergraphs does induce a partial order, and "flattens" the hypergraph into a partially ordered set.
Alternately, edges can be allowed to point at other edges, (irrespective of the requirement that the edges be ordered as directed, acyclic graphs). This allows graphs with edgeloops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges e_1 and e_2, and zero vertices, so that e_1 = \{e_2\} and e_2 = \{e_1\}. As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. 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 longer bipartite, but is rather just some general directed graph.
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. Thus, for the above example, the incidence matrix is simply

\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right].
See also
Notes

^ .

^ Judea Pearl, in HEURISTICS Intelligent Search Strategies for Computer Problem Solving, Addison Wesley (1984), p. 25.

^ Claude Berge, Graphs and Hypergraphs

^ C. Beeri, R. Fagin, D. Maier, M. Yannakakis, On the Desirability of Acyclic Database Schemes

^ C. T. Yu and M. Z. Özsoyoğlu. An algorithm for treequery membership of a distributed query. In Proc. IEEE COMPSAC, pages 306312, 1979

^ ^{a} ^{b} M. H. Graham. On the universal relation. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979

^ S. Abiteboul, R. B. Hull, V. Vianu, Foundations of Databases

^ R. E. Tarjan, M. Yannakakis. Simple lineartime algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. on Computing, 13(3):566579, 1984.

^ ^{a} ^{b} ^{c} Ronald Fagin, Degrees of Acyclicity for Hypergraphs and Relational Database Schemes

^ E. Dauber, in Graph theory, ed. F. Harary, Addison Wesley, (1969) p. 172.

^ 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,

^ Hendrickson, B., Kolda, T.G. (2000), "Graph partitioning models for parallel computing", Parallel Computing 26 (12): 1519–1545,

^ Catalyurek, U.V.; C. Aykanat (1995). A Hypergraph Model for Mapping Repeated Sparse MatrixVector Product Computations onto Multicomputers. Proc. International Conference on Hi Performance Computing (HiPC'95).

^ Catalyurek, U.V.; C. Aykanat (1999), "HypergraphPartitioning Based Decomposition for Parallel SparseMatrix Vector Multiplication", IEEE Transactions on Parallel and Distributed Systems (IEEE) 10 (7): 673–693,

^ Sander, G. (2003), "Layout of directed hypergraphs with orthogonal hyperedges", .

^ Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Orthogonal hypergraph drawing for improved visibility" (PDF), .

^ Mäkinen, Erkki (1990), "How to draw a hypergraph", International Journal of Computer Mathematics 34 (3): 177–185, .

^ Bertault, François; .

^ Kaufmann, Michael; van Kreveld, Marc; Speckmann, Bettina (2009), "Subdivision drawings of hypergraphs", .

^ .

^ Buchin, Kevin; van Kreveld, Marc; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2010), "On planar supports for hypergraphs", .
References

Claude Berge, "Hypergraphs: Combinatorics of finite sets". NorthHolland, 1989.

Claude Berge, Dijen RayChaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 SpringerVerlag

Hazewinkel, Michiel, ed. (2001), "Hypergraph",

Alain Bretto, "Hypergraph Theory: an Introduction", Springer, 2013.

Vitaly I. Voloshin. "Coloring Mixed Hypergraphs: Theory, Algorithms and Applications". Fields Institute Monographs, American Mathematical Society, 2002.

Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.

This article incorporates material from hypergraph on PlanetMath, which is licensed under the Creative Commons Attribution/ShareAlike License.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.