1,526
个编辑
更改
跳到导航
跳到搜索
第106行：
第106行： − + − + + + + + + + + + + +
→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.
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.
由Claude Berge 给出了超图非循环性的首个定义: <ref>Claude Berge,[https://www.amazon.com/Graphs-hypergraphs-North-Holland-mathematical-library/dp/0444103996 ''Graphs and Hypergraphs'']</ref> 如果它的'''关联图'''(上面定义的二部图)是非循环的，则称这个超图是 Berge 不循环的。 这个定义是非常严格的：例如，假设一个超图有一些顶点<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内得到有效验证 。
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]].
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>
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]].
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" />
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==
==Isomorphism and equality==