我们在组织翻译超图这个词条，这个词条是之前Wolfram发的那篇长文中一个非常重要的概念，我们希望可以整理好这个词条，帮助大家更好的理解那篇文章。

现在招募6个小伙伴一起翻译超图这个词条 https://wiki.swarma.org/index.php?title=超图_Hypergraph

*开头正文部分+术语定义（Terminology)——十三维
*二分图模型+不对称性+同构与平等——淑慧
*对称超图+横截面——瑾晗
*关联矩阵+超图着色+分区---厚朴
*定理+超图绘制+超图语法——十三维
*概括+超图学习——世康

截止时间：北京时间18：00之前。

In [[mathematics]], a '''hypergraph''' is a generalization of a [[Graph (discrete mathematics)|graph]] in which an [[graph theory|edge]] can join any number of [[vertex (graph theory)|vertices]]. In contrast, in an ordinary graph, an edge connects exactly two 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 ''edges''. Therefore, <math>E</math> is a subset of <math>\mathcal{P}(X) \setminus\{\emptyset\}</math>, where <math>\mathcal{P}(X)</math> is the [[power set]] of <math>X</math>. The size of the vertex set is called the ''order of the hypergraph'', and the size of edges set is the ''size of the hypergraph''.

在[[数学中]], '''超图'''是一种广义上的[[graph(discrete mathematics)|图]] ，它的一条[[graph theory|边]]可以连接任意数量的[[vertex (graph theory)|顶点]]. 相对而言，在普通图中，一条边只能连接两个顶点.形式上, 超图 <math>H</math> 是一个集合组 <math>H = (X,E)</math> 其中<math>X</math> 是一个以节点或顶点为元素的集合，即顶点集, 而 <math>E</math> 是一组非空子，被称为边或超边.
因此，若<math>\mathcal{P}(X)</math>是 <math>E</math>的幂集，则<math>E</math>是 <math>\mathcal{P}(X) \setminus\{\emptyset\}</math> 的一个子集。在<math>H</math>中，顶点集的大小被称为超图的阶数，边集的大小被称为超图的大小。

While graph edges are 2-element subsets of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often 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''. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting ''k'' nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. A hypergraph is also called a ''set system'' or a ''[[family of sets]]'' drawn from the [[universal set]].

普通图的边是节点的二元子集，超边则是节点的任意集合，所以可以包含任意数量的节点。但我们总先需要研究具有相同基数超边的超图，即一个 k-均匀超图，所有超边的大小都为 k。因此一个 2-均匀超图就是图，一个 3-均匀超图就是三元组的集合，依此类推。超图也被称为从[[泛集]]（universal set）中抽取的一个集系统或[[集族]]。

Hypergraphs can be viewed as [[incidence structure]]s. In particular, there is a bipartite "incidence graph" or "[[Levi graph]]" corresponding to every hypergraph, and conversely, most, but not all, [[bipartite graph]]s can be regarded as incidence graphs of hypergraphs.

超图可以看做是[[关联结构]]（incidence structure）。特别的，每个超图都有一个与超图相对应的二分 "关联图 "或 "[[列维图]]"（Levi graph），反之，大多数（但不是全部）[[二分图]]都可以看作是超图的关联图。

Hypergraphs have many other names. In [[computational geometry]], a hypergraph may sometimes be called a '''range space''' and then the hyperedges are called ''ranges''.<ref>{{citation
| last1 = Haussler | first1 = David | author1-link = David Haussler
| last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
| doi = 10.1007/BF02187876
| issue = 2
| journal = [[Discrete and Computational Geometry]]
| mr = 884223
| pages = 127–151
| title = ε-nets and simplex range queries
| volume = 2
| year = 1987| doi-access = free
}}.</ref>
In [[cooperative game]] theory, hypergraphs are called '''simple games''' (voting games); this notion is applied to solve problems in [[social choice theory]]. In some literature edges are referred to as ''hyperlinks'' or ''connectors''.<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>

超图还有许多其它名称。在[[计算几何学]]中，超图有时可以被称为'''范围空间'''（range space），将超图的边称为''范围''.<ref>{{citation
| last1 = Haussler | first1 = David | author1-link = David Haussler
| last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
| doi = 10.1007/BF02187876
| issue = 2
| journal = [[Discrete and Computational Geometry]]
| mr = 884223
| pages = 127–151
| title = ε-nets and simplex range queries
| volume = 2
| year = 1987| doi-access = free
}}.</ref>
在[[合作博弈论]]中，超图被称为'''简单博弈'''（投票博弈）；这个概念被应用于解决[[社会选择理论]]（social choice theory）中的问题。在一些文献中，超边被称为''超连接''或''连接器''.<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>

