更改

由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内得到有效验证 。

由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内得到有效验证 。

我们可以在线性时间 linear time内检验超图是否是<math> {\alpha}</math>-无环的。 <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内检验超图是否是'''<math> {\alpha}</math>-无环的'''。 <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>

注意到<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)内完成检测。

注意到<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)内完成检测。