(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 relations "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
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 18 October 2007.
HTML page formatted Thu Oct 18 16:16:48 2007.
Cite this as:
Paul E. Black, "hypergraph", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 18 October 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/hypergraph.html
