1,526
个编辑
更改
跳到导航
跳到搜索
第98行：
第98行： − + 第105行：
第105行： −
→无环性
我们可以在线性时间 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>
我们可以在线性时间 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>
无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。 然而，反之均不成立。<ref name="fagin1983degrees" />
无环性的四个概念具有可比性: berge-无环性意味着 <math> {\gamma}</math>- 无环性， <math> {\gamma}</math>- 无环性又意味着 <math> {\beta}</math>- 无环性， <math> {\beta}</math>- 无环性又可以推出 <math> {\alpha}</math> 无环性。 然而，反之均不成立。<ref name="fagin1983degrees" />
===同构和相等===
===同构和相等===