施键兰



无向图同构的判定研究

施键兰

（福建农林大学东方学院，福建 福州 350715）

在图论中，图同构是一个非常重要的问题，是一个N-P问题，在现实中有非常广泛的应用。根据许多的研究结果表明，这类问题应该有多项式时间复杂性的算法。只要其中一个问题能够解决，其他的问题都能够迎刃而解。本文针对无向图，根据图和图之间的关联矩阵，提出了一个实用的算法。在度数相同的顶点范围内，利用图的相邻顶点的度数序列，讨论其对图同构的影响。该算法降低了时间复杂性，具有一定的应用价值；但也有局限性，在判定的时候有一定的拒绝率。

无向图；同构；图同构；关联矩阵

0 引言

无向图同构是个N-P问题，具有广泛的应用。简单来说，就是两个图的结构完全相同。通常图同构被应用在各种模式识别过程之中，比如汉字自动识别中，用来区分两个字形很相似的汉字；或者在电路图识别中，用于识别电路的拓扑结构；以及化学分子结构研究中，用于判断同分异构，等等。类似的问题有300多个，这些问题都是等价的。因此，研究其判定方法具有非常重要的现实意义[1]。

图同构问题来源于图论，由于根据其基本概念进行判断复杂性非常高，因此，许多人在研究该问题时，都试图降低其复杂性，寻找更简单的判断方法。根据许多的研究结果表明，这类问题，应该有多项式时间复杂性的算法。只要其中一个问题的多项式时间算法能够解决，其他的问题都能够迎刃而解。

本文主要讨论在无向图中同构的方法判断，试图找到一种能降低算法复杂性的方法[5]。

1 图的同构概念

首先，给出两图同构的定义：

形象来讲，就是两个表面上看过去相似，或者很不相似的图，在性质上是完全一样的。可以将图看做有弹性的，顶点可以随意移动位置，在不断的拉扯变形的过程中，如果一个图可以变成另一个图，那么两个图就是同构的[6-10]。

比如图1中所示的两组图，G1和G1；H1，H2和H3，表面上不同，但实际上两图的顶点之间可以找到一种一一对应关系，使得两图的性质完全相同。其中H1，H2和H3称作彼得松（Peterson）图，它们的顶点对应关系如图上标注的英文字母所示。

图1 两组同构图

2 无向图的关联矩阵表示

为了便于用代数方法研究图的性质，利用计算机解决实际问题，可以将图用矩阵来表示，将形象的图数字化之后存入计算机，之后利用特定算法对图进行性质判定。

在矩阵表示图之前，需要将图标定顶点和边的顺序，使其成为标定图。比如图2中所示的这张图：

图2 标定图举例1

图2是无向图，用关联矩阵表示为：

其中行为顶点序列，列为边序列，矩阵中的数字为该顶点和对应边的关联次数。该图有4个顶点5条边，因此其关联矩阵有4行5列。与其同构的图3：

图3 标定图举例2

Fig.3 Example 2 of the calibration diagram

其关联矩阵为：

由图同构的性质可以看出，若两图的关联矩阵，通过有限次的行列交换之后，能得到相同的矩阵，则两图同构。因此，通过矩阵表示图的方法，可以在计算机中编程实现图同构的判定。

但由于其中涉及到的行、列交换，在特定的图的情况下，有可能意味着行和列的全排列，所以，在最坏的情况下，交换的总次数将达到n!m!（其中n是图的顶点总数，m是图的边数）。因此，在图的定点数或边数的数量大一些的时候，这个复杂度就太高了[1]。

3 具体算法案例

根据图同构的性质，可以得到关于其同构的一些必要性。比如：两同构图必然顶点数和边数相同，度数列相同。根据其必要性，可以在判定的时候，对全排列的比较算法，做一定的改良，增加一些限制条件，仅对于度数相同的顶点，做相应的比较，忽略度数不同的顶点。这样可以大大降低运算的复杂性。

见图4中有G1，G2两幅图。这两幅图的特点是，都有6个顶点，5条边。画出关联矩阵之后，均为6行5列。

首先画出这两幅图的关联矩阵。

G1和G2的关联矩阵如下：

由于每条边都有两个顶点，因此关联矩阵的每一列的和都是2。从行的角度分析，每一行的数字和，等于每一个顶点的度数。因此，在该矩阵的最前面加一列，用来表示每个顶点对应的度数，方便之后的排列对比。图G1,和G2改变后的矩阵如下。

对每一条边的两个顶点，将其相邻顶点的度数，放到矩阵中。称呼第i行第j列的元素为aij，在G1中，a11=1，其对应的相邻顶点在a21，该顶点是2度，因此，就将数字2填入第一行第一列中，即a11=2。

按照这种规律整理完矩阵，得到如下两个矩阵。

