In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, a directed hypergraph is a pair , where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of . Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain.
The order of a hypergraph is the number of vertices in . The size of the hypergraph is the number of edges in . The order 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 a directed 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.
Under one definition, an undirected hypergraph is a directed hypergraph which has a symmetric edge set: If then . For notational simplicity one can remove the "duplicate" hyperedges since the modifier "undirected" is precisely informing us that they exist: If then where means implicitly in.
While graph edges connect only 2 nodes, hyperedges connect an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a k-uniform 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 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. An undirected hypergraph is also called a set system or a family of sets drawn from the universal set.
Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, every bipartite 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. In computational geometry, an undirected hypergraph may sometimes be called a range space and then the hyperedges are called ranges. 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.
The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
Applications
Undirected hypergraphs are useful in modelling such things as satisfiability problems, databases, machine learning, and Steiner tree problems. They have been extensively used in machine learning tasks as the data model and classifier regularization (mathematics). The applications include recommender system (communities as hyperedges), image retrieval (correlations as hyperedges), and bioinformatics (biochemical interactions as hyperedges). Representative hypergraph learning techniques include hypergraph spectral clustering that extends the spectral graph theory with hypergraph Laplacian, and hypergraph semi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results. For large scale hypergraphs, a distributed framework built using Apache Spark is also available.
Directed hypergraphs can be used to model things including telephony applications, detecting money laundering, operations research, and transportation planning. They can also be used to model Horn-satisfiability.
Generalizations of concepts from graphs
Many theorems and concepts involving graphs also hold for hypergraphs, in particular:
Matching in hypergraphs; Vertex cover in hypergraphs (also known as: transversal); Line graph of a hypergraph; Hypergraph grammar - created by augmenting a class of hypergraphs with a set of replacement rules; Ramsey's theorem; Erdős–Ko–Rado theorem; Kruskal–Katona theorem on uniform hypergraphs; Hall-type theorems for hypergraphs.
In directed hypergraphs: transitive closure, and shortest path problems.
Hypergraph drawing
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.