Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices.
Hence any standard graph theoretic concept that is independent of the edge orders
is an undirected graph whose edges connect not just two vertices, but an arbitrary number.
[8] They have been extensively used in machine learning tasks as the data model and classifier regularization (mathematics).
[15] For large scale hypergraphs, a distributed framework[7] built using Apache Spark is also available.
Directed hypergraphs can be used to model things including telephony applications,[16] detecting money laundering,[17] operations research,[18] and transportation planning.
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.
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 order-n Venn diagram, for instance, may be viewed as a subdivision drawing of a hypergraph with n hyperedges (the curves defining the diagram) and 2n − 1 vertices (represented by the regions into which these curves subdivide the plane).
In contrast with the polynomial-time recognition of planar graphs, it is NP-complete to determine whether a hypergraph has a planar subdivision drawing,[26] 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.
[27] An alternative representation of the hypergraph called PAOH[1] is shown in the figure on top of this article.
to every vertex of a hypergraph in such a way that each hyperedge contains at least two vertices of distinct colors.
One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed.
where 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 vertex x1 is contained in edge e1 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.
Berge-cyclicity can obviously be tested in linear time by an exploration of the incidence graph.
We can define a weaker notion of hypergraph acyclicity,[6] later termed α-acyclicity.
This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph being chordal; it is also equivalent to reducibility to the empty graph through the GYO algorithm[32][33] (also known as Graham's algorithm), a confluent iterative process which removes hyperedges using a generalized definition of ears.
[34] Besides, α-acyclicity is also related to the expressiveness of the guarded fragment of first-order logic.
Motivated in part by this perceived shortcoming, Ronald Fagin[36] defined the stronger notions of β-acyclicity and γ-acyclicity.
We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent[36] to an earlier definition by Graham.
[33] The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to Bachman diagrams.
Note that When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism.
When the vertices of a hypergraph are explicitly labeled, one has the notions of equivalence, and also of equality.
Note that, with this definition of equality, graphs are self-dual: A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices.
If all edges have the same cardinality k, the hypergraph is said to be uniform or k-uniform, or is called a k-hypergraph.
H is k-regular if every vertex has degree k. The dual of a uniform hypergraph is regular and vice versa.
A partition theorem due to E. Dauber[37] states that, for an edge-transitive hypergraph
Conversely, every collection of trees can be understood as this generalized hypergraph.
Since trees are widely used throughout computer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well.
As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation.
