(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, ...} ∈ 2^{V}}. (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