Hypergraph(超图)
An example hypergraph, with
X = {v1,v2,v3,v4,v5,v6,v7} and E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v5,v6}, {v4}}.
in mathematics, a hypergraph is a generalization of a graph, where anedge can connect any number of vertices. Formally, a hypergraph H is a pairH = (X,E) where X is a set of elements, called nodes or vertices, and Eis a set of non-empty subsets of X called hyperedges or links. Therefore,E is a subset of
, where
is the power set of X.
While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often useful 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, it is a collection of sets of size k.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of triples, and so on.
A hypergraph is also called a set system or a family of sets drawn from the universal set X. Hypergraphs can be viewed as incidence structuresand vice versa. In particular, there is a Levi graph corresponding to every hypergraph, and vice versa. Incomputational geometry, a hypergraph may be called a range space and the hyperedges are called ranges. Special cases of hypergraphs include the clutter, where no edge appears as a subset of another edge; and theabstract simplicial complex, which contains all subsets of every edge. The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
Contents [hide] [1]
? ? ?
equality
1 Terminology 2 Bipartite graph model 3 Isomorphism and
o ?
3.1 Examples
4 Symmetric
hypergraphs
? ? ? ? ? ? ? ? ? ?
5 Transversals 6 Incidence matrix 7 Hypergraph coloring 8 Partitions 9 Theorems
10 Hypergraph drawing 11 Generalizations 12 See also 13 Notes 14 References
Terminology
Because hypergraph links can have any cardinality, there are multiple, distinct notions of the concept of a subgraph: subhypergraphs, partial hypergraphs and section hypergraphs. Let H = (X,E) be the hypergraph consisting of vertices
that is, the vertices are indexed by an index
with the edges ei indexed by an index
.
, and the edge set is
A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph HA induced by a subset Aof X is defined as
The partial hypergraph is a hypergraph with some edges removed. Given a subset hypergraph
of the index set I, the partial hypergraph generated by J is the
Given a subset
, the section hypergraph is the partial hypergraph
The dual H of H is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by {ei}and whose edges are given by {Xn} where
When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is aninvolution, i.e.,
A connected graph G with the same vertex set as a connected hypergraph H is a host graph for H if every hyperedge of H induces a connected subgraph in G. For a disconnected hypergraph H, G is a host graph if there is a bijection between the connected components of G and of H, such that each connected component G' of G is a host of the corresponding H'.
The primal graph of a hypergraph is the graph with the same vertices of the
hypergraph, and edges between all pairs of vertices contained in the same hyperedge. The primal graph is sometimes also known as the Gaifman graphof the hypergraph
*
Bipartite graph model
A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the parts of BG, and (X1,E1) are connected with an edge if and only if they are incident to each other in H. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the way described above.
Isomorphism and equality
hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.
A hypergraph H = (X,E) is isomorphic to a hypergraph G = (Y,F), written as there exists a bijection
and a permutation π of I such that
if
φ(ei) = fπ(i)
超图 hypergraph
