基于关联点度矩阵的无向图同构判定

The Improvement and Analysis of the Regular Graph Isomorphism Algorithm

文章给出判定2个无向图同构的重要概念:关联点度矩阵和完全圈矩阵。首先对两无向图顶点的度序列进行非减排序编号,若两无向图和为非正则图,则同构于的充要条件是和的关联度矩阵的行相同;若和为正则图,则同构于的充要条件是和的完全圈矩阵相同。

This article gives two important concepts of undirected graph isomorphism which is correlation degree matrix and full circle matrix.First,gives the two undirected graph＇s vertex degree sequence for Not reduced order and serial number.Then,if the two undirected graphand is a Irregular figure,the sufficient and necessary condition of they are isomorphism is at the same line of correlation matrix.If the two undirected graphand is a regular figure,the sufficient and necessary condition of they are isomorphism is they completely same circle matrix.