page_title: Hypergraph
hierarchical_section_title: Hypergraph
caption_attribution_description: English: An alternative representation of hypergraph. Edges are represented as vertical lines connecting the set of vertices. Vertices are aligned on the left.
context_page_description: 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 hypergraph is a pair where is a set of elements called nodes or vertices, and is a set of non-empty subsets of called hyperedges or edges. Therefore, is a subset of, where is the power set of. The size of the vertex set is called the order of the hypergraph, and the size of edges set is the size of the hypergraph.
  While graph edges are 2-element subsets of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. A hypergraph is also called a set system or a family of sets drawn from the universal set.
  Hypergraphs can be viewed as incidence structures.
context_section_description: 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 hypergraph  is a pair  where  is a set of elements called nodes or vertices, and  is a set of non-empty subsets of  called hyperedges or edges. Therefore,  is a subset of , where  is the power set of . The size of the vertex set is called the order of the hypergraph, and the size of edges set is the size of the hypergraph. 
  While graph edges are 2-element subsets of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting k nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. A 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, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs.
  Hypergraphs have many other names.  In computational geometry, a hypergraph may sometimes be called a range space and then the hyperedges are called ranges.
  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.
  The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
caption: Alternative representation of the hypergraph reported in the figure above, called PAOH.[1] Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges.
exif: {}