Hypergraph

From Wikipedia, the free encyclopedia

Sample of hypergraph:

V = {v 1, v 2, v 3, v 4, v 5, v 6, v 7}

E = {e 1 = {v 1, v 2, v 3}, e 2 = {v 2, v 3}, e 3 = {v 3, v 5, v 6}, e 4 = {v 4}}

In mathematics, a hypergraph is a generalization of a graph, where edges can connect any number of vertices. Formally, a hypergraph is a pair $(X, E)$ where $X$ is a set of elements, called nodes or vertices, and $E$ is a set of non-empty subsets of $X$ called hyperedges. Therefore, $E$ is a subset of $S(X) \backslash \emptyset$ , where $S (X)$ 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.

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.

Unlike graphs, hypergraphs are difficult to draw on paper, so they tend to be studied using the nomenclature of set theory rather than the more pictorial descriptions (like 'trees','forests' and 'cycles') of graph theory.

[edit] Theorems

Many theorems involving graphs also hold for hypergraphs. Ramsey's theorem is a typical example. Some methods for studying symmetries of graphs extend to hypergraphs. For instance, a hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge. An hypergraph isomorphism is a homomorphism that is invertible. 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). The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.

A transversal or hitting set of a hypergraph H = (X, E) is a set T ⊂ X that has nonempty intersection with every edge. The transversal hypergraph of H is the hypergraph (X, F) whose edge set F consists of all transversals of H. Computing the transversal hypergraph has applications in machine learning and other fields of computer science.

A hypergraph H is called k-uniform or a k-hypergraph if every edge has cardinality k. A graph is just a 2-uniform hypergraph. The degree d(v) of a vertex v is the number of edges that contain it. H is k-regular if every vertex has degree k.

Let $V = \{v_1, v_2, ~\ldots, ~ v_n\}$ and $E = \{e_1, e_2, ~ \ldots ~ e_m\}$ . Every hypergraph has an $n \times m$ incidence matrix $A = (a i j)$ where

$a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise} \end{matrix} \right.$

The transpose $A t$ of the incidence matrix defines a hypergraph $H * = (V *, E *)$ called the dual of $H$ , where $V *$ is an m-element set and $E *$ is an n-element set of subsets of $V *$ . For $v^*_j \in V^*$ and $e^*_i \in E^*, ~ v^*_j \in e^*_i$ if and only if $a i j = 1$ . The dual of a uniform hypergraph is regular and vice-versa. Considering duals often leads to discoveries.

[edit] Hypergraph colouring

Hypergraph colouring is defined as follows. Be $H = (V, E)$ a hypergraph such that $\Vert V(H)\Vert = n$ . We claim that $C=\{c_1, c_2, \ldots, c_n\}$ is a proper colouring of $H$ if and only if, for all $e \in E, \vert e\vert > 1$ , there exists $v_i, v_j \in e$ such that $c_i \neq c_j$ .