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

Isomorphism Determination Methods for Simple Undirected Graphs

作　　者：王卓 王成红[2] WANG Zhuo;WANG Cheng-Hong(School of Instrumentation and Optoelectronic Engineering,Beihang University,Beijing 100191;National Natural Science Foundation of China,Beijing 100083)

机构地区：[1]北京航空航天大学仪器科学与光电工程学院,北京100191 [2]国家自然科学基金委员会,北京100083

出　　处：《自动化学报》2023年第9期1878-1888,共11页Acta Automatica Sinica

基　　金：广东省重点领域研发计划(2021B0101410005);国家自然科学基金(61673041)资助。

摘　　要：给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义,将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵.针对简单无向连通图的同构判定问题:给出了基于距离矩阵特征多项式的同构判定条件;进一步,为避免计算误差对判定结果的影响,给出了基于距离矩阵的秩与列和向量的同构判定条件.上述两个判定条件均是充要条件且均具有多项式时间复杂度.This work gives the definitions of matrix isomorphic transformation,distance matrix of the simple undirected graph,column sum vector of the distance matrix,and distance spectrum of the graph,which extend the adjacency matrix-based isomorphism determination conditions to the distance matrix-based ones for simple undirected graphs.For the isomorphism determination problem of simple undirected connected graphs:One determination condition based on the characteristic polynomial of distance matrix is proposed;Further,another determination condition based on the rank and the column sum vector of distance matrix is proposed to avoid the influence of calculation error on the determination result.These two determination conditions are both necessary and sufficient conditions and both have polynomial time complexity.

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

分 类 号：O157.5[理学—数学]