763
个编辑
更改
跳到导航
跳到搜索
第88行：
第88行： − + − 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. − − 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. − − 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 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> − 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]]. − 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" />
→无环性 Acyclicity
一个'''超图 <math>{H} </math>'''可以用二分图<math>{BG} </math>表示，其构成如下: 集合<math>X</math>和<math> E </math>是<math>BG</math>的分割，而且 ("x<sub>1</sub>", "e<sub>1</sub>") 与边连通当且仅当顶点"x<sub>1</sub>"包含在<math>H </math>的边" e<sub>1</sub>"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为'''关联图'''。
一个'''超图 <math>{H} </math>'''可以用二分图<math>{BG} </math>表示，其构成如下: 集合<math>X</math>和<math> E </math>是<math>BG</math>的分割，而且 ("x<sub>1</sub>", "e<sub>1</sub>") 与边连通当且仅当顶点"x<sub>1</sub>"包含在<math>H </math>的边" e<sub>1</sub>"中。 反之，任何具有固定的'''部分 part'''且在第二部分中没有不连通节点的二分图也代表具有上述性质的部分超图。 这个二分图也称为'''关联图'''。
==无环性 Acyclicity==
===无环性===
与只有'''圈 cycle'''和'''森林 forest'''的普通无向图相比，对于超图的特殊情形，那些坍缩为普通图的无环性超图天然地有多种不等价的'''无环性 acyclicity''' 定义。
与只有'''圈 cycle'''和'''森林 forest'''的普通无向图相比，对于超图的特殊情形，那些坍缩为普通图的无环性超图天然地有多种不等价的'''无环性 acyclicity''' 定义。
由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内得到有效验证 。
此处，我们可以定义一个减弱的超图无环性的概念<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。 这个无环性的概念等价于超图是同形的 conformal (原图的每个团都被某个超边所覆盖) ，它的原图称为弦图 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 的表达能力有关。
此处，我们可以定义一个减弱的超图无环性的概念<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。 这个无环性的概念等价于超图是同形的 conformal (原图的每个团都被某个超边所覆盖) ，它的原图称为弦图 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 的表达能力有关。
我们可以在线性时间 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内检验超图是否是-无环的。 <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)内完成检测。
无环性的四个概念具有可比性: 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" />