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