Special kinds of hypergraphs include: [[#Symmetric hypergraphs|''k''-uniform ones]], as discussed briefly above; [[clutter (mathematics)|clutter]]s, where no edge appears as a subset of another edge; and [[abstract simplicial complex]]es, which contain all subsets of every edge.
The collection of hypergraphs is a [[Category (mathematics)|category]] with hypergraph [[homomorphism]]s as [[morphism]]s.

特殊类型的超图包括：上文简单讨论过的 k-均匀超图；散簇，没有一条边作是另一条边的子集；以及[[抽象单纯复形]]（abstract simplicial complexes），包含每条边的所有子集。
超图是一个以超图同态为[[态射]]（morphism）的范畴。

==Terminology==

==== Definitions ====
There are different types of hypergraphs such as:
* ''Empty hypergraph'': a hypergraph with no edges.
* ''Non-simple (or multiple) hypergraph'': a hypergraph allowing loops (hyperedges with a single vertex) or repeated edges, which means there can be two or more edges containing the same set of vertices.
* ''Simple hypergraph'': a hypergraph that contains no loops and no repeated edges.
* ''<math>k </math>-uniform hypergraph'': a hypergraph where each edge contains precisely <math>k</math> vertices.
* ''<math>d </math>-regular hypergraph'': a hypergraph where every vertex has degree <math>d </math>.
* ''Acyclic hypergraph'': a hypergraph that does not contain any cycles.

超图有不同的类型，如：
* 空超图：没有边的超图
* 非简单（或多重）超图：允许有循环（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点。
* 简单超图：不包含循环和重复边的超图。
* 𝑘-均匀超图：每条超边都正好包含 k 个顶点的超图。
* 𝑑-正则超图：每个顶点的度数都是 𝑑 的超图
* 非循环超图：不包含任何循环的超图。

Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''.

因为超图的链接可以有任意基数，所以有几种子图的概念，分别是''子超图''（subhypergraphs）、''部分超图''（partial hypergraphs）和''分段超图''（section hypergraphs）。

Let <math>H=(X,E)</math> be the hypergraph consisting of vertices

:<math>X = \lbrace x_i | i \in I_v \rbrace,</math>

and having ''edge set''

:<math>E = \lbrace e_i | i\in I_e \land e_i \subseteq X \land e_i \neq \emptyset \rbrace,</math>

where <math>I_v</math> and <math>I_e</math> are the [[index set]]s of the vertices and edges respectively.

A ''subhypergraph'' is a hypergraph with some vertices removed. Formally, the subhypergraph <math>H_A</math> induced by <math>A \subseteq X </math> is defined as

:<math>H_A=\left(A, \lbrace e \cap A | e \in E \land
e \cap A \neq \emptyset \rbrace \right).</math>

An ''extension'' of a ''subhypergraph'' is a hypergraph where each
hyperedge of <math>H</math> which is partially contained in the subhypergraph <math>H_A</math> and is fully contained in the extension <math>Ex(H_A)</math>.
Formally
:<math>Ex(H_A) = (A \cup A', E' )</math> with <math>A' = \bigcup_{e \in E} e \setminus A</math> and <math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>.

The ''partial hypergraph'' is a hypergraph with some edges removed. Given a subset <math>J \subset I_e</math> of the edge index set, 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 \land e_i \subseteq A \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_m \rbrace</math> where

:<math>X_m = \lbrace e_i | x_m \in e_i \rbrace. </math>

When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an [[involution (mathematics)|involution]], i.e.,

:<math>\left(H^*\right)^* = H.</math>

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'' [[induced subgraph|induces]] a connected subgraph in ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the [[connected component (graph theory)|connected components]] of ''G'' and of ''H'', such that each connected component ''G<nowiki>'</nowiki>'' of ''G'' is a host of the corresponding ''H<nowiki>'</nowiki>''.

对于不连通的超图 G 和具有相同顶点连通的超图 H，如果 H 的每个超边都有 G 中一个子图连接，则 G 是一个主图（host graph）；
对于不连通的超图 H，如果 G 和 H 的连通部分之间存在一个双射，使得 G 的每个连通部分 G' 都是对应的 H' 的主图，则 G 是一个主图。

A hypergraph is ''bipartite'' if and only if 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. Alternatively, such a hypergraph is said to have [[Property B]].

一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类 U 和 V ：每个基数至少为 2 超边包含两类中的至少一个顶点。相反的，超图则被称为具有属性 B。

The '''2-section''' (or '''clique graph''', '''representing graph''', '''primal graph''', '''Gaifman 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.

2-段超图（或团图，代表图、原始图、盖夫曼图）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。

==二部图模型 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 (''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. This bipartite graph is also called [[incidence graph]].

[[File:bipartie graph.jpeg|200px|缩略图|右| 设<math>G=(V,E)</math>是一个无向图，如果顶点V可分割为两个互不相交的子集<math> {(group1, group2)}</math>，并且图中的每条边<math>{（i，j）}</math>所关联的两个顶点<math>{i}</math>和<math>{j}</math>分别属于这两个不同的部分<math>{(i \in group1,j \in group2)}</math>，则称图<math>{G}</math>为一个二部图。]]

一个'''超图“ <math>{H} </math>”'''可以用二部图“<math>{BG} </math>”表示，其构成如下: 集合"X"和" E"是"BG"的分割，而且 ("x1", "e1") 与边连通当且仅当顶点"x1"包含在" <math>H </math>"的边" e1"中。反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二部图也代表具有上述性质的部分超图。这个二部图也称为'''关联图'''。

==无环性 Acyclicity==
In contrast with ordinary undirected graphs for which there is a single natural notion of [[cycle (graph theory)|cycles]] and [[Forest (graph theory)|acyclic graphs]], there are multiple natural non-equivalent definitions of acyclicity for hypergraphs which collapse to ordinary graph acyclicity for the special case of ordinary graphs.

与只有'''圈 cycle'''和'''森林 forest'''的普通无向图相比，对于超图的特殊情形，那些坍缩为平凡图的无环性超图有多种自然不等价的'''无环性 acyclicity''' 定义。

A first definition of acyclicity for hypergraphs was given by [[Claude Berge]]:<ref>[[Claude Berge]], ''Graphs and Hypergraphs''</ref> a hypergraph is Berge-acyclic if its [[incidence graph]] (the [[bipartite graph]] defined above) is acyclic. This definition is very restrictive: for instance, if a hypergraph has some pair <math>v \neq v'</math> of vertices and some pair <math>f \neq f'</math> of hyperedges such that <math>v, v' \in f</math> and <math>v, v' \in f'</math>, then it is Berge-cyclic. Berge-cyclicity can obviously be tested in [[linear time]] by an exploration of the incidence graph.

由Claude Berge 给出了超图无环性的首个定义: <ref>Claude Berge,[https://www.amazon.com/Graphs-hypergraphs-North-Holland-mathematical-library/dp/0444103996 ''Graphs and Hypergraphs'']</ref> 如果它的'''关联图'''(上面定义的二部图)是无环的，则称这个超图是 Berge 无环的 Berge-acyclic。这个定义是非常严格的：例如，假设一个超图有一些顶点<math>v \neq v'</math>和一些超边<math>f \neq f'</math> ，例如 <math>v, v' \in f</math> 和<math>v, v' \in f'</math>，那么它就是 Berge成环的 Berge-cyclic。通过对关联图的探讨，Berge成环性 berge-cyclity可以在线性时间 linear time内得到有效验证。

We can define a weaker notion of hypergraph acyclicity,<ref>C. Beeri, [[Ronald Fagin|R. Fagin]], D. Maier, [[Mihalis Yannakakis|M. Yannakakis]], ''On the Desirability of Acyclic Database Schemes''</ref> 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 graph|chordal]]; it is also equivalent to reducibility to the empty graph through the GYO algorithm<ref>C. T. Yu and M. Z. Özsoyoğlu. ''[https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf An algorithm for tree-query membership of a distributed query]''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979</ref> (also known as Graham's algorithm), a [[confluence (abstract rewriting)|confluent]] iterative process which removes hyperedges using a generalized definition of [[ear (graph theory)|ears]]. In the domain of [[database theory]], it is known that a [[database schema]] enjoys certain desirable properties if its underlying hypergraph is α-acyclic.<ref>[[Serge Abiteboul|S. Abiteboul]], [[Richard B. Hull|R. B. Hull]], [[Victor Vianu|V. Vianu]], ''Foundations of Databases''</ref> Besides, α-acyclicity is also related to the expressiveness of the [[guarded fragment]] of [[first-order logic]].

此处，我们可以定义一个减弱的超图无环性的概念<ref>C. Beeri, [[Ronald Fagin|R. Fagin]], D. Maier, [[Mihalis Yannakakis|M. Yannakakis]], ''On the Desirability of Acyclic Database Schemes''</ref>，后来被称为 <math> {\alpha}</math>-无环性 <math> {\alpha}</math> acyclicity。这个无环性的概念等价于超图是同构的(原图的每个团都被某个超边所覆盖) ，它的原图称为弦图 chordal graph ; 它也等价于通过 GYO 算法 Graham-Yu-Ozsoyoglu Algorithm （也称为格雷厄姆算法 Graham's algorithm) 得到具有可约性的空图<ref>C. T. Yu and M. Z. Özsoyoğlu. ''[https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf An algorithm for tree-query membership of a distributed query]''. In Proc. IEEE COMPSAC, pages 306-312, 1979</ref><ref name="graham1979universal">M. H. Graham. ''On the universal relation''. Technical Report, University of Toronto, Toronto, Ontario, Canada, 1979</ref>。GYO 算法是一个合流 confluence（抽象重写 abstract rewriting）迭代过程，该算法中使用耳朵 ear的广义定义去除超边 (图论中的耳朵就定义为一条路径，其中除了端点外的点的度数均为 2（端点可以重合），而且删去后不破坏图的连通性)。总所周知，在数据库理论 database theory 的领域中，如果一个数据库模式 database schema的底层超图是<math> {\alpha}</math>无环的，那么它就具有某些理想的性质。 <ref>Serge Abiteboul, Richard B. Hull, Victor Vianu|V. Vianu, ''Foundations of Databases''</ref> 除此之外,<math> {\alpha}</math>无环性也与一阶逻辑 first-order logic 保护的片段 guarded fragment 的表达能力有关。

We can test in [[linear time]] if a hypergraph is α-acyclic.<ref>[[Robert Tarjan|R. E. Tarjan]], [[Mihalis Yannakakis|M. Yannakakis]]. ''Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs''. SIAM J. on Computing, 13(3):566-579, 1984.</ref>

我们可以在线性时间 linear time内检验超图是否是-无环的。 <ref>Robert Tarjan|R. E. Tarjan, Mihalis Yannakakis|M. Yannakakis. ''Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs''. SIAM J. on Computing, 13(3):566-579, 1984.</ref>

Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming, [[Ronald Fagin]]<ref name="fagin1983degrees">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</ref> 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<ref name="fagin1983degrees"/> to an earlier definition by Graham.<ref name="graham1979universal"/> The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to [[Bachman diagram]]s. Both β-acyclicity and γ-acyclicity can be tested in [[PTIME|polynomial time]].

注意到<math> {\alpha}</math>-无环性似乎直觉不相符，即<math> {\alpha}</math>-成环超图添加超边可能使其成为<math> {\alpha}</math>-无环的（例如，添加一条包含超图所有顶点的超边总能其成为<math> {\alpha}</math>-无环的）。为了克服这个缺点，Ronald Fagin<ref name="fagin1983degrees">[[Ronald Fagin]], ''Degrees of Acyclicity for Hypergraphs and Relational Database Schemes''</ref> 定义了更强的 <math> {\beta}</math>-无环性 <math> {\beta}</math>-acylicity 和 <math> {\gamma}</math>无环性 <math> {\gamma}</math>-acylicity 概念。应当指出：<math> {\gamma}</math>无环超图是推出其所有子超图都是<math> {\alpha}</math>无环的必要条件，这与 Graham 的早期定义<ref name="graham1979universal"/> 等价。 <math> {\gamma}</math>无环性的概念是一个更加严苛的条件，它等价于数据库模式的几个理想性质，并且与Bachman 图 Bachman diagrams有关. <math> {\beta}</math>-无环性和 <math> {\gamma}</math>无环性都可以在多项式时间 polynomial time(PTIME)内完成检测。

Those four notions of acyclicity are comparable: Berge-acyclicity implies γ-acyclicity which implies β-acyclicity which implies α-acyclicity. However, none of the reverse implications hold, so those four notions are different.<ref name="fagin1983degrees" />

无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。然而，反之均不成立。<ref name="fagin1983degrees" />

==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'', ''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<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 (combinatorics)|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 [[combinatorial optimization]], in [[game theory]], and in several fields of [[computer science]] such as [[machine learning]], [[Index (database)|indexing of database]]s, the [[Boolean satisfiability problem|satisfiability problem]], [[data mining]], and computer [[program 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>.

分别设 <math>V = \{v_1, v_2, ~\ldots, ~ v_n\}</math>， <math>E = \{e_1, e_2, ~ \ldots ~ e_m\}</math>。
每一个超图都有一个 <math>n \times m</math>[[关联矩阵]]<math>A = (a_{ij})</math>其为：<math>a_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right.</math>

其关联矩阵的[[转设]] <math>A^t</math>定义了 <math>H^* = (V^*,\ E^*)</math>称为<math>H</math>的'''对偶'''，其中<math>V^*</math>是一个''m''元集合 <math>E^*</math>是一个<math>V^*</math>子集的''n''元集合。

对于<math>v^*_j \in V^*</math> 和 <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> [[当且仅当]] <math>a_{ij} = 1</math>。

==Hypergraph coloring==
Classic hypergraph coloring is assigning one of the colors from set <math>\{1,2,3,...\lambda\}</math> 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. Minimum number of used distinct colors over all colorings is called the chromatic number of a hypergraph.

经典超图着色是将集合<math>\{1,2,3,...\lambda\}</math>中的其中一种颜色赋予给超图的每个顶点，使每个超边至少包含两个不同颜色的顶点。换句话说，不能存在基数至少为2的单色深边。从此意义上出发，它是通常图着色的直接推广。在所有着色行为中使用到最小的不同颜色数称为超图的色数。

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.
存在着使用多达''k'' 种颜色着色的超图称为''k- 可着色图''。'''2-可染超图就是二分图'''。

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. See http://spectrum.troy.edu/voloshin/mh.html for details.

经典超图着色有许多推广。在允许单色边情况下，混合超图着色是其中之一。一些混合超图对于任意数量的颜色都是不可着色的。同时不可着色性的内在标准是未知的。当一个混合超图是可着色时，其所使用的最小和最大颜色数分别称为下色数和上色数。详情请参阅 http://spectrum.troy.edu/voloshin/mh.html

==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.

由E. Dauber<ref>E. Dauber, in ''Graph theory'', ed. F. Harary, Addison Wesley, (1969) p. 172.</ref>所提出的一个分区定理表明，对于边传递超图 <math>H=(X,E)</math>存在一个[[分区]]:<math>(X_1, X_2,\cdots,X_K)</math>对于顶点集 <math>X</math>使得由<math>X_k</math>生成的子超图<math>H_{X_k}</math>在<math>1\le k \le K</math>时是可传递的，并且使得<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math>，其中<math>r(H)</math>是 ''H''的秩。

作为推论，不是点传递的边传递超图则是双色的。

[[Graph partitioning]] (and in particular, hypergraph partitioning) has many applications to IC design<ref>{{Citation |title=Multilevel hypergraph partitioning: applications in VLSI domain |author=Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |date=March 1999 |volume=7 |issue=1 |pages=69–79 |doi=10.1109/92.748202 |postscript=.|citeseerx=10.1.1.553.2367 }}</ref> and parallel computing.<ref>{{Citation |doi=10.1016/S0167-8191(00)00048-X |title=Graph partitioning models for parallel computing |author= Hendrickson, B., Kolda, T.G. |journal=Parallel Computing | year=2000 |volume=26 |issue=12 |pages=1519–1545 |postscript=.|url=https://digital.library.unt.edu/ark:/67531/metadc684945/ |type=Submitted manuscript }}</ref><ref>{{Cite conference |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=A Hypergraph Model for Mapping Repeated Sparse Matrix-Vector Product Computations onto Multicomputers |conference=Proc. International Conference on Hi Performance Computing (HiPC'95) |year=1995}}</ref><ref>{{Citation |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication |journal=IEEE Transactions on Parallel and Distributed Systems |volume=10 |issue=7 |pages=673–693 |year=1999|doi=10.1109/71.780863 |postscript=. |citeseerx=10.1.1.67.2498 }}</ref> Efficient and Scalable [[Graph partition|hypergraph partitioning algorithms]] are also important for processing large scale hypergraphs in machine learning tasks.<ref name=hyperx>{{citation|last1=Huang|first1=Jin|last2=Zhang|first2=Rui|last3=Yu|first3=Jeffrey Xu|journal=Proceedings of the IEEE International Conference on Data Mining|title=Scalable Hypergraph Learning and Processing|year=2015}}</ref>

[[图分区]](特别是超图分区)在集成电路设计<ref>{{Citation |title=Multilevel hypergraph partitioning: applications in VLSI domain |author=Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |date=March 1999 |volume=7 |issue=1 |pages=69–79 |doi=10.1109/92.748202 |postscript=.|citeseerx=10.1.1.553.2367 }}</ref> 和并行计算<ref>{{Citation |doi=10.1016/S0167-8191(00)00048-X |title=Graph partitioning models for parallel computing |author= Hendrickson, B., Kolda, T.G. |journal=Parallel Computing | year=2000 |volume=26 |issue=12 |pages=1519–1545 |postscript=.|url=https://digital.library.unt.edu/ark:/67531/metadc684945/ |type=Submitted manuscript }}</ref><ref>{{Cite conference |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=A Hypergraph Model for Mapping Repeated Sparse Matrix-Vector Product Computations onto Multicomputers |conference=Proc. International Conference on Hi Performance Computing (HiPC'95) |year=1995}}</ref><ref>{{Citation |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication |journal=IEEE Transactions on Parallel and Distributed Systems |volume=10 |issue=7 |pages=673–693 |year=1999|doi=10.1109/71.780863 |postscript=. |citeseerx=10.1.1.67.2498 }}</ref>中有很多应用。在机器学习任务中，高效、可扩展的[[超图分区算法]]对于处理大规模超图也很重要。<ref name=hyperx>{{citation|last1=Huang|first1=Jin|last2=Zhang|first2=Rui|last3=Yu|first3=Jeffrey Xu|journal=Proceedings of the IEEE International Conference on Data Mining|title=Scalable Hypergraph Learning and Processing|year=2015}}</ref>

==Theorems==
Many [[theorem]]s 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.

许多涉及图的定理和概念也适用于超图，典型的例子有[[拉姆西定理]]（Ramsey's theorem）和超图的线图。研究图的对称性的一些方法也被扩展到超图。
均匀超图上有[[Erdős-Ko-Rado theorem]]和[[Kruskal-Katona theorem]]两个著名定理。

==Hypergraph drawing==
[[File:CircuitoDosMallas.png|thumb|This [[circuit diagram]] can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.]]（这个线路图可以解释为一个超图，其中四个顶点（用白色的矩形和圆盘表示）由三个用树表示的超图连接）

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.<ref>{{citation
| last = Sander | first = G.
| contribution = Layout of directed hypergraphs with orthogonal hyperedges
| pages = 381–386
| publisher = Springer-Verlag
| series = [[Lecture Notes in Computer Science]]
| title = Proc. 11th International Symposium on Graph Drawing (GD 2003)
| contribution-url = http://gdea.informatik.uni-koeln.de/585/1/hypergraph.ps
| volume = 2912
| year = 2003| title-link = International Symposium on Graph Drawing
}}.</ref><ref>{{citation
| last1 = Eschbach | first1 = Thomas
| last2 = Günther | first2 = Wolfgang
| last3 = Becker | first3 = Bernd
| issue = 2
| journal = [[Journal of Graph Algorithms and Applications]]
| pages = 141–157
| title = Orthogonal hypergraph drawing for improved visibility
| url = http://jgaa.info/accepted/2006/EschbachGuentherBecker2006.10.2.pdf
| volume = 10
| year = 2006 | doi=10.7155/jgaa.00122}}.</ref> 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 curve]]s that enclose sets of points.<ref>{{citation
| last = Mäkinen | first = Erkki
| doi = 10.1080/00207169008803875
| issue = 3
| journal = International Journal of Computer Mathematics
| pages = 177–185
| title = How to draw a hypergraph
| volume = 34
| year = 1990}}.</ref><ref>{{citation
| last1 = Bertault | first1 = François
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| contribution = Drawing hypergraphs in the subset standard
| doi = 10.1007/3-540-44541-2_15
| pages = 45–76
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 8th International Symposium on Graph Drawing (GD 2000)
| volume = 1984
| year = 2001| title-link = International Symposium on Graph Drawing
| isbn =
| doi-access = free
}}.</ref><ref>{{citation
| last1 = Naheed Anjum | first1 = Arafat
| last2 = Bressan | first2 = Stéphane
| contribution = Hypergraph Drawing by Force-Directed Placement
| doi = 10.1007/_31
| pages = 387–394
| publisher = Springer International Publishing
| series = Lecture Notes in Computer Science
| title = 28th International Conference on Database and Expert Systems Applications (DEXA 2017)
| volume = 10439
| year = 2017| isbn =
}}.</ref>

其中一种超图的可视化表示法，类似于标准的图的画法：用平面内的曲线来描绘图边，将超图的顶点画成点状、圆盘或盒子，超边则被描绘成以顶点为叶子的树[16][17]。如果顶点表示为点，超边也可以被描绘成连接点集的平滑曲线，或显示为封闭点集的简单闭合曲线[18][19][20]。

[[File:Venn's four ellipse construction.svg|thumb|An order-4 Venn diagram, which can be interpreted as a subdivision drawing of a hypergraph with 15 vertices (the 15 colored regions) and 4 hyperedges (the 4 ellipses).]]（一个4阶维恩图，可以被解释为一个15个顶点（15个有色区域）和4个超边（4个椭圆）的超图的细分图）

In another style of hypergraph visualization, the subdivision model of hypergraph drawing,<ref>{{citation
| last1 = Kaufmann | first1 = Michael
| last2 = van Kreveld | first2 = Marc
| last3 = Speckmann | first3 = Bettina | author3-link = Bettina Speckmann
| contribution = Subdivision drawings of hypergraphs
| doi = 10.1007/_39
| pages = 396–407
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 16th International Symposium on Graph Drawing (GD 2008)
| volume = 5417
| year = 2009| title-link = International Symposium on Graph Drawing
| isbn =
| doi-access = free
}}.</ref> 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 (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 polynomial-time recognition of [[planar graph]]s, it is [[NP-complete]] to determine whether a hypergraph has a planar subdivision drawing,<ref>{{citation
| last1 = Johnson | first1 = David S. | author1-link = David S. Johnson
| last2 = Pollak | first2 = H. O.
| doi = 10.1002/jgt.3190110306
| issue = 3
| journal = Journal of Graph Theory
| pages = 309–325
| title = Hypergraph planarity and the complexity of drawing Venn diagrams
| volume = 11
| year = 2006}}.</ref> 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.<ref>{{citation
| last1 = Buchin | first1 = Kevin
| last2 = van Kreveld | first2 = Marc
| last3 = Meijer | first3 = Henk
| last4 = Speckmann | first4 = Bettina
| last5 = Verbeek | first5 = Kevin
| contribution = On planar supports for hypergraphs
| doi = 10.1007/978-3-642-11805-0_33
| pages = 345–356
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 17th International Symposium on Graph Drawing (GD 2009)
| volume = 5849
| year = 2010| title-link = International Symposium on Graph Drawing
| isbn = 978-3-642-11804-3
| doi-access = free
}}.</ref>

超图可视化的另一种样式，是绘制超图的细分模型[21]，平面被细分为区域，每个区域代表超图的一个顶点。超图的超边用这些区域的相邻子集来表示，这些子集可以通过着色、或在它们周围画轮廓来表示，或者兼而有之。

An alternative representation of the hypergraph called PAOH<ref name="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.

超图的另一种表示法被称做 PAOH[24]，如上图所示，边是连接顶点的垂线，顶点在左边是对齐的。右边的图例显示了边的名称。它是为动态超图设计的，但也可以用于简单的超图。

==Hypergraph grammars==
{{main|Hypergraph grammar}}
By augmenting a class of hypergraphs with replacement rules, [[graph grammar]]s can be generalised to allow hyperedges.

通过扩充一组替换规则于超图，[[图语法]]可以被推广超边上。

== 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, subsets of subsets of vertices and so on ''ad infinitum''. In essence, every edge is just an internal node of a tree or [[directed acyclic graph]], and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). 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. So, for example, this generalization arises naturally as a model of [[term algebra]]; edges correspond to [[term (logic)|terms]] and vertices correspond to constants or variables.

For such a hypergraph, 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 graph|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>

==超图概念的延伸==

超图的相关概念可以进行进一步的延伸，如超图中的一些边可以指向另一些边。这种延伸有两种变体。在第一种变体中，超图的边不仅包含一组节点，而且还可以包含这组节点的子集、子集的子集等等。本质上，超图的每条边只是树结构或有向无环图的一个内部节点，而节点就是叶子。从这个意义上来说，超图就是具有共享节点的树的集合(即内部节点或叶子可能出现在不同的树结构中)，反过来说，每个树的集合又可以理解为一个超图。因为树结构在计算机科学和许多数学分支中被广泛使用，所以超图的出现也是自然而然的。比如这种延伸是作为项代数的模型而自然产生的：边对应项，节点对应常量或变量。

对于上述的超图，节点集提供了一种排序。但是该排序既不是偏序也不是预序，因为它是不可传递的。与这一延伸方式的Levi图相对应的图是有向无环图。例如，一个超图的节点集为<math>V= \{a,b\}</math>，边为<math>e_1=\{a,b\}</math>和<math>e_2=\{a,e_1\}</math>。那么，虽然<math>b\in e_1</math>且<math>e_1\in e_2</math>，但<math>b\in e_2</math>却不是真的。然而，这类超图节点集的封闭传递确实诱导了偏序，并将超图“展平”为一个偏序集。

第二种变体中，超图中的边可以指向其他边，同时不用考虑必须形成有向非循环图的要求。这允许超图具有边的循环，而不需要有任何节点。例如，考虑由两条边e1和e2组成的，节点个数为零的广义超图，使得<math>e_1 = \{e_2\}</math>且<math>e_2 = \{e_1\}</math>。因为这个循环是无限递归的，所以边的集合违反了基础公理。具体来说，对于这样的超图，不存在节点集的封闭传递。虽然这样的结构乍看起来可能很奇怪，但只要注意到它的Levi图的等价延伸不再是二分图，而是一般的有向图，就可以很容易地去理解。

根据定义，这种超图的广义关联矩阵是一个方阵，其秩等于节点和边的总数。因此，对于上面的示例，关联矩阵为:
<math>\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right]</math>。

==Hypergraph learning==

Hypergraphs have been extensively used in [[machine learning]] tasks as the data model and classifier [[regularization (mathematics)]].<ref>{{citation| last1 = Zhou | first1 = Dengyong| last2 = Huang | first2 = Jiayuan | last3=Scholkopf | first3=Bernhard| issue = 2| journal = Advances in Neural Information Processing Systems| pages = 1601–1608| title = Learning with hypergraphs: clustering, classification, and embedding| year = 2006}}</ref> The applications include [[recommender system]] (communities as hyperedges),<ref>{{citation|last1=Tan | first1=Shulong | last2=Bu | first2=Jiajun | last3=Chen | first3=Chun | last4=Xu | first4=Bin | last5=Wang | first5=Can | last6=He | first6=Xiaofei|issue = 1| journal = ACM Transactions on Multimedia Computing, Communications, and Applications| title = Using rich social media information for music recommendation via hypergraph model| year = 2013|url=https://www.researchgate.net/publication/226075153| bibcode=2011smma.book..213T }}</ref> [[image retrieval]] (correlations as hyperedges),<ref>{{citation|last1=Liu | first1=Qingshan | last2=Huang | first2=Yuchi | last3=Metaxas | first3=Dimitris N. |issue = 10–11| journal = Pattern Recognition| title = Hypergraph with sampling for image retrieval| pages=2255–2262| year = 2013| doi=10.1016/j.patcog.2010.07.014 | volume=44}}</ref> and [[bioinformatics]] (biochemical interactions as hyperedges).<ref>{{citation|last1=Patro |first1=Rob | last2=Kingsoford | first2=Carl| issue = 10–11| journal = Bioinformatics| title = Predicting protein interactions via parsimonious network history inference| year = 2013| pages=237–246|doi=10.1093/bioinformatics/btt224 |pmid=23812989 |pmc=3694678 | volume=29}}</ref> Representative hypergraph learning techniques include hypergraph [[spectral clustering]] that extends the [[spectral graph theory]] with hypergraph Laplacian,<ref>{{citation|last1=Gao | first1=Tue | last2=Wang | first2=Meng | last3=Zha|first3=Zheng-Jun|last4=Shen|first4=Jialie|last5=Li|first5=Xuelong|last6=Wu|first6=Xindong|issue = 1| journal = IEEE Transactions on Image Processing| volume=22 | title = Visual-textual joint relevance learning for tag-based social image search| year = 2013| pages=363–376|url=http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | doi=10.1109/tip.2012.2202676| pmid=22692911 | bibcode=2013ITIP...22..363Y }}</ref> and hypergraph [[semi-supervised learning]] that introduces extra hypergraph structural cost to restrict the learning results.<ref>{{citation|last1=Tian|first1=Ze|last2=Hwang|first2=TaeHyun|last3=Kuang|first3=Rui|issue = 21| journal = Bioinformatics| title = A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge| year = 2009| pages=2831–2838|doi=10.1093/bioinformatics/btp467|pmid=19648139| volume=25|doi-access=free}}</ref> For large scale hypergraphs, a distributed framework<ref name=hyperx /> built using [[Apache Spark]] is also available.

==超图与机器学习==

超图已被广泛用于机器学习中，常作为一种数据结构或一种正则化的方式[25]。这些应用包括推荐系统(社团作为超边)[26]、图像检索(相关性作为超边)[27]、和生物信息学(生物、化学分子间相互作用作为超边)[28]。比较典型的超图机器学习方法包括：超图谱聚类法（用超图Laplacian扩展光谱图理论）[29]和超图半监督学习（通过引入超图结构来对结果进行限定）。对于大尺寸的超图，可以使用Apache Spark构建的分布式框架[15]。

==See also==
{{Commons category|Hypergraphs}}

* [[Simplicial complex]]

* [[Combinatorial design]]
* [[Factor graph]]
* [[Greedoid]]
* [[Incidence structure]]
* [[Matroid]]
* [[Multigraph]]
* [[P system]]
* [[Sparse matrix-vector multiplication]]
*[[Matching in hypergraphs]]

==Notes==
{{Reflist}}

==References==
* Claude Berge, "Hypergraphs: Combinatorics of finite sets". North-Holland, 1989.
* Claude Berge, Dijen Ray-Chaudhuri, "Hypergraph Seminar, Ohio State University 1972", ''Lecture Notes in Mathematics'' '''411''' Springer-Verlag
* Hazewinkel, Michiel, ed. (2001) [1994], "Hypergraph", [https://en.wikipedia.org/wiki/Encyclopedia_of_Mathematics Encyclopedia of Mathematics], Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
* Alain Bretto, "Hypergraph Theory: an Introduction", Springer, 2013.
* Vitaly I. Voloshin. "Coloring Mixed Hypergraphs: Theory, Algorithms and Applications". Fields Institute Monographs, American Mathematical Society, 2002.
* Vitaly I. Voloshin. "Introduction to Graph and Hypergraph Theory". [[Nova Science Publishers, Inc.]], 2009.
* This article incorporates material from hypergraph on PlanetMath, which is licensed under the[https://en.wikipedia.org/wiki/Wikipedia:CC-BY-SA Creative Commons Attribution/Share-Alike License].

==External links==
* [https://www.aviz.fr/paohvis PAOHVis]: open-source PAOHVis system for visualizing dynamic hypergraphs.

{{Graph representations}}

[[Category:Hypergraphs| ]]

[[de:Graph (Graphentheorie)#Hypergraph]]

==编者推荐==
*[https://book.douban.com/subject/1237624/ 《超图-限集的组合学》]by [法]Claude Berge
超图的第一本专著，作者是近代图论之父法国数学家Claude Berge，将图里的普通边拓展为超边，小小的一步拓展却引发了一个大的领域。