论文部分内容阅读
图的同构判定是图论学科的基本问题之一。所谓图的同构，就是指两个图的拓扑结构完全相同。从定义看这个问题似乎并不复杂，但它却是一个世界性难题，多数学者将其归为NP-完全问题。
本文从图邻接矩阵的特征系统这一角度入手，提出了针对任意图同构的判定算法。在构建有效描述任意图邻接矩阵的基础上，分别计算两个矩阵的特征值所对应的特征向量，并依据它们的极大无关组寻找可能的同构对应关系。通过对全体特征值的逐一考察，实现图同构的判定并确定同构图的顶点对应关系。
文中详细介绍了算法和相关应用，完成的工作包括：
1)对已发表文章中提出的同构算法进行了回顾，并指明存在的不足；
2)对与算法相关的新概念进行了阐述，主要包括：图的预处理、描述任意图的邻接矩阵、权度序列、特征值序列、同序向量组和关系矩阵等。
3)对算法涉及的性质和定理进行了详细证明；
4)提出了任意图的同构判定算法：特征向量法。文中给出详细的算法描述同时，将本文算法与部分发表文献中方法进行了判定性能对比。
5)将算法应用于电路、化学、机械等领域中，实现算法理论价值与应用价值的结合。
大量同构判定实验表明，随着判定规模增大及图对称性增强，特征向量法与已有一些方法相比，具有更高的同构判定效率，并且证实多数情况下此方法是快捷有效的。