对这两个矩阵，每行都按照数字从大到小进行排序，可以得到两个新的矩阵：

在这两个矩阵之中，对应度数相同的行，逐一进行比较。比如G1的第一行，其度数为1，在G2中找到了第一行为的度数也为1，比较后发现两行是相同的，因此就标注G2的第一行为G1的对应行，并将G2的第一行所有数字都改成0。重复这个过程，继续向下比较。G1的第二行是2度，对比G2中2度的顶点，有第2行和第4行。在这两行中，并没有和G1的第2行相匹配的行，所以对比结束，两图不同构。

之所以提出这种思路，是因为对于同构的图，其对应顶点的性质应该是完全相同的，即每个顶点所关联的边，其另一个顶点的度数序列应完全相同。通过这种判断思路，降低了对比次数，从而提高了算法效率。

归纳这个算法，具体的步骤如下：

步骤1：先做出两幅图的关联矩阵。

步骤2：在关联矩阵的每一行前面加上该顶点的度数作为行标。

步骤3：将每一行中顶点的相邻顶点的度数记录到矩阵中。

步骤4：按从大到小排列每行的顶点度数。

步骤5：对比度数相同的行，将对比成功的行进行标注。某两行对比不成功，则图不同构，退出对比。若成功，则重复该过程直至所有的行都对比完成。

4 结论

这个方法可以减少行列交换的重排列次数，由于采用了排序算法，列的时间复杂度为O(m2)，低于原本的m!。虽然行的对比次数，在极端情况下，也就是该图的每个顶点度数都接近相同，该图接近正则图的情况下，复杂度还是n!，但从整体来看，时间复杂度还是有相应降低的。

但这个算法也有缺陷，即具有一定的拒绝率，比如对于非同构的正则图，该算法无法判断出来。经过C语言实验进行数据测试后，对于不同构的两个图，顶点个数越少，运行时间越短。图形中相同度数的顶点个数越多，运行时间越长[3-4]。

[1] 李锋, 李晓艳. 图的同构判定算法: 关联度序列法及其应用[J]. 复旦学报(自然科学版), 2001.6, 318-325.

[2] 屈婉玲, 耿素云, 张立昂. 离散数学[M]. 高等教育出版社, 2015.

[3] 侯爱民, 郝志峰, 胡传福, 等. 无向图同构的快速算法[J]. 华南理工大学学报(自然科学版), 2011.10, 79-83.

[4] 侯爱民. 求解图同构的判定算法[J]. 计算机工程与应用, 2011, 47(16), 52-57.

[5] 李锋, 商慧亮. 有向图的同构判定算法: 出入度序列法[J]. 应用科学学报, 2002.6, 258-262.

[6] 罗笑玲, 黄绍锋, 欧阳天优, 等. 基于多分类器集成的图像文字识别技术及其应用研究[J]. 软件, 2015, 36(3): 98-102.

[7] 任忠良. 一种基于SIFT特征的快速图像匹配算法[J]. 软件, 2015, 36(6): 53-57.

[8] 王琪瑞, 帅天平. 含4-圈且不含3-圈的P4-等可覆盖图的刻画[J]. 软件, 2015, 36(10): 05-08.

[9] 卢超, 黄蔚, 胡国超. 基于图形数据结构的复杂对象建模设计[J]. 软件, 2015, 36(12): 220-223.

[10] 陈园, 侯赞, 刘军华, 等. 基于改进K-Means聚类医学图像配准[J]. 软件, 2018, 39(01): 75-82.

[11] 胡一然, 宋中山, 孙翀, 等. NVSA: 一种具有可变节点值的查询图搜索算法[J]. 软件, 2018, 39(3): 16-21.

The Study of Undirected Graph Isomorphism

SHI Jian-lan

(DongFang College, Fujian Agriculture and Forestry University, Fuzhou 350715)

Undirected graph isomorphism is a vary important problem in graph theory. It's an N-P problem. It has a wide range of applications in reality. According to many research results, this kind of problem should have polynomial time complexity algorithm. As long as one problem can be solved, all other problems can be solved. In this paper, a practical algorithm is proposed for undirected graph according to the association matrix between graph and graph. The effect on graph isomorphism is discussed by using the degree sequence of adjacent vertices within the same degree range. The algorithm reduces the time complexity and has certain application value. But also have limitation, have certain rejection rate when judging.

Undirected graph; Isomorphism; Graph isomorphism; Incidence matrix

O157.5

A

10.3969/j.issn.1003-6970.2018.11.015

福建省中青年教师教育科研项目：“图同构算法的研究与实现”，(闽教科〔2017〕76号，项目编号：JAT170897)

施键兰(1984-)，女，福建福州，讲师，研究方向：计算机算法。

施键兰. 无向图同构的判定研究[J]. 软件，2018，39（11）：64-67