Hypergraph

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.
PAOH visualization of a hypergraph
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 .

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.

An undirected hypergraph is an undirected graph whose edges connect not just two vertices, but an arbitrary number.[2] 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.[3] 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.[4]

The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.

  1. ^ Valdivia, Paola; Buono, Paolo; Plaisant, Catherine; Dufournaud, Nicole; Fekete, Jean-Daniel (2020). "Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization" (PDF). IEEE Transactions on Visualization and Computer Graphics. 26 (1). IEEE: 12. doi:10.1109/TVCG.2019.2933196. eISSN 1941-0506. ISSN 1077-2626. PMID 31398121. S2CID 199518871. Archived (PDF) from the original on 2021-01-26. Retrieved 2020-09-08.
  2. ^ Ouvrard, Xavier (2020), "Hypergraphs: an introduction and review", arXiv:2002.05014 [cs.DM].
  3. ^ Haussler, David; Welzl, Emo (1987), "ε-nets and simplex range queries", Discrete and Computational Geometry, 2 (2): 127–151, doi:10.1007/BF02187876, MR 0884223.
  4. ^ Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishing Company. p. 25. ISBN 978-0-201-05594-8. Archived from the original on 2023-02-04. Retrieved 2021-06-12.