Hypergraph 232535 225203593 2008-07-12T13:06:41Z Gubbubu 53423 /* See also */ [[Image:Hypergraph.gif|right|frame| Sample of hypergraph: <math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math>, <math>E= \{e_1,e_2,e_3,e_4\}</math> <math>=\{\{v_1, v_2, v_3\}, \{v_2,v_3\},</math> <math>\{v_3,v_5,v_6\},\{v_4\}\}</math>. ]] In [[mathematics]], a '''hypergraph''' is a generalization of a [[graph (mathematics)|graph]], where [[graph theory|edges]] can connect any number of [[vertex (graph theory)|vertices]]. Formally, a hypergraph <math>H</math> is a pair <math>H = (X,E)</math> where <math>X</math> is a set of elements, called ''nodes'' or ''vertices'', and <math>E</math> is a set of non-empty subsets of <math>X</math> called ''hyperedges'' or ''links''. Therefore, <math>E</math> is a subset of <math>\mathcal{P}(X) \backslash \{\varnothing\}</math>, where <math>\mathcal{P}(X)</math> is the [[power set]] of <math>X</math>. 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 structure]]s and vice versa. In particular, there is a [[Levi graph]] corresponding to every hypergraph, 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]]. Special cases include the [[clutter (mathematics)|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 theory|category]] with hypergraph homomorphisms as [[morphism]]s. == 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 <math>H=(X,E)</math> be the hypergraph consisting of vertices :<math>X = \lbrace x_n | n \in N \rbrace</math> that is, the vertices are indexed by an index <math>n\in N</math>, and the edge set is :<math>E = \lbrace e_i | i\in I, e_i \subseteq X \rbrace</math> with the edges <math>e_i</math> indexed by an index <math>i\in I</math>. A '''subhypergraph''' is a hypergraph with some vertices removed. Formally, the subhypergraph <math>H_A</math> induced by a subset <math>A</math> of <math>X</math> is defined as :<math>H_A=\left(A, \lbrace e_i \cap A | e_i \cap A \neq \varnothing \rbrace \right)</math> The '''partial hypergraph''' is a hypergraph with some edges removed. Given a subset <math>J \subset I</math> of the index set <math>I</math>, the partial hypergraph generated by <math>J</math> is the hypergraph :<math>\left(X, \lbrace e_i | i\in J \rbrace \right)</math> Given a subset <math>A\subseteq X</math>, the '''section hypergraph''' is the partial hypergraph :<math>H \times A = \left(A, \lbrace e_i | i\in I, e_i \subseteq A \subseteq X \rbrace \right)</math> The '''dual''' <math>H^*</math> of <math>H</math> is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by <math>\lbrace e_i \rbrace</math> and whose edges are given by <math>\lbrace X_n \rbrace</math> where :<math>X_n = \lbrace e_i | x_n \in e_i \rbrace </math> When a notion of equality is properly defined, as done below, hypergraphs can be seen to be self-dual: :<math>\left(H^*\right)^* = H</math> == 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 <math>H=(X,E)</math> is '''isomorphic''' to a hypergraph <math>G=(Y,F)</math>, written as <math>H \simeq G</math> if there exists a [[bijection]] :<math>\phi:X \to Y</math> and a [[permutation]] <math>\pi</math> of <math>I</math> such that :<math>\phi(e_i) = f_{\pi(i)}</math> The bijection <math>\phi</math> is then called the [[isomorphism]] of the graphs. Note that :<math>H \simeq G</math> if and only if <math>H^* \simeq G^*</math>. When the edges of a hypergraph are explicitly labeled, one has the additional notion of ''strong isomorphism''. One says that <math>H</math> is '''strongly isomorphic''' to <math>G</math> if the permutation is the identity. One then writes <math>H \cong G</math>. Note that all strongly isomorphic graphs are isomorphic, but not vice-versa. When the vertices of a hypergraph are explicitly labeled, one has the notions of ''equivalence'', and also of ''equality''. One says that <math>H</math> is '''equivalent''' to <math>G</math>, and writes <math>H\equiv G</math> if the isomorphism <math>\phi</math> has :<math>\phi(x_n) = y_n</math> and :<math>\phi(e_i) = f_{\pi(i)}</math> Note that :<math>H\equiv G</math> if and only if <math>H^* \cong G^*</math> If, in addition, the permutation <math>\pi</math> is the identity, one says that <math>H</math> equals <math>G</math>, and writes <math>H=G</math>. Note that, with this definition of equality, graphs are self-dual: :<math>\left(H^*\right) ^* = H</math> 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'',&nbsp;''E'')) is a [[group (mathematics)|group]] under composition, called the [[automorphism group]] of the hypergraph and written Aut(''H''). ===Examples=== Consider the hypergraph <math>H</math> with edges :<math>H = \lbrace e_1 = \lbrace a,b \rbrace, e_2 = \lbrace b,c \rbrace, e_3 = \lbrace c,d \rbrace, e_4 = \lbrace d,a \rbrace, e_5 = \lbrace b,d \rbrace, e_6 = \lbrace a,c \rbrace \rbrace</math> and :<math>G = \lbrace f_1 = \lbrace \alpha,\beta \rbrace, f_2 = \lbrace \beta,\gamma \rbrace, f_3 = \lbrace \gamma,\delta \rbrace, f_4 = \lbrace \delta,\alpha \rbrace, f_5 = \lbrace \alpha,\gamma \rbrace, f_6 = \lbrace \beta,\delta \rbrace \rbrace</math> Then clearly <math>H</math> and <math>G</math> are isomorphic (with <math>\phi(a)=\alpha</math>, ''etc.''), but they are not strongly isomorphic. So, for example, in <math>H</math>, vertex <math>a</math> meets edges 1, 4 and 6, so that, :<math>e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace</math> In graph <math>G</math>, there does not exist any vertex that meets edges 1, 4 and 6: :<math>f_1 \cap f_4 \cap f_6 = \varnothing</math> In this example, <math>H</math> and <math>G</math> are equivalent, <math>H\equiv G</math>, and the duals are strongly isomorphic: <math>H^*\cong G^*</math>. ==Symmetric hypergraphs== The '''rank''' <math>r(H)</math> of a hypergraph <math>H</math> 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 '''''k''-uniform''', or is called a '''''k''-hypergraph'''. 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''. The dual of a uniform hypergraph is regular and vice-versa. Two vertices ''x'' and ''y'' of ''H'' are called '''symmetric''' if there exists an automorphism such that <math>\phi(x)=y</math>. Two edges <math>e_i</math> and <math>e_j</math> are said to be '''symmetric''' if there exists an automorphism such that <math>\phi(e_i)=e_j</math>. A hypergraph is said to be '''vertex-transitive''' (or '''vertex-symmetric''') if all of its vertices are symmetric. Similarly, a hypergraph is '''edge-transitive''' if all edges are symmetric. If a hypergraph is both edge- and vertex-symmetric, then the hypergraph is simply '''transitive'''. Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity. ==Transversals== A '''transversal''' or '''hitting set''' of a hypergraph ''H'' = (''X'', ''E'') is a set <math>T\subseteq X</math> that has nonempty [[intersection (set theory)|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]], [[Index (database)|indexing of database]], [[Boolean satisfiability problem|SAT problem]] and [[Optimization (computer science)|optimization]]. ==Incidence matrix== Let <math>V = \{v_1, v_2, ~\ldots, ~ v_n\}</math> and <math>E = \{e_1, e_2, ~ \ldots ~ e_m\}</math>. Every hypergraph has an <math>n \times m</math> [[incidence matrix]] <math>A = (a_{ij})</math> where :<math>a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise} \end{matrix} \right.</math> The [[transpose]] <math>A^t</math> of the [[incidence (geometry)|incidence]] matrix defines a hypergraph <math>H^* = (V^*,\ E^*)</math> called the '''dual''' of <math>H</math>, where <math>V^*</math> is an ''m''-element set and <math>E^*</math> is an ''n''-element set of subsets of <math>V^*</math>. For <math>v^*_j \in V^*</math> and <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> [[if and only if]] <math>a_{ij} = 1</math>. == Hypergraph colouring == Hypergraph colouring is defined as follows. Let <math>H=(V, E)</math> be a hypergraph such that <math>\Vert V\Vert = n</math>. Then <math>C=\{c_1, c_2, \ldots, c_n\}</math> is a proper colouring of <math>H</math> if and only if, for all <math>e \in E, \vert e\vert > 1,</math> there exists <math>v_i, v_j \in e</math> such that <math>c_i \neq c_j</math>. ==Partitions== A partition theorem due to E. Dauber<ref>E. Dauber, in ''Graph theory'', ed. F. Harary, Addison Wesley, (1969) p. 172.</ref> states that, for an edge-transitive hypergraph <math>H=(X,E)</math>, there exists a [[partition of a set|partition]] :<math>(X_1, X_2,\cdots,X_K)</math> of the vertex set <math>X</math> such that the subhypergraph <math>H_{X_k}</math> generated by <math>X_k</math> is transitive for each <math>1\le k \le K</math>, and such that :<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math> where <math>r(H)</math> is the rank of ''H''. As a corollary, an edge-transitive hypergraph that is not vertex-transitive is bicolorable. == Theorems == Many [[theorem]]s involving graphs also hold for hypergraphs. [[Ramsey's theorem]] is a typical example. Some methods for studying symmetries of graphs extend to hypergraphs. Two prominent theorems are the [[Erd&#337;s&ndash;Ko&ndash;Rado theorem]] and the [[Kruskal&ndash;Katona theorem]] on uniform hypergraphs. ==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 <math>V= \{a,b\}</math> and whose edges are <math>e_1=\{a,b\}</math> and <math>e_2=\{a,e_1\}</math>. Then, although <math>b\in e_1</math> and <math>e_1\in e_2</math>, it is not true that <math>b\in e_2</math>. 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 edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges <math>e_1</math> and <math>e_2</math>, and zero vertices, so that <math>e_1 = \{e_2\}</math> and <math>e_2 = \{e_1\}</math>. 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 :<math>\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right]</math> ==See also== * [[Incidence structure|Incidence structure]] * [[P system]] ==References== <references/> * Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", ''Lecture Notes in Mathematics'' '''411''' Springer-Verlag * {{planetmath|id=3508|title=hypergraph}} [[Category:Set families]] [[Category:Graph families]] [[Category:combinatorics]] [[de:Glossar Graphentheorie#Hypergraph]] [[es:Hipergrafo]] [[eo:Hipergrafeo]] [[fr:Hypergraphe]] [[hu:Hipergráf]] [[ja:ハイパーグラフ]] [[pl:Hipergraf]] [[pt:Hipergrafo]] [[ru:Гиперграф]] [[sr:Хиперграф]] [[sv:Hypergraf]]