更改

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

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-uniform hypergraph'''（所有超边的大小都为 k）。因此一个2-均匀超图就是普通图，一个3-均匀超图就是无序三元组 unordered triples 的集合，依此类推。超图也被称为从泛集 universal set 中抽取的一个集系统或集族 universal set。

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

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.

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），反之，大多数（但不是全部）[[二分图]]都可以看作是超图的关联图。

超图可以看做是'''关联结构 incidence structure'''。特别的，每个超图都有一个与超图相对应的二分 "关联图 incidence graph"或 "列维图 Levi graph"，反之，大多数（但不是全部）'''二分图 bipartite 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

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

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>

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

超图还有许多其它名称。在'''计算几何学 family of sets'''中，超图有时可以被称为'''范围空间 range space'''，将超图的边称为''范围 ranges''.<ref>{{citation

  | last1 = Haussler | first1 = David | author1-link = David Haussler

  | last1 = Haussler | first1 = David | author1-link = David Haussler

  | last2 = Welzl | first2 = Emo | author2-link = Emo Welzl

  | last2 = Welzl | first2 = Emo

  | doi = 10.1007/BF02187876

  | doi = 10.1007/BF02187876

  | issue = 2

  | issue = 2

  | journal = [[Discrete and Computational Geometry]]

  | journal = Discrete and Computational Geometry

  | mr = 884223

  | mr = 884223

  | pages = 127–151

  | pages = 127–151

  | title = ε-nets and simplex range queries

  | title = ε-nets and simplex range queries

  | volume = 2

  | volume = 2

  | year = 1987| doi-access = free

  | year = 1987

  }}.</ref>

  }}.</ref>

在[[合作博弈论]]中，超图被称为'''简单博弈'''（投票博弈）；这个概念被应用于解决[[社会选择理论]]（social choice theory）中的问题。在一些文献中，超边被称为''超连接''或''连接器''.<ref>Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.</ref>

在合作博弈论 cooperative game中，超图被称为'''简单博弈 simple games'''（投票博弈 voting games）；这个概念被应用于解决社会选择理论 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.

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.

The collection of hypergraphs is a [[Category (mathematics)|category]] with hypergraph [[homomorphism]]s as [[morphism]]s.

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

特殊类型的超图包括：上文简单讨论过的k-均匀超图；散簇 clutter，也即没有一条边作是另一条边的子集；以及'''抽象单纯复形 abstract simplicial complexes'''，这里面包含每条边的所有子集。

==== Definitions ====

==术语 Terminology==

 

====定义 Definitions ====

There are different types of hypergraphs such as:

There are different types of hypergraphs such as:

* ''Empty hypergraph'': a hypergraph with no edges.  

* ''Empty hypergraph'': a hypergraph with no edges.  

超图有不同的类型，如：

超图有不同的类型，如：

* 空超图 Empty hypergraph：没有边的超图

* 空超图 Empty hypergraph：没有边的超图

* 非简单（或多重）超图：允许有循环（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点。

 

* 简单超图：不包含循环和重复边的超图。

* 非简单（或多重）超图 Non-simple (or multiple) hypergraph ：允许有环 loops（有单个顶点的超边）或重复边的超图，也就是说可以有两个或两个以上的边包含同一组顶点。

* 𝑘-均匀超图：每条超边都正好包含 k 个顶点的超图。

 

* 𝑑-正则超图：每个顶点的度数都是 𝑑 的超图

* 简单超图 Simple hypergraph ：不包含循环和重复边的超图。

* 无环超图：不包含任何圈的超图。

 

* <math>k </math>-均匀超图 <math>k </math>-uniform hypergraph：每条超边都正好包含 k 个顶点的超图。

 

* <math>d </math>-正则超图 <math>d </math>-regular hypergraph：每个顶点的度数都是 𝑑 的超图。

 

* 无环超图 Acyclic hypergraph：不包含任何环的超图。

 

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

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）。

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

让 <math>H=(X,E)</math> 是一个超图，包含顶点集：

假定 <math>H=(X,E)</math> 是一个超图，包含顶点集：

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

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

和 ''边集''：

和 “边集”：

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

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

其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的[[索引集]]

其中 <math>I_v</math> 和 <math>I_e</math> 分别是顶点和边集的索引集 index set

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

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

e \cap A \neq \emptyset \rbrace \right).</math>

e \cap A \neq \emptyset \rbrace \right).</math>

''子超图'' 是去掉某些顶点的超图。在形式上，若 <math>A \subseteq X </math> 是顶点子集，则子超图 <math>H_A</math> 被定义为：

*'''子超图 subhypergraph''' 是去掉某些顶点的超图。在形式上，若 <math>A \subseteq X </math> 是顶点子集，则子超图 <math>H_A</math> 被定义为：

