CAJ | 학술논문

针对无向图同构的判定问题, 一种层次化的基于谱分析的同构判定算法. 比较两图的顶点数、边数以及度数序列对图进行预同构判定; 然后对具有唯一 Fiedler 向量的图通过层次化的谱分析算法进行再次同构判定. 与最具代表性的同构判定算法 Nauty 相比, 随着判定图的规模增大, 该算法对于规则网格图和固定度数图具有更高的同构判定效率.
침대무향도동구적판정문제, 일충층차화적기우보분석적동구판정산법. 비교량도적정점수、변수이급도수서렬대도진행예동구판정; 연후대구유유일 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.