摘要： 提出了一种判别无向图同构的方法,该方法根据无向图的邻接矩阵的特征值来判别出图的同构关系,而不需要其它附加信息。同时给出用方法求出无向图的邻接矩阵的特征值的一种并行算法,它可以在分布式存储的多处理机上实现。实验结果表明,此方法是快速Jacobi有效的,能在较短的运算时间内给出判断结果。

关键词: 同构, 邻接矩阵, 特征值, 并行算法

Abstract: A method for testing isomorphism of undirected graphs is presented. The method tests the isomorphism by computing the ,eigenvalues of the graphs' adjacency matrixes without any further information. To compute the eigenvalues of the adjacency matrixesa parallel algorithm on multiprocessor with distributed memory is also presented. Experimental results show that the method is fast and ,effectiveit can get the test result in a very short time. ;;;

中图分类号: 

• TP301.6