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

Hierarchical Spectral Analysis Isomorphism Testing Algorithm for Undirected Graph

针对无向图同构的判定问题,一种层次化的基于谱分析的同构判定算法.比较两图的顶点数、边数以及度数序列对图进行预同构判定;然后对具有唯一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.