Hypergraph

A hypergraph is a generalization of a graph in which edges, called hyperedges, can connect any number of vertices. Formally, a hypergraph H is a pair (V, E), where V is a set of vertices and E is a set of nonempty subsets of V. An ordinary graph is the special case where every hyperedge contains exactly two vertices. Hyperedges may have any size; a k-uniform hypergraph has all hyperedges of size k. If every vertex has the same degree, the hypergraph is called r-regular.

Representations: Hypergraphs can be represented by an incidence matrix of size |V| × |E| with entry 1 when a vertex lies in a hyperedge. They can also be modeled by a bipartite incidence graph between V and E. The dual hypergraph, obtained by interchanging vertices and hyperedges, has the roles reversed.

Variants: A hypergraph is linear when any two hyperedges intersect in at most one vertex. Acyclicity has several meanings in hypergraphs; Berge-acyclic is one. Transversals or hitting sets are vertex sets that meet every hyperedge. A 2-uniform hypergraph corresponds exactly to a simple graph.

Applications: Hypergraphs model relations among multiple objects and appear in database theory, circuit design, and knowledge representation. They are used in clustering, document categorization, and machine learning; in parallel computing for partitioning workloads; and in social network analysis to capture group interactions beyond pairwise ties.

Computational aspects: Many problems generalize from graphs to hypergraphs; for example, hypergraph matching seeks a maximum collection of disjoint hyperedges and is NP-hard in general. Special cases such as uniform or linear hypergraphs admit more efficient approaches.