任意非赋权图同构的判定算法

摘要

本发明涉及一种判定任意非赋权图同构的算法，所述算法包括针对任意非赋权图的同构判定，提出一种新的算法，即在两个图中分别依次删除最大度数顶点及其关联的边，并对其邻点进行标记，在余下的子图中,如法炮制,直至余下的子图为空图，然后按照顶点标记判断两图是否同构，通过计算、比较两图的度序列、被删除的顶点的度数以及它们邻点的度集合,证明两图同构问题的复杂度是多项式的。本发明方法结果准确，计算简单。