Hypergraph
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 directed hypergraph is a pair, where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of. Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain.
The order of a hypergraph is the number of vertices in. The size of the hypergraph is the number of edges in. The order of an edge in a directed hypergraph is : that is, the number of vertices in its tail followed by the number of vertices in its head.
The definition above generalizes from a directed graph to a directed hypergraph by defining the head or tail of each edge as a set of vertices rather than as a single vertex. A graph is then the special case where each of these sets contains only one element. Hence any standard graph theoretic concept that is independent of the edge orders will generalize to hypergraph theory.
An undirected hypergraph is an undirected graph whose edges connect not just two vertices, but an arbitrary number. An undirected hypergraph is also called a set system or a family of sets drawn from the set of elements.
Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, every bipartite graph can be regarded as the incidence graph of a hypergraph when it is 2-colored and it is indicated which color class corresponds to hypergraph vertices and which to hypergraph edges.
Hypergraphs have many other names. In computational geometry, an undirected hypergraph may sometimes be called a range space and then the hyperedges are called ranges.
In cooperative game theory, hypergraphs are called simple 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.
Applications
Undirected hypergraphs are useful in modelling such things as satisfiability problems, databases, machine learning, and Steiner tree problems. They have been extensively used in machine learning tasks as the data model and classifier regularization. The applications include recommender system, image retrieval, and bioinformatics. Representative hypergraph learning techniques include hypergraph spectral clustering that extends the spectral graph theory with hypergraph Laplacian, and hypergraph semi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results. For large scale hypergraphs, a distributed framework built using Apache Spark is also available. It can be 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.Directed hypergraphs can be used to model things including telephony applications, detecting money laundering, operations research, and transportation planning. They can also be used to model Horn-satisfiability.
Generalizations of concepts from graphs
Many theorems and concepts involving graphs also hold for hypergraphs, in particular:- Matching in hypergraphs;
- Vertex cover in hypergraphs ;
- Line graph of a hypergraph;
- Hypergraph grammar - created by augmenting a class of hypergraphs with a set of replacement rules;
- Ramsey's theorem;
- Erdős–Ko–Rado theorem;
- Kruskal–Katona theorem on uniform hypergraphs;
- Hall-type theorems for 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. 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.
In another style of hypergraph visualization, the subdivision model of hypergraph drawing, 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 order-n Venn diagram, for instance, may be viewed as a subdivision drawing of a hypergraph with n hyperedges and 2n − 1 vertices. In contrast with the polynomial-time recognition of planar graphs, it is NP-complete to determine whether a hypergraph has a planar subdivision drawing, 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.
An alternative representation of the hypergraph called PAOH is shown in the figure on top of this article. Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges. It has been designed for dynamic hypergraphs but can be used for simple hypergraphs as well.
Hypergraph coloring
Classic hypergraph coloring is assigning one of the colors from set to every vertex of a hypergraph in such a way that each hyperedge contains at least two vertices of distinct colors. In other words, there must be no monochromatic hyperedge with cardinality at least 2. In this sense it is a direct generalization of graph coloring. The minimum number of used distinct colors over all colorings is called the chromatic number of a hypergraph.Hypergraphs for which there exists a coloring using up to k colors are referred to as k-colorable. The 2-colorable hypergraphs are exactly the bipartite ones.
There are many generalizations of classic hypergraph coloring. One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed. Some mixed hypergraphs are uncolorable for any number of colors. A general criterion for uncolorability is unknown. When a mixed hypergraph is colorable, then the minimum and maximum number of used colors are called the lower and upper chromatic numbers respectively.
Properties of hypergraphs
A hypergraph can have various properties, such as:- Empty - has no edges.
- Non-simple - has loops or repeated edges, which means there can be two or more edges containing the same set of vertices.
- Simple - has no loops and no repeated edges.
- -regular - every vertex has degree, i.e., contained in exactly hyperedges.
- 2-colorable - its vertices can be partitioned into two classes U and V in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. An alternative term is Property B.
- * Two stronger properties are bipartite and balanced.
- -uniform - each hyperedge contains precisely vertices.
- -partite - the vertices are partitioned into parts, and each hyperedge contains precisely one vertex of each type.
- * Every -partite hypergraph is both -uniform and bipartite.
- Reduced: no hyperedge is a strict subset of another hyperedge; equivalently, every hyperedge is maximal for inclusion. The reduction of a hypergraph is the reduced hypergraph obtained by removing every hyperedge which is included in another hyperedge.
- Downward-closed - every subset of an undirected hypergraph's edges is a hyperedge too. A downward-closed hypergraph is usually called an abstract simplicial complex. It is generally not reduced, unless all hyperedges have cardinality 1.
- * An abstract simplicial complex with the augmentation property is called a matroid.
- Laminar: for any two hyperedges, either they are disjoint, or one is included in the other. In other words, the set of hyperedges forms a laminar set family.
Related hypergraphs
Let be the hypergraph consisting of vertices
and having edge set
where and are the index sets of the vertices and edges respectively.
A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph induced by is defined as
An alternative term is the restriction of H to A.
An extension of a subhypergraph is a hypergraph where each hyperedge of which is partially contained in the subhypergraph is fully contained in the extension. Formally
The partial hypergraph is a hypergraph with some edges removed. Given a subset of the edge index set, the partial hypergraph generated by is the hypergraph
Given a subset, the section hypergraph is the partial hypergraph
The dual of is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by and whose edges are given by 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
The 2-section 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.