自动化学报2024，Vol.50Issue(6)：1143-1150,8.DOI:10.16383/j.aas.c230612
复杂无向图的同构判定方法
Isomorphism Determination Methods for Complex Undirected Graphs
摘要
Abstract
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 isomorph-ism 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 com-plex undirected graphs degenerate into simple undirected graphs.关键词
复杂无向图/邻接矩阵/距离矩阵/特征多项式/同构判定条件Key words
Complex undirected graphs/adjacency matrix/distance matrix/characteristic polynomials/isomorph-ism determination conditions引用本文复制引用
王卓,王成红..复杂无向图的同构判定方法[J].自动化学报,2024,50(6):1143-1150,8.基金项目
广东省重点领域研发计划(2021B0101410005),国家自然科学基金(61673041)资助 Supported by Key Area Research and Development Program of Guangdong Province(2021B0101410005)and National Natur-al Science Foundation of China(61673041) （2021B0101410005）
