 Hypergraph

In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = (X,E) where X is a set of elements, called nodes or vertices, and E is a set of nonempty 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 kuniform 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 2uniform hypergraph is a graph, a 3uniform 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 structures and vice versa. In particular, there is a Levi graph corresponding to every hypergraph, and vice versa. In computational geometry, a hypergraph may be called a range space and the hyperedges are called ranges.^{[1]} In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory.
Special cases of hypergraphs include the clutter, where no edge appears as a subset of another edge; and the abstract simplicial complex, which contains all subsets of every edge.
The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
Contents
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 , and the edge set is
with the edges e_{i} indexed by an index .
A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph H_{A} induced by a subset A of X is defined as
The partial hypergraph is a hypergraph with some edges removed. Given a subset of the index set I, the partial hypergraph generated by J is the hypergraph
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 {e_{i}} and whose edges are given by {X_{m}} where
When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, 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 graph of 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 partitions of BG, and (x_{1}, e_{1}) are connected with an edge if and only if vertex x_{1} is contained in edge e_{1} in H. Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.
Isomorphism and equality
A 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 if there exists a bijection
and a permutation π of I such that
 ϕ(e_{i}) = f_{π(i)}
The bijection ϕ is then called the isomorphism of the graphs. Note that
 if and only if .
When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism. One says that H is strongly isomorphic to G if the permutation is the identity. One then writes . Note that all strongly isomorphic graphs are isomorphic, but not viceversa.
When the vertices of a hypergraph are explicitly labeled, one has the notions of equivalence, and also of equality. One says that H is equivalent to G, and writes if the isomorphism ϕ has
 ϕ(x_{n}) = y_{n}
and
 ϕ(e_{i}) = f_{π(i)}
Note that
 if and only if
If, in addition, the permutation π is the identity, one says that H equals G, and writes H = G. Note that, with this definition of equality, graphs are selfdual:
A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph H (= (X, E)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H).
Examples
Consider the hypergraph H with edges
 H = {e_{1} = {a,b},e_{2} = {b,c},e_{3} = {c,d},e_{4} = {d,a},e_{5} = {b,d},e_{6} = {a,c}}
and
 G = {f_{1} = {α,β},f_{2} = {β,γ},f_{3} = {γ,δ},f_{4} = {δ,α},f_{5} = {α,γ},f_{6} = {β,δ}}
