NIST

hypergraph

(data structure)

Definition: A graph whose hyperedges connect two or more vertices.

Formal Definition: A hypergraph G can be defined as a pair (V, E), where V is a set of vertices, and E is a set of hyperedges between the vertices. Each hyperedge is a set of vertices: E ⊆ {{u, v, ...} ∈ 2V}. (Hyperedges are undirected.)

Generalization (I am a kind of ...)
undirected graph.

Aggregate child (... is a part of or used in me.)
hyperedge, vertex.

See also multigraph.

Note: Consider "family," a relation connecting two or more people. If each person is a vertex, a family hyperedge connects the father, the mother, and all of their children. So G = (people, family) is a hypergraph. Contrast this with the binary relation "married to," which connects a man and a woman, or "child of," which is directed from a child to his or her father or mother.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 26 August 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "hypergraph", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 26 August 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/hypergraph.html