复杂无向图的同构判定方法  

Isomorphism Determination Methods for Complex Undirected Graphs

作　　者：王卓 王成红 WANG Zhuo;WANG Cheng-Hong(School of Instrumentation and Optoelectronic Engineering,Beihang University,Beijing 100191;Council of Chinese Association of Automation,Beijing 100190)

机构地区：[1]北京航空航天大学仪器科学与光电工程学院,北京100191 [2]中国自动化学会理事会,北京100190

出　　处：《自动化学报》2024年第6期1143-1150,共8页Acta Automatica Sinica

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

摘　　要：针对一般复杂无向图的同构判定问题,给出了基于邻接矩阵之和的特征多项式判定条件;针对复杂无向连通图的同构判定问题,给出了基于距离矩阵特征多项式和邻接矩阵特征多项式的同构判定条件,将该条件用于复杂无向不连通图的各个连通子图,就可解决复杂无向不连通图的同构判定问题.上述两个判定条件均是充要条件且当复杂无向图退化为简单无向图时仍然适用.For the isomorphism determination problem of general complex undirected graphs,one determination condition based on the characteristic polynomial of the sum of adjacency matrices is proposed.For the isomorphism determination problem of complex undirected connected graphs,another determination condition based on the characteristic polynomials of the distance as well as the adjacency matrices is proposed,which can also be applied to each connected subgraph of the complex undirected unconnected graph,whose isomorphism determination problem can thus be solved.The above two are both necessary and sufficient conditions and still hold true when the complex undirected graphs degenerate into simple undirected graphs.

关 键 词：复杂无向图 邻接矩阵 距离矩阵 特征多项式 同构判定条件 

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