Then clearly H and G are isomorphic (with ϕ(a) = α, etc.), but they are not strongly isomorphic. So, for example, in H, vertex a meets edges 1, 4 and 6, so that,
In graph G, there does not exist any vertex that meets edges 1, 4 and 6:
In this example, H and G are equivalent, , and the duals are strongly isomorphic: .
Symmetric hypergraphs
The rank r(H) of a hypergraph H is the maximum cardinality of any of the edges in the hypergraph. If all edges have the same cardinality k, the hypergraph is said to be uniform or kuniform, or is called a khypergraph. A graph is just a 2uniform hypergraph.
The degree d(v) of a vertex v is the number of edges that contain it. H is kregular if every vertex has degree k.
The dual of a uniform hypergraph is regular and viceversa.
Two vertices x and y of H are called symmetric if there exists an automorphism such that ϕ(x) = y. Two edges e_{i} and e_{j} are said to be symmetric if there exists an automorphism such that ϕ(e_{i}) = e_{j}.
A hypergraph is said to be vertextransitive (or vertexsymmetric) if all of its vertices are symmetric. Similarly, a hypergraph is edgetransitive if all edges are symmetric. If a hypergraph is both edge and vertexsymmetric, then the hypergraph is simply transitive.
Because of hypergraph duality, the study of edgetransitivity is identical to the study of vertextransitivity.
Transversals
A transversal or hitting set of a hypergraph H = (X, E) is a set that has nonempty intersection with every edge. A transversal T is called minimal if no proper subset of T is a transversal. The transversal hypergraph of H is the hypergraph (X, F) whose edge set F consists of all minimal transversals of H. Computing the transversal hypergraph has applications in machine learning and other fields of computer science, as game theory, indexing of databases, SAT problem, data mining and optimization.
Incidence matrix
Let and . Every hypergraph has an incidence matrix A = (a_{ij}) where
The transpose A^{t} of the incidence matrix defines a hypergraph called the dual of H, where V ^{*} is an melement set and E ^{*} is an nelement set of subsets of V ^{*} . For and if and only if a_{ij} = 1.
Hypergraph coloring
Hypergraph colouring is defined as follows. Let H = (V,E) be a hypergraph such that . Then is a proper colouring of H if and only if, for all there exists such that .
In other words: For every edge in the graph having at least two nodes as endpoints, the nodes this edge connects are not all of the same color.
Partitions
A partition theorem due to E. Dauber^{[2]} states that, for an edgetransitive hypergraph H = (X,E), there exists a partition
of the vertex set X such that the subhypergraph generated by X_{k} is transitive for each , and such that
where r(H) is the rank of H.
As a corollary, an edgetransitive hypergraph that is not vertextransitive is bicolorable.
Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design^{[3]} and parallel computing.^{[4]}^{[5]}^{[6]}
Theorems
Many theorems and concepts involving graphs also hold for hypergraphs. Ramsey's theorem and Line graph of a hypergraph are typical examples. Some methods for studying symmetries of graphs extend to hypergraphs.
Two prominent theorems are the Erdős–Ko–Rado theorem and the Kruskal–Katona theorem on uniform hypergraphs.
Hypergraph drawing
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.
In one possible visual representation for hypergraphs, similar to the standard graph drawing style in which curves in the plane are used to depict graph edges, a hypergraph's vertices are depicted as points, disks, or boxes, and its hyperedges are depicted as trees that have the vertices as their leaves.^{[7]}^{[8]} If the vertices are represented as points, the hyperedges may also be shown as smooth curves that connect sets of points, or as simple closed curves that enclose sets of points.^{[9]}^{[10]}
In another style of hypergraph visualization, the subdivision model of hypergraph drawing,^{[11]} the plane is subdivided into regions, each of which represents a single vertex of the hypergraph. The hyperedges of the hypergraph are represented by contiguous subsets of these regions, which may be indicated by coloring, by drawing outlines around them, or both. An ordern Venn diagram, for instance, may be viewed as a subdivision drawing of a hypergraph with n hyperedges (the curves defining the diagram) and 2^{n} − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomialtime recognition of planar graphs, it is NPcomplete to determine whether a hypergraph has a planar subdivision drawing,^{[12]} but the existence of a drawing of this type may be tested efficiently when the adjacency pattern of the regions is constrained to be a path, cycle, or tree.^{[13]}
Generalizations
One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, ad infinitum. Set membership then provides an ordering, but the ordering is neither a partial order nor a preorder, since it is not transitive. The graph corresponding to the Levi graph of this generalization is a directed acyclic graph. Consider, for example, the generalized hypergraph whose vertex set is V = {a,b} and whose edges are e_{1} = {a,b} and e_{2} = {a,e_{1}}. Then, although and , it is not true that . However, the transitive closure of set membership for such hypergraphs does induce a partial order, and "flattens" the hypergraph into a partially ordered set.
Alternately, edges can be allowed to point at other edges, (irrespective of the requirement that the edges be ordered as directed, acyclic graphs). This allows graphs with edgeloops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges e_{1} and e_{2}, and zero vertices, so that e_{1} = {e_{2}} and e_{2} = {e_{1}}. As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer bipartite, but is rather just some general directed graph.
The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply
See also
Notes
 ^ D. Haussler and E. Welzl. εnets and simplex range queries. Discrete Compututational Geometry, 2:127–151, 1987.
 ^ E. Dauber, in Graph theory, ed. F. Harary, Addison Wesley, (1969) p. 172.
 ^ Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (March 1999), "Multilevel hypergraph partitioning: applications in VLSI domain", IEEE Transactions on Very Large Scale Integration (VLSI) Systems 7 (1): 69–79, doi:10.1109/92.748202, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=748202.
 ^ Hendrickson, B., Kolda, T.G. (2000), "Graph partitioning models for parallel computing", Parallel Computing 26 (12): 1519–1545, doi:10.1016/S01678191(00)00048X.
 ^ Catalyurek, U.V.; C. Aykanat (1995). "A Hypergraph Model for Mapping Repeated Sparse MatrixVector Product Computations onto Multicomputers". Proc. Internation Conference on Hi Performance Computing (HiPC'95).
 ^ Catalyurek, U.V.; C. Aykanat (1999), "HypergraphPartitioning Based Decomposition for Parallel SparseMatrix Vector Multiplication", IEEE Transactions on Parallel and Distributed Systems (IEEE) 10 (7): 673–693, doi:10.1109/71.780863, http://doi.ieeecomputersociety.org/10.1109/71.780863.
 ^ Sander, G. (2003), "Layout of directed hypergraphs with orthogonal hyperedges", Proc. 11th International Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, 2912, SpringerVerlag, pp. 381–386, http://gdea.informatik.unikoeln.de/585/1/hypergraph.ps.
 ^ Eschbach, Thomas; Günther, Wolfgang; Becker, Bernd (2006), "Orthogonal hypergraph drawing for improved visibility", Journal of Graph Algorithms and Applications 10 (2): 141–157, http://jgaa.info/accepted/2006/EschbachGuentherBecker2006.10.2.pdf.
 ^ Mäkinen, Erkki (1990), "How to draw a hypergraph", International Journal of Computer Mathematics 34 (3): 177–185, doi:10.1080/00207169008803875.
 ^ Bertault, François; Eades, Peter (2001), "Drawing hypergraphs in the subset standard", Proc. 8th International Symposium on Graph Drawing (GD 2000), Lecture Notes in Computer Science, 1984, SpringerVerlag, pp. 45–76, doi:10.1007/3540445412_15.
 ^ Kaufmann, Michael; van Kreveld, Marc; Speckmann, Bettina (2009), "Subdivision drawings of hypergraphs", Proc. 16th International Symposium on Graph Drawing (GD 2008), Lecture Notes in Computer Science, 5417, SpringerVerlag, pp. 396–407, doi:10.1007/9783642002199_39.
 ^ Johnson, David S.; Pollak, H. O. (2006), "Hypergraph planarity and the complexity of drawing Venn diagrams", Journal of graph theory 11 (3): 309–325, doi:10.1002/jgt.3190110306.
 ^ Buchin, Kevin; van Kreveld, Marc; Meijer, Henk; Speckmann, Bettina; Verbeek, Kevin (2010), "On planar supports for hypergraphs", Proc. 17th International Symposium on Graph Drawing (GD 2009), Lecture Notes in Computer Science, 5849, SpringerVerlag, pp. 345–356, doi:10.1007/9783642118050_33.
References
 Claude Berge, Dijen RayChaudhuri, "Hypergraph Seminar, Ohio State University 1972", Lecture Notes in Mathematics 411 SpringerVerlag
 This article incorporates material from hypergraph on PlanetMath, which is licensed under the Creative Commons Attribution/ShareAlike License.
 Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". Nova Science Publishers, Inc., 2009.
Categories: Hypergraphs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Hypergraph — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… … Deutsch Wikipedia
hypergraph — noun A generalization of a graph, in which edges can connect any number of vertices … Wiktionary
HypergraphTeleskop — Ein Hypergraph Teleskop ist ein Spiegelteleskop, das ähnlich aufgebaut ist wie ein Cassegrain Teleskop (parabolischer Primärspiegel, hyperbolischer Sekundärspiegel). Um die optische Qualität für die Fotografie zu erhöhen, wird beim Hypergraph wie … Deutsch Wikipedia
Line graph of a hypergraph — The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of … Wikipedia
Symmetric hypergraph theorem — The Symmetric hypergraph theorem is a theorem in combinatorics that puts an upper bound on the chromatic number of a graph (or hypergraph in general). The original reference for this paper is unknown at the moment, and has been called folklore [R … Wikipedia
Kuniformer Hypergraph — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Nachbarschaft und Grad sind grundlegende Begriffe der… … Deutsch Wikipedia
Uniformer Hypergraph — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Nachbarschaft und Grad sind grundlegende Begriffe der… … Deutsch Wikipedia
Conformal hypergraph — In graph theory, a branch of mathematics, a hypergraph H is conformal if all the maximal cliques of the 2 section of H are edges of H . Here, the 2 section has an edge F if F contains two vertices and is contained in some edge of H , or if F… … Wikipedia
Clique complex — “Whitney complex” redirects here. For the Mississippi sports facility, see Davey Whitney Complex. Clique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that… … Wikipedia
Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… … Wikipedia