一种对称无向图的同构判定算法  

An isomorphism identification algorithm for symmetric undirected graphs

作　　者：李正平[1] 白倩倩 LI Zhengping;BAI Qianqian(School of Electronics and Information Engineering, Anhui University, Hefei 230601, China)

机构地区：[1]安徽大学电子信息工程学院,安徽合肥230601

出　　处：《合肥工业大学学报（自然科学版）》2021年第3期332-336,共5页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61474001)。

摘　　要：文章在电路模拟法的基础上提出了一种对称无向图的同构判定算法。电路模拟法对随机图的同构判定问题非常有效,但是对于处理对称度较高的图,判定效率明显降低甚至失效。该文提出的算法针对对称无向图的特性,在电路模拟法的基础上结合Dijkstra算法,综合得到顶点属性和最短距离序列来搜索顶点之间的映射关系,能够有效判定这类图的同构问题。Based on the circuit simulation method,this paper proposes an algorithm to determine the isomorphism of the symmetric undirected graphs.The circuit simulation method is very effective for the isomorphic identification problem of random graphs,while the identification efficiency is significantly decreased or even invalid for the graphs with higher symmetry.For the characteristics of symmetric undirected graphs,the proposed algorithm in this paper combines Dijkstra algorithm with circuit simulation method,searching the correspondence of vertexes according to vertexes invariant properties and distance sequences,which can availably determine the isomorphism of such graphs.

关 键 词：对称无向图 图同构 电路模拟法 DIJKSTRA算法 距离序列 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]