无向图同构的判定研究

摘要

在图论中,图同构是一个非常重要的问题,是一个N-P问题,在现实中有非常广泛的应用.根据许多的研究结果表明,这类问题应该有多项式时间复杂性的算法.只要其中一个问题能够解决,其他的问题都能够迎刃而解.本文针对无向图,根据图和图之间的关联矩阵,提出了一个实用的算法.在度数相同的顶点范围内,利用图的相邻顶点的度数序列,讨论其对图同构的影响.该算法降低了时间复杂性,具有一定的应用价值;但也有局限性,在判定的时候有一定的拒绝率.