非正则图同构的算法改进及分析

陈中标

（无锡科技职业学院，江苏 无锡214000）

非正则图同构的算法改进及分析

陈中标

（无锡科技职业学院，江苏 无锡214000）

对于非正则图的同构问题,给出了新的判定方法,并且对该方法的复杂度进行了简单的分析,最后用实例证明新方法比以往的方法简单方便。

图同构;邻接矩阵;关联度;算法

引言

图的同构判定问题是图论学科的基本问题之一。所谓图的同构,简单地说,就是两个图的结构完全相同。以往人们用图的关联矩阵相同或邻接矩阵相同来判定任意两图是否同构。但是,若图的顶点序号标记不同,则其本身就会产生不同个关联矩阵、邻接矩阵,此时，当两图的顶点数量较多时,要比较该两图是否同构,计算起来相当复杂。本文针对非正则图的同构问题,给出改进的算法步骤并且对其算法进行简单的分析,最后用实际例子进行验证,结果表明改进的算法比以往的算法简单。

1 图同构的有关概念

定义1[1]如果两个图G1与G2的点之间一一对应,边之间一一对应,而且对应点与对应边之间保持相同的关联关系,那么G1与G2同构,记作G1≌G2。

定义2[2]顶点的度全相等的图称为正则图。

定理1[2]图G1与G2同构当且仅当对某一顶点的顺序,它们的邻接矩阵相同。

2 图同构的判定方法

以往人们常用以下方法来判断任意两图是否同构[3]:首先写出两个图G1与G2的邻接矩阵或者关联矩阵A1与A2;然后分别对A1和A2的行、列进行初等变换,若能使A1=A2,则判定G1≌G2，否则G1不同构与G2。笔者对以上方法进行简单的分析,若对所有可能的行、列交换意味着行的全排列与列的全排列，所以行、列交换的总次数将达到n！m！（n为图顶点数，m为边数）。若n、m都比较大时，计算起来相当复杂。

例1判断图1和图2是否同构。

图1

图2

解：分别写出图1和图2的邻接矩阵,记作A（D）和B（D），则

,虽然A（D）和B（D）含有相同个数的0,相同个数的2,但也不能表明它们就是同构的,因此要对A（D）或B（D）进行初等变换,经变换后看是否有与对方完全相同的矩阵。第一步:A（D）中第一行与第二行交换位置;第二步:第三行与第五行交换位置;第三步:第一列与第二列交换位置;第四步:第三列与第五列交换位置,经过一系列交换得

故图1与图2是同构的。

3 非正则图同构的改进算法

在以往判断两图是否同构的过程中,需要对其生成的矩阵进行行、列交换,然后根据交换后的矩阵是否相同来判定两图是否同构。构成算法的复杂是因为两图中的顶点的顺序不同,即度序列不同,导致重复计算。若能合理的给顶点进行编号,有时直接就可以判断两图是否同构,这样就可以减少冗余计算,给计算带来方便。下面给出非正则图的同构判定的新的算法。

3.1 非正则图同构的算法步骤

设有两图G1与G2,顶点分别为Vij、V'ij（i=0，1，2，…；j=0，1，2，…）,邻接矩阵分别记为A（D）和A'（D）。

第一步:对两图按度序列进行不减排序并且编号,记作Vij、V'ij（i=0，1，2，…；j=0，1，2，…）。i表示第n个顶点的度数,表示对相同度的顶点的编号,若i=i+1，则j=j+1，否则置j=1。

第二步:若i=1或两图的编号Vij≠V'ij,则两图不同构,退出.否则转第三步.

第三步:若Vij＝V'ij,则写出相应的邻接矩阵,记作A（D）和A'（D），若A（D）＝A'（D）,则两图同构。

建设智慧校园旨在推动下一代数字技术在智慧校园建设中的创新应用，改造和优化现行校园网络环境，构建高速泛在、智能灵活、开放共享、安全可靠的校园信息环境。2015年以来，学校启动了智慧校园建设，并将智慧校园建设列入学校“十三五”规划重点项目，设立智慧校园建设专职系统集成、软件研发和推广团队，保障智慧校园试点项目顺利实施。

第四步:若A（D）≠A'（D），则对i相同的标号中,交换j的顺序,重新编号，并且给出相应的邻接矩阵,若所有的j都交换顺序后A（D）≠A'（D），则两图不同构,否则转第三步.

例2用4.1方法判定例1中两图是否同构。

解:按4.1算法对图1、图2进行编号,得到以下图3、图4,如图所示,经过编号后的图3、图4,不必计算就可以直接判断两图是同构的。

图3

图4

例3给出以下两图,图4、图5,判断两图是否同构。

图5

图6

解:以上两图的顶点数有6个,如果用以往的算法难度较大,按4.1算法对两图分别进行编号,Vij、V'ij（i=0，1，2，…；j=0，1，2，…），然后分别写出它们的邻接矩阵A（D）和A'（D），

重新编号,图5中V11与V12交换位置,如图7所示。

图7

写出新的邻接矩阵

再重新编号，V21与V22交换位置,写出相应的新的邻接矩阵A（D），若A（D）≠A'（D），再交换V31与V32位置重新编号，写出相应的新的邻接矩阵A（D），若A（D）≠A'（D），根据算法停止编号,判定图5与图6是不同构的。

3.2 算法分析

该非正则图同构的新算法，主要在于对两图编号后,若得到Vij＝V'ij，则说明它们有相同的顶点个数及相同度数的顶点数，该条件已经满足了图同构的定理1条件。然后分别写出两图的邻接矩阵后,不同的地方就在相同度数的顶点的编号顺序,因此只要对相同度数顶点的编号进行重新排序即可。若图有n个顶点m条边,则只需进行计算m！次,而以往需要n！m！。若n、m都比较大时，计算复杂度的差距是非常大的。在该新算法的使用过程中,若m较小,直接笔算就可得出结论,若m较大时,计算起来还是有一定的难度,此时我们可以借助计算机来实现。

4 总结

以上图的同构的判定方法只是针对于非正则图而言的,而对于正则图的同构的判定还没有更好的方法，因此如何判断两正则图是否同构是我们继续要努力的目标！

注释及参考文献：

[1]耿素云,屈婉玲,张立昂．离散数学[M]．北京:清华大学出版社,2004:59．

[2]范益政,汪毅,龚世才,等．图论引导[M]．北京:人民邮电出版社,2007:102．

[3]陈晓红,王敏丽．关于图的同构判定方法的探讨[J]．大学数学,2006,2(2):75-77．

The Improvement andAnalysis of the Regular Graph IsomorphismAlgorithm

CHEN Zhong-Biao
(Wuxi Technology and Professional College,Wuxi,Jiangsu 214000)

A new decision method for non regular graph isomorphism problem is given in this article which also analysis its complexity.Finally,an example is used to prove this methed is simple and convenient than before.

graph isomorphism;adjacency matrix;correlation;algorithm

0157．5

A

1673-1891（2015）01-0025-03

2014-10-29

陈中标(1981-)，男，江苏盐城人，讲师，主要从事计算机科学教学研究。