计算数学——根据已知链图找出最大链图的有效的算法

摘要

一个有效的处理工具．代表相同条件独立结构的链图称为Markov等价的．Frydenberg指出在等价的链图中存在一个包含其他所有等价链图的元素，称为最大链图．给出了一个根据已知链图找出最大链图的算法，计算复杂度仅为O（n3）（日前已有算法的复杂度约为O（n!）），从而给出了直观地判断一个链图是否是与之等价的最大链图的方法．14