任意图的同构判定算法:特征向量法

在构建有效描述任意图邻接矩阵的基础上,分别计算2个矩阵的特征值所对应的特征向量,并依据它们的极大无关组寻找可能的同构对应关系.通过逐一考查全体特征值,实现图同构的判定并确定同构图的顶点对应关系.随着判定规模增大及图对称性增强,与已有方法相比,文中方法具有更高的同构判定效率.实验结果表明,在多数情况下该方法是快捷有效的.

Isomorphism Testing Algorithm for Arbitrary Graphs-the Eigenvector-Based Method

With the construction of adjacency matrices that can effectively describe an arbitrary topological graph, the eigenvectors of the same eigenvalue of the two matrices are calculated respectively and the possible isomorphic correspondences are established on the basis of their maximum impertinent groups. After all the eigenvalues have been considered, isomorphism will be determined and correspondence of vertices in isomorphic graphs can be ultimately identified. With the scale and symmetry of graphs increasing, this method enjoys advantages in efficiency compared with some proposed methods. It has been experimentally verified to be efficient and effective in most cases.