无向图的层次化谱分析同构判定算法  

Hierarchical Spectral Analysis Isomorphism Testing Algorithm for Undirected Graph

作　　者：谢敏[1] 杨帆[1] 曾璇[1] 

机构地区：[1]复旦大学专用集成电路与系统国家重点实验室,上海201203

出　　处：《计算机辅助设计与图形学学报》2015年第11期2169-2176,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(91330201;61125401;61376040;61474026);国家"十二五"科技重大专项(2011ZX01035-001-001-003);上海市教育发展基金会晨光计划

摘　　要：针对无向图同构的判定问题,一种层次化的基于谱分析的同构判定算法.比较两图的顶点数、边数以及度数序列对图进行预同构判定;然后对具有唯一Fiedler向量的图通过层次化的谱分析算法进行再次同构判定.与最具代表性的同构判定算法Nauty相比,随着判定图的规模增大,该算法对于规则网格图和固定度数图具有更高的同构判定效率.In this paper, a hierarchical isomorphism testing algorithm based on spectral analysis is proposed for undirected graphs. The proposed algorithm firstly checks the vertices number, edge number and degree sequence of the two graphs. Afterwards, a hierarchical spectral algorithm is employed to further test the isomorphism of the graphs. The proposed algorithm can achieve higher efficiency for graphs of regular grid or fixed degrees compared with the state-of-the-art Nauty algorithm.

关 键 词：图同构 谱分析 Fiedler向量 层次化方法 

分 类 号：TP391.71[自动化与计算机技术—计算机应用技术]