Acta Scientiarum Naturalium Universitatis Pekinensis

Previous Articles     Next Articles

The Structure and Determination of the Set of Reversible Edges in a Directed Acyclic Graph

XU Jing, ZHENG Zhongguo   

  1. School of Mathematical Sciences, Peking University, Beijing, 100871
  • Received:2002-01-25 Online:2003-01-20 Published:2003-01-20


许静, 郑忠国   

  1. 北京大学数学学院概率统计系,北京,100871

Abstract: Authores have studied the structure of RG, which is the set of reversible edges of a dag(directed acyclic graph) G and present the sufficent and necessary condition to determine RG. This result can help to search the equivalent classes of a dag and be used in the learning of Bayesian Network.

Key words: directed acyclic graph, reversible edge, compelled edge, clique, v-structure, system of parent and children

摘要: 讨论了有向非循环图(dag)G的可反向边集合RG的结构,给出了判断RG的充分必要条件。这一结果将有助于设计算法搜索G中的等价类,在用得分等价原则学习贝叶斯网络结构时,可以进行局部得分,从而减少所需的数据量,提高效率。

关键词: 有向非循环图, 可反向边, 不可反向边, clique, v-结构, 父子结构

CLC Number: