摘要
将判定两棵树的同构问题转化成“图的同构”问题和“两棵树根结点之间的对应关系”问题的判定。基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom_Up Layer Traversing)的方法,简称BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明。该算法很容易扩展为图同构的判定算法。
Solving the tree isomorphism problem is equivalent to solve two problems： whether there exists a bi-jection between two graphs and whether the bi-jection maps on distinguished node in one graph to one distinguished node in the other graph. Based on the relation between graphs and trees, a bottom up layer traversing algorithm, BULT algorithm for short, with linear time complexity and space complexity to solve these two problems is given. And the correctness of the altgorittma is also proven in the paper. The result can be easily extended to graphs.
出处
《中山大学学报（自然科学版）》
CAS
CSCD
北大核心
2005年第6期24-28,共5页
Acta Scientiarum Naturalium Universitatis Sunyatseni
基金
广东省科技厅工业攻关资助项目(A10103)
关键词
树
树同构
时间复杂度
空间复杂度
tree
tree isomorphism
time complexity
space complexity