:<math>H_A=\left(A, \lbrace e \cap A | e \in E \land

<math>H_A=\left(A, \lbrace e \cap A | e \in E \land

e \cap A \neq \emptyset \rbrace \right).</math>

e \cap A \neq \emptyset \rbrace \right).</math>

Formally

Formally

一个''子超图''的''扩展''是一个超图，其中每个属于 <math>H</math> 的超边都部分包含在子超图的 <math>H_A</math>，并且完全包含在扩展的 <math>Ex(H_A)</math> 中。即在形式上：

:: 一个'''子超图'''的'''扩展 extension'''是一个超图，其中每个属于 <math>H</math> 的超边都部分包含在子超图的 <math>H_A</math>中，并且完全包含在扩展的 <math>Ex(H_A)</math> 中。即在形式上：

:<math>Ex(H_A) = (A \cup A', E' )</math>和 <math>A' = \bigcup_{e \in E} e \setminus A</math> 和<math>E' = \lbrace e \in E | e \subseteq (A \cup A') \rbrace</math>.

:<math>Ex(H_A) = (A \cup A', E' )</math>和 <math>A' = \bigcup_{e \in E} e \setminus A</math> 和<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

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>J \subset I_e</math> ，由 <math>J</math> 生成的部分超图就是

*'''部分超图 partial hypergraph'''是去掉一些边的超图。给定一个边索引集的子集 <math>J \subset I_e</math> ，由 <math>J</math> 生成的部分超图就是

 

Given a subset <math>A\subseteq X</math>, the ''section hypergraph'' is the partial hypergraph

Given a subset <math>A\subseteq X</math>, the ''section hypergraph'' is the partial hypergraph

而给定一个子集  <math>A\subseteq X</math>，则''分段超图''是部分超图

*而给定一个子集  <math>A\subseteq X</math>，则''section hypergraph''是部分超图:

:<math>H \times A = \left(A, \lbrace e_i |  

 

<math>H \times A = \left(A, \lbrace e_i |  

i\in I_e \land e_i \subseteq A  \rbrace \right).</math>

i\in I_e \land e_i \subseteq A  \rbrace \right).</math>

<math>H</math> 的对偶 <math>H^*</math> 则是一个顶点和边互换的超图，因此顶点由 <math>\lbrace e_i \rbrace</math> 给出，边由 <math>\lbrace X_m \rbrace</math> 给出，其中

<math>H</math> 的对偶 <math>H^*</math> 则是一个顶点和边互换的超图，因此顶点由 <math>\lbrace e_i \rbrace</math> 给出，边由 <math>\lbrace X_m \rbrace</math> 给出，其中:

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

 

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

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>

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

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）；

对于连通的超图'' G'' 和具有相同顶点连通的超图 ''H''，如果 ''H'' 的每个超边都由 ''G'' 中一个子图导出 induce，则 ''G'' 是一个主图 host graph；

对于不连通的超图 H，如果 ''G'' 和 ''H'' 的连通部分之间存在一个双射，使得 G 的每个连通部分 ''G'' 都是对应的 ''H'' 的主图，则 ''G'' 是一个主图。

对于不连通的超图 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]].

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]]。

一个超图是二分（bipartite）的，当且仅当它的顶点能被分成两类''U'' 和 ''V''  ：每个基数至少为 2 超边包含两类中的至少一个顶点。换而言之，超图则被称为具有 B 属性 Property 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.

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-段超图（或团图，表示图、原始图、盖夫曼图）是具有相同顶点的图，并且所有顶点对之间的边包含在相同的超边中。

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

==二部图模型 Bipartite graph model==

==二分图模型 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 (''x₁'',  ''e₁'') are connected with an edge if and only if vertex ''x₁'' is contained in edge ''e₁'' 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]].

A hypergraph ''H'' may be represented by a [[bipartite graph]] ''BG'' as follows: the sets ''X'' and ''E'' are the partitions of ''BG'', and (''x₁'',  ''e₁'') are connected with an edge if and only if vertex ''x₁'' is contained in edge ''e₁'' 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>为一个二部图。]]

[[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"的分割，而且 ("x₁",  "e₁") 与边连通当且仅当顶点"x₁"包含在" <math>H </math>"的边" e₁"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二部图也代表具有上述性质的部分超图。 这个二部图也称为'''关联图'''。

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

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.

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''' 定义。

与只有'''圈 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.

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.

<math>f_1 \cap f_4 \cap f_6 = \varnothing</math>

<math>f_1 \cap f_4 \cap f_6 = \varnothing</math>

在这个例子，<math>H</math> 和 <math>G</math>是等价的， <math>H\equiv G</math>，而且两者的对偶图是强同构的：<math>H^*\cong G^*</math>

在这个例子，<math>H</math> 和 <math>G</math>是等价的， <math>H\equiv G</math>，而且两者的对偶图是强同构的：<math>H^*\cong G^*</math>。

==对称超图 Symmetric hypergraphs==

==对称超图 Symmetric hypergraphs==