简单无向图的同构判定方法

摘要：

给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义,将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵.针对简单无向连通图的同构判定问题:给出了基于距离矩阵特征多项式的同构判定条件;进一步,为避免计算误差对判定结果的影响,给出了基于距离矩阵的秩与列和向量的同构判定条件.上述两个判定条件均是充要条件且均具有多项式时间复杂度.

关键词：简单无向图、同构判定条件、距离矩阵列和向量、图的距离谱、特征多项式

所属期刊栏目：49

分类号：O151.21;TP301.6;O221.5

在线出版日期：2023-10-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1878-1888