Hypergraph
|
|
In mathematics, the concept of hypergraph generalizes the notion of a graph.
Informally a hypergraph is a graph whose edges, instead of each connecting just two vertices, connect a non null number of vertices. For any set X, let X[m] be the set of subsets of X whose elements have precisely m members (these are the m-sets or m-subsets of X, and can be counted by a binomial coefficient in case X is finite). Then an m-hypergraph consists of a set X of vertices and a subset E of X[m]. A hypergraph is then defined to be a pair of sets (X,E) such that the pair constitute an m-hypergraph for some m. Commonly X is finite but this need not always be the case.
It is also possible to define a hypergraph in a more general way as a pair of sets (X,E) where E is some arbitrary subset of the power set of X. In this case the number of the vertices in each edge is not constant from one edge to the next. This definition is less commonly encountered, but in such contexts the term uniform is used to mean a hypergraph whose edges have an equal number of elements. A synonym for hypergraph in this sense is set system, or family of sets, drawn from X as universal set.
Many theorems involving graphs also hold for hypergraphs. See Ramsey's theorem for a typical example. Some methods of studying the symmetries of graphs extend to hypergraphs too. For instance, a hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that one edge is mapped to another edge. An hypergraph isomorphism is a homomorphism that is invertible. A hypergraph automorphism is an isomorphism from a vertex set into itself. The set of automorphisms of a hypergraph H (=(X,E)) is a group under composition. This group is called the automorphism group of the hypergraph, written Aut(H). The collection of hypergraphs is clearly a category with hypergraph homomorphisms as morphisms.
A property of graphs that encourages their study, is that it is easy to draw a representation of them on a piece of paper. This is not so for hypergraphs and so their study tends to be conducted using the nomenclature of set theory rather than the more pictorial descriptions (for instance 'trees','forests' and 'cycles') of graph theory.
A transversal or hitting set of the hypergraph H=(X,E) is a set T⊂X that has nonempty intersection with all the edges in E. The transversal hypergraph of H is the hypergraph (X,F) whose edge set F consists of all transversals of H. Computing the transversal hypergraph has applications in machine learning and other fields of computer science.