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

陈中标

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

关键词：图的同构；关联点度矩阵；完全圈矩阵；正则图

图的同构判定问题是图论的一个难题，至今没有一个简单明了的方法来判断两图是否同构。现有的方法有金雄伟、梁立的《一种新的改进的判定图同构的遗传算法》，侯爱民的《求解图同构的判定算法》，郭美美的《基于CAD判断图同构》等。笔者也就此问题作简单探讨，引出了关联点度矩阵和完全圈矩阵的概念，并且给出了判定无向图同构的相关定理。

1 图同构的相关定义

[参考文献]

[1]金雄伟，梁立.一种新的改进的判定图同构的遗传算法[J].云南师范大学学报，2013（1）：50-52.

[2]候爱民.求解图同构的判定算法[J].计算机工程与应用，2011（16）：52-54.

[3]郭美美.基于CAD判断图同构[J].图形图像，2014（6）：49-51.

[4]汪毅，龚世才.图论导引[M].北京：人民邮电出版社，2007.

[5]瓒武.应用图论[M].长沙：国防大学出版社，2006.

[6]丁晓红，王敏丽.关于图的同构判定方法的探讨[J].大学数学，2006（2）：75-77.

[7]李晓艳.图的同构判定算法：关联度系列法及其应用[J].复旦学报：自然科学版，2001（3）：323.

The Improvement and Analysis of the Regular Graph Isomorphism Algorithm

Chen Zhongbiao

（Wuxi Technology and Professional College， Wuxi 214000， China）

Abstract： This article gives two important concepts of undirected graph isomorphism which is correlation degree matrix and full circle matrix. First，gives the two undirected graphs 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.

Key words： graph isomorphism； correlation degree matrix； full circle matrix； regular graph