更改

添加19字节 、 2020年4月22日 (三) 17:41
无编辑摘要
第239行: 第239行:  
==Symmetric hypergraphs==
 
==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<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.
 +
 
超图<math>H</math>的<math>r(H)</math>表示该超图中任何一条边的最大基数。如果所有边具有相同的基数''k'',则称该超图为''均匀的''或''k-均匀的'',或称之为''k-超图''。图只是一个2-均匀的超图。
 
超图<math>H</math>的<math>r(H)</math>表示该超图中任何一条边的最大基数。如果所有边具有相同的基数''k'',则称该超图为''均匀的''或''k-均匀的'',或称之为''k-超图''。图只是一个2-均匀的超图。
 +
 
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 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''.
 +
 
顶点''v''的度''d(v)''表示包含该顶点的边的数量。如果每个顶点的度都为''k'',则超图''H''是''k-正则的''。
 
顶点''v''的度''d(v)''表示包含该顶点的边的数量。如果每个顶点的度都为''k'',则超图''H''是''k-正则的''。
 +
 
The dual of a uniform hypergraph is regular and vice versa.
 
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>.
 
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>.
 +
 
如果存在一个形如<math>\phi(x)=y</math>的自同构,则超图''H''的两个顶点''x''和''y''''对称''。如果存在一个自同构使得<math>\phi(e_i)=e_j</math>,则称两个边<math>e_i</math>和<math>e_j</math>为''对称''。
 
如果存在一个形如<math>\phi(x)=y</math>的自同构,则超图''H''的两个顶点''x''和''y''''对称''。如果存在一个自同构使得<math>\phi(e_i)=e_j</math>,则称两个边<math>e_i</math>和<math>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''.
 
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.
 
Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity.
 +
 
由于超图的对偶性,边传递性的研究与顶点传递性的研究是相一致的。
 
由于超图的对偶性,边传递性的研究与顶点传递性的研究是相一致的。
 +
 
==Transversals==
 
==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''.
 
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''.
 +
 
超图''H'' = (''X'', ''E'')的横截集(或“命中集”)是一个<math>T\subseteq X</math>集合,该集合与每条边都有非空的交集。如果''T''的真子集不是横截集,则称''T''为极小截集。''H'' 的横截超图是超图(''X'', ''F''),其边集''F''包含''H''的所有最小横截。
 
超图''H'' = (''X'', ''E'')的横截集(或“命中集”)是一个<math>T\subseteq X</math>集合,该集合与每条边都有非空的交集。如果''T''的真子集不是横截集,则称''T''为极小截集。''H'' 的横截超图是超图(''X'', ''F''),其边集''F''包含''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]].
 
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]].
计算横向超图在[[组合优化 Combinatorial Optimization]]、[[博弈论 Game Theory]]和[[计算机科学 Computer Science]]的一些领域(例如[[机器学习 Machine Learning]]、[[数据库索引 Indexing of Databases]]、[[可满足性问题the Satisfiability Problem]]、[[数据挖掘Data Mining]]和[[计算机程序优化 Program Optimization]])都有应用。
+
 
 +
计算横截面超图在[[组合优化 Combinatorial Optimization]]、[[博弈论 Game Theory]]和[[计算机科学 Computer Science]]的一些领域(例如[[机器学习 Machine Learning]]、[[数据库索引 Indexing of Databases]]、[[可满足性问题the Satisfiability Problem]]、[[数据挖掘Data Mining]]和[[计算机程序优化 Program Optimization]])都有应用。
 +
 
 
==Incidence matrix==
 
==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
 
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
16

个编辑