根据已知链图找出最大链图的有效的算法  

作　　者：刘佰军[1] 郑忠国[1] 赵慧[1] 

机构地区：[1]北京大学数学科学学院,北京100871

出　　处：《中国科学（A辑）》2005年第10期1188-1200,共13页Science in China(Series A)

基　　金：国家自然科学基金

摘　　要：链图(CG)是Markov图模型的一个有效的处理工具.代表相同条件独立结构的链图称为Markov等价的.Frydenberg指出在等价的链图中存在一个包含其他所有等价链图的元素,称为最大链图.给出了一个根据已知链图找出最大链图的算法,计算复杂度仅为O(n^3)(目前已有算法的复杂度约为O(n!)),从而给出了直观地判断一个链图是否是与之等价的最大链图的方法.

关 键 词：Markov图模型 链图 最大链图 被保护边 算法 MARKOV 链 计算复杂度 处理工具 条件独立 

分 类 号：O157.5[理学—数学]