基于复杂邻接矩阵和散列函数的图同构算法---毕业论文

本 科 毕 业 论 文 基于复杂邻接矩阵和散列函数的图同构算法Graph Matching Algorithm Based on Complicated Adjacency Matrix and Hash Function姓 名：学 号：学院：软件学院系：软件工程专 业：软件工程年 级：指导教师： 年 月摘要本文首先介绍了图同构问题以及之前的相关研究，指出图同构问题在算法研究领域的地位。图同构问题是目前少数几个既没有被归为NP完全问题，也没有被归为P问题的NP问题，目前还没有多项式复杂度的算法。然后总结了图同构的各种算法，通过比较分析，发现了现有图同构算法所具有的共性，指出了目前的一些算法的优缺点。接着给出了图同构问题的数学定义，结合矩阵的概念给出了图同构更具体的数值计算的表述方式，用更接近图同构问题的数学本质的方法来理解和解决问题。本文结合传统的图同构算法的结构设计，从数学的角度提取图同构更接近其本质的性质给出具体的计算方法，采用了改进的复杂邻接矩阵作为图的存储结构，实现了用成熟的数学模型来表述图，并且使用散列函数的概念来实现具体的算法。本文所实现的CAMH算法明显优于传统的图同构算法，在计算方法上也比现有的各种算法更简单，在较好情况下算法复杂度为O(n2)。但是如果参与比较的图出现自同构现象或者Hash冲突情况会大大增加算法运算量，这种情况只有在给出进一步的数学研究成果后才可能解决。在图挖掘中往往不仅要求判断两图是否等价，还要得出两图中节点的对应关系，这无形中也增加了图同构算法的复杂度。关键词：图挖掘；复杂邻接矩阵；图同构AbstractThis paper introduces the problem of graph matching and the related researches firstly, and indicates the position of graph matching problem in algorithm research. Graph matching problem is one of a few NP-problems which havent been proved to be NPC-problem or P-problem, and there is no polynomial algorithm. Then it summarizes some recent algorithms of graph matching problem, and discovers that all these algorithms have a comman characteristic. It also gives the mathematics concept of graph matching, and a formulation of graph matching using matrix, which are easy to be processed by computer.This paper gives a new graph matching algorithm, CAMH, which conbines the structure of classical graph matching algorithms and new mathematic characteristics, uses a developed mathematic model, improved complex adjacency matrix, to store and describe a graph, and implies a specific algorithm using a hash function.The algorithm in this paper is better than classical graph matching algorithms obviously, and its computing method is easier than recent algorithms. Its average time complex is O(n2) in good conditions, but the amout of computation will increases heavily when the graph is self-isomorphic or hash conflict occurs. This problem can be solved only when there is new achievement in mathematic. Especially in graph mining， it needs not only to judge whether the two graph are equivalence， but also the mapping of the nodes. This also increases the time complexity of graph matching algorithm.Keywords: Graph Mining; Complicated Adjacency Matrix; Graph Matching目录第一章绪论11.1研究背景及选题意义11.2研究现状及存在问题21.3主要研究内容及特色41.4本文结构安排4第二章当前主要的图同构算法62.1图同构问题62.2电路模拟法82.3关联度和出入度序列算法122.4基于邻接矩阵的图同构算法研究192.5特征向量法202.6图同构算法的分析232.7小结24第三章CAMH算法设计与实现253.1复杂邻接矩阵253.2图同构的数学解释273.3 CAMH图同构算法283.3.1 CAMH算法思想283.3.2 CAMH算法设计293.4小结32第四章实验与结构分析334.1系统实现334.1.1 isomorph包344.1.2 matrix包354.1.3 classic包384.2实验结果及分析394.3算法复杂度分析和存在的问题444.4小结45第五章总结与展望46致谢语47参考文献48ContentChapter 1Introduction11.1 Research Background11.2 Present Research and Problems21.3 Main Characteristic41.4 Contents and Organization4Chapter 2Related Work62.1 Graph Matching Problems62.2 Circit Simulation82.3 Degree of Association and I/O122.4 Adjacency Matrix Based Algorithms192.5 Eigen System202.6 Graph Matching Algorithms Analysis232.7 Summary24Charpter 3CAMH Algorithm Approach253.1 Complicated Adjacency Matrix253.2 Math Principle of Graph Matching273.3 CAMH Graph Matching Algorithm283.3.1 CAMH Algorithm idea283.3.2 CAMH Algorithm Design293.4 Summary32Charpter 4Experiment and Analysis334.1 Application334.1.1 Package isomorph344.1.2 Package matrix354.1.3 Package classic384.2 Result and Analysis394.3 Complexity of the Algorithm444.4 Summary45Charpter 5Conclusions and future works46Acknowledgement47References48基于复杂邻接矩阵和散列函数的图同构算法第一章绪论1.1研究背景及选题意义与一般意义上的“图像”概念不同，这里的“图”指的是图论意义上的图，它由一些节点以及连接节点的边构成，经常用来表示一些实体和实体间的关系。图挖掘就是对这种关系数据进行挖掘从而得到有价值的信息和模式。而图挖掘中普遍使用了图同构的算法，而且经常要频繁地将某一大图中的子图与目标图进行比较。比如为了判断一个子图是否为频繁，必须统计该子图的重复出现的次数，这时就要遍历原图中的子图并将该子图与目标图进行比较。不难想象，这种两图间进行比较的次数是原图节点个数的指数级。这就使得图同构算法的运行效率直接影响到图挖掘算法的时空复杂度，选用一个好的图同构算法能在根本上提高图挖掘算法的效率。但是对于图的匹配目前还没有一个多项式级的好算法。理论上可以证明图同构算法属于NP问题，即它的结果的验证时间为多项式级，但是仍然没有对它的求解时间的证明。也就是说既不能说它的复杂度是多项式级，也不能说一定不是多项式级，因此研究图同构的算法是有意义的，一个图同构的快速算法将直接改进大部分图挖掘算法的运行效率。在图挖掘中往往不仅要求判断两图是否等价，还要得出两图中节点的对应关系，这无形中也增加了图同构算法的复杂度。因为两图是否等价这个问题的结果只有一个，真或假，而如果两图等价得出的节点的对应关系则可能不止一种。要处理n个节点并且要产生m（0mn!）个结果，所用的时间至少为nm，这在增加图同构算法的复杂度的同时也放宽了限制，只要能满足平均时间消耗较低，而且可以通过多次低时间复杂度的计算排除绝大部分错误答案，就可以称为好算法。图的经典存储结构包含邻接矩阵、邻接表、十字链表等，其中邻接矩阵表示法与其他表示法不同，它不是对图的简单模拟，而是抽象为一种数学概念矩阵，这有助于从本质上解释图同构的概念，也可以从数学的角度给出更直接更高效的算法。已经有很多图论或者计算机算法上的，借助矩阵和它的一些特性解决图同构问题的尝试，但是传统的邻接矩阵表示法仍然不足以表示图挖掘中的复杂图，必须使用复杂化的邻接矩阵。本文就是总结和图同构相关的各方面的研究成果和结论，尝试给出一个好的图同构算法，从而有助于解决更多图相关的计算问题。不仅在图挖掘领域需要处理图之间的同构关系，由于图同构是非常经典的数学图论问题，因此在很多其他领域也都有应用。比如在化学的分子结构研究上，将一个分子看成图之后，就可以将分子和分子间的同构比较看作图和图的同构判定；在社会关系研究领域，将人与人之间的关系网看作图，就可以将团体间的同构比较看作图和图的同构判定。此外还有很多方面可以利用图的同构算法，因此解决同构算法对各方面的计算都有很大的促进作用。1.2研究现状及存在问题图的同构判定问题是图论学科中的基本问题之一。所谓图的同构，就是两个图的结构完全相同。有人试图用图的一组不变量来确定图的同构，如回路数、树数、连通片数等，这些尝试都归于失败1,2。因为不同构的图也会出现完全相同的不变量，有人3曾经认为图的邻接矩阵的特征多项式和特征值可能是图的同构判据，结果依然失败了，因为不同构的图也可能有相同的特征多项式和特征值。多年来，人们一直在寻找一种有效的同构判定方法，但是对于图的匹配目前还没有一个多项式级的好算法。理论上可以证明图同构算法属于NP问题4-9，即它的结果的验证时间为多项式级，但是仍然没有对它的求解复杂度的证明。也就是说既不能说它的复杂度是多项式级，也不能说一定不是多项式级。如果使用穷举法计算，则需要依次尝试n个节点的全排列才能得出所有的结果，时间复杂度大于O（n!）。目前，研究人员在同构判定问题上提出了一些新方法，如将同构问题等效转换的电路模拟法10,11、以拓扑图的图论特性为依据的关联度序列法3和出入度序列法4、基于Hopfield 网络的图同构判定算法5等，它们在判定的速度与准确性上都取得新的进展。但一些文献10,11 12只能处理不含权值的无向图；李锋等人则针对不含权的有向图13；基于Hopfield 网络的方法可能导致网络运行至不希望的吸引子或吸引环内，而使判定速度变慢1415。现有的算法都没有从根本上解决同构的问题，仍然是在进行穷举求解，只不过通过各种各样的约束条件进行剪枝，缩小穷举的范围。并且由于各自的局限性，现有的各种算法都不算一个好的算法，无法解决图挖掘中的图同构问题。而且所有的算法都止于得出两图是否同构，对于图中节点的各种对应关系都没有进行计算。除了Hopfield 网络算法之外，考虑其他的各种同构算法，如果抛开它们给出的各种解释，只观察它们的计算过程则不难发现，所有的算法都包含三个步骤。假设两个图的节点数目都是n，第一步对两个图分别计算n个数值序列：在电路模拟法中求出了n-1个节点的节点电压，加上假设的第一个节点为基准电压，共有n个数值；在关联度序列和出入度序列算法中，直接用每个节点的拓扑特征信息求出n个数值；在特征值系统算法中，由于n阶方阵有n个特征值和n个特征向量，这样就计算出了n个数值。在这一步上各种算法都有自己的计算方法和解释，但求得的结果和内涵其实都是一样的。第二步，将两个图的两组数值序列进行配对，它们的对应关系实际上就代表了节点的对应关系，这样就求出了几种可能的同构变换。第三步必须对这些可能的同构对应关系进行验证，如果验证成功，则两图同构。因此除非在数学上取得了突破性进展，给出了图同构的更简单有效的充分必要条件，否则同构算法就仍然要使用这三步的计算方法，只不过在第一步求n个数的数值序列时有可能找到更有效的算法。而有些算法看似复杂而有效，综合使用了其他学科的知识，或者采用了数学中更复杂的概念和计算，但是并没有做出实质上的突破，不能摆脱那三个步骤的约束，甚至在第一步求解数值序列的时候也没有好的表现。因此图同构算法的主要改进方法有三种：1. 寻找一个图同构的容易进行验证的充分条件，这样可以一劳永逸的解决图同构问题，同时这也意味着证明图同构问题是属于P问题的；然而这种方式显然更依赖于数学上的进步和图论上新的研究成果，目前仍没有大的进展。2. 寻求图的等价表示方法，将图进行转化为新的数学模型之后寻找一个解决同构问题的方法。3. 进一步改进三个步骤中的第一步，使用更严格的必要条件排除非同构的候选匹配方案，从而优化算法。 1.3主要研究内容及特色本文借鉴了以往的算法设计以及数学研究，综合了几个方面的成果，并提出了新的图同构算法。主要的创新点和特色在以下几个方面。1. 本文所提出的算法首先对传统的邻接矩阵表示法做出了改进，用复杂化的邻接矩阵来存储图的信息，从而可以用比较简单的数学概念来表示图并且使得所处理的图可以有多种类型的边，两节点间允许有重复的边。2. 分析了图同构的数学本质，说明了同构的两个图其实是既相似又合同的，并且其中的元素集合是相同的。3. 从这个图同构的本质出发，借鉴散列函数，本文提出了一种新的基于复杂邻接矩阵和散列函数的图同构算法（Complicated Adjacency Matrix and Hash Function based graph matching algorithm，CAMH），不仅有效的解决了图同构问题，而且可以给出节点的所有对应可能。1.4本文结构安排本文首先介绍了图挖掘中的图同构问题，回顾了以往对于图同构问题的各种研究和成果，然后给出了图的复杂邻接矩阵表示法，并在此基础上提出了新的图同构算法的理论证明和具体实现，最后得出本文结论，并提出未来需要改进的工作。本文共五章，其中：第一章 绪论：介绍了本文研究的背景及研究意义。第二章 当前主要的同构算法：介绍了图同构问题以往的研究和成果，以及其他基于邻接矩阵表示法的图算法研究。第三章 算法设计与实现：介绍了传统的邻接矩阵表示法以及它在图挖掘领域的不足，提出本文使用的复杂邻接矩阵表示法。第四章 实验与结构分析：给出算法的具体实现并在给定的数据集上进行实验，对实验结果进行分析。第五章 总结及未来工作：对本文工作进行总结并提出进一步的研究计划。第二章当前主要的图同构算法2.1图同构问题本文所研究的图是图论意义上的概念。定义1. 图G由两个集合V和E组成，记为：G=(V, E)。其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。图的同构判定问题是图论学科中的基本问题之一。所谓图的同构，就是两个图的结构完全相同。严格的定义如下：定义 2. 图G(V,E) 和G(V,E) 同构，若存在V到V的一个双射，使得P ( u,v) E ( u),( v) )E，且(u , v) 的重数和( u),( v) )的重数相同。假定将图表示为其邻接矩阵，则两个图的同构判定问题可描述为：输入：图G和G的邻接矩阵A(G）= (auv)和A(G) =( auv)。输出：若G和G所表示的图同构，则输出G的行号集合 1 , 2 , ,n 到G的行号集合 1 ,2 , ,n的一个双射，使得对任何u, v 1 , 2 , , n，若auv0 必有auv=a（ u）（ v）；否则输出不同构信息。此问题在图论中被认为是很麻烦的。根据上述图同构的定义，判断图G、G是否同构，等价于判断是否存在 1 ,2 , , n的一个置换12n（1）（2）（ n），满足问题定义中的条件。强力算法的思想是，在 1 , 2 , ,n 的所有n ! 个置换构成的置换群中查找同构映射。显然，此算法的时间复杂度为O（n!）。理论上这是一个比指数级更复杂的算法。有人试图用图的一组不变量来确定图的同构，如回路数、树数、连通片数等。但是目前所作的所有尝试都归于失败。寻找图同构的不变量实际上是要寻找一个图同构的充分条件，但已知一个结论去求条件往往比求解一个问题更困难，因此目前寻找的各种所谓不变量都是图同构的必要条件。对这些不变量进行检验只能排查一部分不同构的情况，但是因为不同构的图也会出现完全相同的不变量，所以这些不变量并不能有效的解决同构问题。有人曾经认为图的邻接矩阵的特征多项式和特征值可能是图的同构判据，结果依然失败了，因为不同构的图也可能有相同的特征多项式和特征值。多年来，人们一直在寻找一种有效的同构判定方法，但是对于图的匹配目前还没有一个多项式级的好算法。理论上可以证明图同构算法属于NP问题，即它的结果的验证时间为多项式级，但是仍然没有对它的求解复杂度的证明。也就是说既不能说它的复杂度是多项式级，也不能说一定不是多项式级。目前，研究人员在同构判定问题上提出了一些新方法。电路模拟法2将图转换为伴随电路。然后选定一个节点电压为基准，并在该节点施加激励电流，这样其他各节点就有一个电压。以这些节点电压按照大小顺序排列，如果两图同构，则节点电压完全相同。如果节点电压的序列不同，则两图不同构；但是即使相同，仍然不能保证两图同构，还要进行进一步验证。实际上电路模拟法只是利用了一个图同构的必要条件，并且转换为伴随电路颇有点画蛇添足的意味。如果抛开电路，只看算法中做的计算，我们可以发现这种算法实际上是取某个点为基准点后，给其他各点一个权值，然后对权值的集合进行比较。所以这种方法看起来比关联度序列法3和出入度序列法4更复杂，但是基本思想是一样的，而且它的计算更加复杂耗时，涉及到了浮点计算，这也使算法的效果更难以估计。以拓扑图的图论特性为依据的关联度序列法3和出入度序列法4则直接利用了图同构的几个必要条件，直接用关联度或者出入度作为节点的权值，然后比较节点权值的集合来排除不同构的可能。相比前面的电路模拟法，这类算法的计算更简单，大多为适合计算机的整数计算。但是相对来说，缺点也是明显的，由于节点权值的计算过于简单，所以在很大情况下会出现冲撞的情况：虽然两节点不可能对应，但是计算出的权值却是一样的。在这种情况下，假设两图都有n个节点，其中m个节点的权值计算是一样的，那么就需要对m个节点的所有对应情况进行排查，也就是说时间复杂度为O（m!），虽然不高于原先预计的O（n!），但是在冲撞次数高的情况下仍然非常耗时。基于Hopfield 网络的图同构判定算法5等，它们在判定的速度与准确性上都取得新的进展。但是基于Hopfield 网络的方法可能导致网络运行至不希望的吸引子或吸引环内，而使判定速度变慢56。但一些文献23只能处理不含权值的无向图；李锋等人则针对不含权的有向图4。由于各自的局限性，现有的各种算法都不算一个好的算法，无法解决图挖掘中的图同构问题，而且所有的算法都止于得出两图是否同构，对于图中节点的各种对应都没有进行计算。2.2电路模拟法首先介绍几个电路模拟法中用到的概念。相同电路是指，如果电路N与N对应的拓扑图G与G是同构图，且N与N对应支路上有相同的电路元件，那么N 与N称为相同电路，记为N=N。如图2-1所示。图2-1 相同电路伴随电路是指将任意图G 的边用电导替代，电导为该边的权值wij（或mij） ，对有向边按其方向加上并联电流源，电流为该边的权值wij （或mij），这样所得电路N 称为G 的伴随电路。伴随电路中电流源是与电导并联的，需要将电流值设为该边的权值（即电导值） ，这样电流源和电导才能对应起来，唯一的确定一条有向边，而没有对应电流源的电导，则表示一条无向边。显然，按伴随电路的定义建立的伴随电路与原任意图的对应是唯一的。定理1. 同构图的伴随电路是相同电路。图2.2中的G 与G对应的伴随电路如图2-2所示，其中为避免电导值与电流源值混淆，图中电流源电流值后加上符号“”，显然N 与N是两个相同电路。图2-2 伴随电路伴随电路的定义及定理说明了，判定两个图是否同构就等价于判定两个伴随电路是否相同。这样图的同构问题就转化成了电路的相同问题。全激励是指，在n 个节点（电路的节点即拓扑图的顶点） 的伴随电路N 中，以节点i 为参考点，在i 与其余n - 1 个节点间分别施加激励电流源I s = 1 ，电流方向都是从i 指向其余节点，这样一种激励方式称为节点i 的全激励。另外还有定理：相同的伴随电路N 和N， 对应节点的全激励所产生的节点电压对应相等。根据电路理论，相同电路在相同的激励下应有相同的响应。所以相同伴随电路N 与N对应节点的全激励所产生的节点电压必然一一对应相等。这里以图2-3中电路为例，如在节点1与1施以全激励Is。列出和求解这两个电路的节点电压方程，从结果可以看出，各节点电压对应相等。V 2 = V 2= 1. 377 8 ， V 3 = V 3= 1. 088 9 ，V 4 = V 4= 1. 622 2节点电压序列与节点电压序列集是指，在伴随电路N 中，将节点i 全激励时的节点电压按增序排列起来（如有数值相同的节点电压， 则把它们排在一起） ，这样所得的有序集合称为节点i的节点电压序列，记为Si，并将N中所有的节点电压序列组成的集合称为电路N的节点电压序列集，记为SN = Si ，（ i= 1,2, , n）。图2-3 全激励的伴随电路在图2.4 中节点1 和节点1的节点电压序列分别为： 2 3 4 S1=1.377 81.088 91.622 2 2 3 4 S1=1.377 81.088 91.622 2最后一个定理是：若G与G同构，则它们的伴随电路N与N中的对应节点有相同的节点电压序列， N与N有相同的节点电压序列集，即SN= SN。证明：因为G 与G同构，它们的伴随电路N和N是相同电路，而相同电路对应节点的全激励所产生的节点电压对应相等，于是N与N中的对应节点有相同的节点电压序列，N与N有相同的节点电压序列集，即SN= SN。这一定理是本文将要讨论的算法的基础，是两图同构的又一更为严格的必要条件。若SNSN，则图G与G不同构；若SN= SN，则G与G可能同构。在可能同构的情况下，有两种情况：1. 若SN中没有相同的节点电压序列，则对应顶点全部被确定；2. 若SN中有相同的节点电压序列，则只有这部分节点电压序列的顶点对应关系未被确定。对情况1，按确定的对应顶点重新排列D，如D= D，则G与G同构，否则不同构。对情况2，按确定的对应顶点重新排列D，对部分尚未确定的对应顶点，对D中相应行与列作所有可能的排列并与D作比较，若D = D则G与G同构，否则不同构。假设待判定的任意图G与G满足同构的3 个必要条件：顶点数相同；边数相同；具有相同度数集n的顶点数相同；则因为这3 个条件是非常容易检验的，如不满足，即可判定G G。假设G与G是连通的，因为对不连通的图，可以分别对各连通子图进行判定.设G与G含有n个顶点，b条边，顶点编号分别为1,2, ,n,1,2, ,n。在上述假设下，提出图的同构判定算法如下：第1 步：输入G与G的有关信息，包括顶点编号和邻接矩阵D = D。第2 步：对D的行与列按照顶点度数集相同的数量从少到多进行分组排序。第3 步：构造G与G的伴随电路N 与N。第4 步：从N和N中度数集相同的节点组开始，按第2 步顺序计算各组内以顶点为参考点的节点电压序列，得到该组的节点电压序列集。比较两组节点电压序列集，若它们不能对应相等，可判定两图不同构；若完全对应相等，则检查的该组节点电压序列集中，是否存在某个序列内部的节点电压值各不相等，若存在，将该序列挑出，否则跳至第7步。第5 步：在N的对应组节点电压序列中找出一个与该序列相等的序列，按照序列中的节点电压对应的节点确定顶点与顶点之间的对应关系，参考点互相对应。 例如： 2 3 4 5 6 7 S1=1 2 3 4 5 6 3 5 6 1 4 7 S2=1 2 3 4 5 6则两图中顶点的对应关系为1 - 2，2 - 3，3 - 5，4 - 6，5 - 1，6 - 4，7 - 7。第6 步：依照上一步得到的对应关系，将两图的顶点重新排序，写出新的邻接矩阵，若相等则可判定两图同构，否则两图不同构，结束判断。第7 步：将N中该组节点电压序列集比照N 中对应组中节点电压序列集，得到该组度数集相同顶点的对应关系。第8 步：如果已经解完所有的节点作为参考点的全激励得到的响应，则继续下一步，否则跳回第4步继续解下一组节点电压序列。第9 步：若两个电路的节点电压序列一一对应相等，则依照G 来调整G的顶点顺序，写出新的邻接矩阵，若D= D则两图同构，否则不同构。若两个电路有多个节点电压序列均为相同值，而非一一对应，则调整N电路中度数集相同、节点电压序列相等的顶点的顺序，得到新的邻接矩阵，判断调整后D与D是否相等，若相等则结束判断；若DD则重复这一步直至把所有可能的顺序都判断过，如仍然有DD，则可判断图G与G不同构。例如，若存在两组度数集相同且对应节点电压序列相等的顶点(2,4),(1,3)，则它们可能的对应关系共有两种： (2,1) ,(4,3), (2,3),(4,1)。对于含有自环的图，可以先将自环去掉，用本算法判断剩下的部分是否同构，若不同构则说明原图之间也不同构，若同构且自环位于对应的点上，则两原图依然同构，否则不同构。该算法将电路理论运用于图论中，将电路元件的物理性质与任意图的拓扑结构对应起来，建立了伴随电路，从而确保电路计算的结果能高效的寻找同构任意图的可能的对应顶点.该算法对大多数图是快速有效的。当SN中无相同的节点电压序列时，绝大多数时间是用于解线性方程组，如果图有n个顶点，则节点电压方程的阶数是n 1。伴随电路是线性直流电阻电路，因此节点电压方程是n - 1阶的线性代数方程组，求解该方程组，其时间复杂性为O( n 1)3)。本算法至多需要求解2n个伴随电路，因而时间复杂性至多为O(n(n 1)3) O(n4)。所以在大多数情况下本算法是一个多项式时间复杂性算法。当SN中含有相同的节点电压序列时，只有部分顶点无法确定对应关系，此时仅需调整这部分顶点在D中的排列顺序，所以，在最坏情况下，本算法比盲目交换D中序列的算法也要优越得多。2.3关联度和出入度序列算法n点连通子图的关联度是指：在图G中，与一个n点连通子图G(Vn)相连接的边（不包括G(Vn)的内部边）称为关联边。关联边的边数称为G(Vn)的关联度，记作d(Vn)。例如图2-4(a)中，与3点连通子图G(2, 3, 5)相连接的边有3条：b2，b7，b8，所以G(2, 3, 5)的关联度d(2, 3, 5)= 3 ，同样，与4 点连通子图G(1, 2, 3, 4) 相连的边有2条：b5、b6，所以G(1, 2, 3, 4)的关联度d(1, 2, 3, 4)= 2。特别地，当n点连通子图G(vn)的n = 1，n点连通子图就退化为一个孤立点，此时n点连通子图的关联度就是该点的度数。可见，关联度的概念实际上就是点的度数概念的推广。针对有向图，一个节点的出入度就是指向这个节点和离开这个节点的边的数目。实际上出入度算法和关联度算法除了选取的序列的含义不同，其他计算方法几乎完全相同。以下计算将以关联度为主，很容易类比出出入度算法。图2-4 n点连通子图举例n点连通子图的关联度序列的定义是：若图G的n点连通子图一共有P个，则将这P个n点连通子图的关联度按从大到小的顺序排列起来所得到的有序集合称为n点连通子图的关联度序列，记为S(n)。下面我们以图2-4(a)为例来说明S(n)的概念与求法。求该图的S(3)。图2-4(a)共有5个点，3点连通子图可能的点的组合是：(1, 2, 3)；(1, 2, 4)； (1, 2, 5)；(1, 3, 4)；(1, 3, 5)；(1, 4, 5)；(2, 3, 4)；(2, 3, 5)；(2, 4, 5)；(3, 4, 5)。经考察，组合(1, 4, 5)与(2, 4, 5)不构成3点连通子图，故舍去。分别求出各连通子图的关联度，其结果如下：d (1, 2, 3) = 4，d (1, 2, 4) = 5，d (1, 2, 5) = 5，d (1, 3, 4) = 4d (1, 3, 5) = 6，d (2, 3, 4) = 5，d (2, 3, 5) = 3，d (2, 4, 5) = 5将d ( V3) 按从大到小的顺序排列起来得：S (3) =6, 5, 5, 5, 5, 4, 4, 3，或简记为S (3) =6, 54, 42, 3.顶点合并的定义是：将项点i 与j 重合，并使原接于i的边都连接到j，再消去这一过程中可能出现的自环。这样一个操作，称为顶点i与j合并。例如，我们将图2-4(a)中的顶点5与2合并，先得图2-5(a) 所示的图，再消去自环b5，则得图2-5 (b)所示的合并结果。图2-5顶点合并图示顶点的合并，可以通过对图的关联矩阵的等价操作来完成。图2.5 (a)的关联矩阵为：A= b1b2b3b4b5b6b7b812345 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 如果要将顶点5与2合并，先将A的第5行与第2行执行“环和”运算，即得：A1=5 b1b2b3b4b5b6b7b81234 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 再删去全0 的第5 列（对应于消去自环b5） ，即得：A2= b1b2b3b4b6b7b81234 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 A2正是图2.6(b)所示点5与2合并所得图的关联矩阵。这里的“环和”运算，来自于集合论，其规则为：11=0，10=1，01=1，00=0。可以推论，如果将图中n 个点合并，就是将关联矩阵中这n 个点对应的行执行环和运算，且将全0 的列删去。如果将N点连通子图的n 个点合并， 则一个n点的连通子图就收缩为一个“新点”。显然，这个“新点”的度数就是这个n点连通子图的关联度，例如G(2 ，5） 的关联度d (2,5) = 4，而点5与2合并后，G(2,5)就收缩为新点2，新点2的度数d (2) = 4，显然d (2,5) = d (2)。定理2. 设G1与G2是同构图，如果G1中n个点与G2中n个一一对应，那么这n个点合并后所得的新图G1与G2仍是同构图，且原有的点之间保持一一对应，合并所得的新点之间保持互相对应。证：设图G1、G2的对应点、对应边处在相同的行、列位置上，则G1与G2有相同的关联矩阵，即A1=A2。因为G1中n个点与G2中n个点一一对应，所以这n个点对应着A1、A2中相同的行。而n个点合并即是将这n个点对应的行执行“环和”运算，且删去全0的列。因执行的是相同的运算，所以，运算结果有A1= A2， A1对应着新图G1，A1对应着新图G2 ，所以G1与G2是同构图. 在A1与A2中，原有的对应的行未变，合并后新点对应的行是n 行环和运算产生的新行，所以，对新图G1与G2而言，原有点之间保持一一对应，合并所得新点之间保持互相对应。证毕。定理3. 设G1与G2同构，如果G1中有一个n点连通子图的关联度为d1 ( Vn)，那么，G2中必有一个n点连通子图，其关联度与之相同，即d2 ( Vn) = d1 ( Vn)。证：因为G1与G2同构，所以G2中必有n个点与G1中的n个点一一对应，因为G1中的n个点可构成连通子图，所以G2 中的这n 个点也必定构成连通子图. 根据定理1，这n个点合并以后所得的新图G1与G2是同构的，且合并所得的新点之间保持互相对应。设这二个新图中的新点分别是P1与P2，那么有：d1(P1)=d2(P2)，由前分析知，P1点的度数等于G1中n点连通子图的关联度，即d1(Vn)=d1(P1)，P2点的度数等于G2中n点连通子图的关联度，即d2(Vn)=d2(P2)。所以有d2(Vn)=d1(Vn)。定理4. 如果G1与G2同构，G1与G2的n点连通子图的关联度序列分别为S1(n)与S2(n)，那么对所有的n都有：S1(n)=S2(n)，n=1, 2, , N 1。这里N 是图G1或G2的点数。证：设n=k，k(1, 2, , N - 1)。因为G1与G2同构，G1中K点连通子图的总数应与G2中K点连通子图的总数相同，所以S1(k)中元素的总数应与S2(k)中元素的总数相同。另外，根据定理3，图中的任何一个k连通子图对应着图G2中关联度与之相同的K连通子图，反之亦也一样。这样S1(k)中的元素必与S2(k)中的元素一一对应。最后，由于S1(4) 与S2(k)中元素的排列都是按从大到小的顺序。所以有S1(k)=S2(k)。证毕。下面我们举1个例子。图2-6中的G1与G2实际上是二个同构图，虽然由于它们的点的标号以及画法不同，“形状”显得很不相同。图2-6 两个同构图对图G1，求S1(1)：因d1(1)=4，d1(2)=3，d1(3)=3，d1(4)=2；所以S1(1)=4, 3, 3, 2 。对图G2，求S2(1)：因d2(1)=3，d2(2)=3，d2(3)=2，d2(4)=4；所以S2(1)=4, 3, 3, 2 。比较S1(1)与S2(1)知：S1(1)=S2(1)。对图G1求S1(2)：因d1(1, 2)=5，d1(1, 3)=5，d1(1, 4)=2，d1(2, 3)=2；所以S1(2)= 5, 5, 2, 2 。对图G2求S2(2)：对图d2(1, 2)=2，d2(1, 4)=5，d2(2, 4)=5，d2(3, 4)=2；所以， S2(2)=5, 5, 2, 2。可见： S1(2)=S2(2)对图G1求S1(3)：因d1(1, 2, 3)=2，d2(1, 2, 4)=3，d1(1, 3, 4)=3；所以S1(3)= 3, 3, 2 。对图G2求S2(3)：因d2(1, 2, 4)=2，d2(1, 3, 4)=3，d2(2, 3, 4)=3；所以S2(3)= 3, 3, 2 。可见S1(3)=S2(3) 图2-7 同构判定算法框图这个例子使我们具体看到了定理4的正确性。而且我们还看到，S1(n)和S2(n)与G1与G2的点的标号无关。这一点，将对我们运用定理4判定二个图是否同构带来方便。定理4揭示了不含自环的同构无向图的重要的拓扑性质。(当把自环作了预处理后也保持这样的性质）。我们认为定理4的逆定理也是成立的，即如果两个图G1与G2的n点连通子图的关联度序列都相等，即S1(n)=S2(n)，n=1, 2, N-1，那么，G1与G2同构。因为关联度序列S(n)反映了各个子图层次上的点与边的关系。如果G1与G2在结构上有稍许细微的差别。都将造成某一层次或某些层次的S1(n)S2(n)，这与假定条件相矛盾。定理4及其逆定理可以作为图的同构判据。即如果S1(n)=S2(n)，n=1, 2, ,N- 1，则判定G1=G2，只要有一个S1(n)S2(n)，则立即判定G1G2。据此我们可得图的同构判定算法框图，如图2-7所示。图2-8 两个不同构图下面我们举一例子，试用本算法判定图2-8中G1与G2是否同构。先计算G1与G2的S1(1)与S2(1)： S1(1)= 3, 3, 2, 2, 2, 1, 1 ；S2(1)=3, 3, 2, 2, 2, 1, 1；可见S1(1)=S2(1)。再计算S1(2)与S2(2)：S1(2)=4, 3, 3, 3, 2, 2, 1，S2(2)=3, 3, 3, 3, 2, 2, 2，可见S1(2)S2(2)。判定G1G2。下面估计一下该算法的时间复杂性。该算法的主要步骤是计算点连通子图的关联度S(n)，当n = i 时， i 点连通子图的可能的最大数目为CNi（N为图的点数） ，当n从1变到N-1时，全部连通子图的可能的最大数目为i=1N-1CNi，而i=1N-1CNi2N，可见，利用本算法判定两个图同构，在最坏情况下，其计算时间复杂性仍为指数的，但是，该算法与关联矩阵A 行列交换算法相比较，仍有不少改进。因为那个算法的时间复杂性是N!B! ，N!B! N/eN2NB/eB2B，当N、B较大时，2NN/eN2NB/eB2B。可见，本算法要比行列交换法“好”许多。需要指出的是，利用本算法判定两个图不同构时，所需的计算时间就要少得多。因为我们只要找到S1(k)S2(k)时，就可判定两个图不同构，并不需要计算所有的S(n)。此时连通子图可能的最大数目仅为i=1KCNi，因KN，所以计算时间复杂性要远远低于2N，（与多项式时间复杂性接近）。但是，A的行列交换算法只有完成所有行列交换仍未找到A1=A2时才能判定二个图不同构，其时间复杂性仍为N!B!。因此，本算法在判定二个图不同构时要有效得多。为了使本算法在实际中得到更有效的应用，我们提出进一步改进的方法. 求S(n)是本算法的主要耗时所在. 为此我们不要从n=1开始，依次计算到n=N-1，而是采用“黄金分割优先搜索”的办法，我们把1到(N-1)标于图2-9所示的坐标轴上，我们先计算n=1的S(n)，再计算， n=N-1的S(n)，第3步计算n= 0. 618(N-1)（x为取x的整数） 的S(n)，第4步计算N=0. 6182(N-1)的S(n) ，第5步计算n=0. 618(1-0. 618)(N-1)的S(n)，计算的步骤如图2.9中的、等各黄金分割点所示。每计算一步比较S1(n)和S2(n)是否相等. 在计算了若干黄金分割点（黄金分割点的数目可视N 的大小而定，N大可多选几点）上的S(n)后，如未发现S1(n)S2(n)，则判G1 = G2。（在某一步如发S1(n)S2(n) 则判G1G2）。虽然这种以对黄金分割点的局部搜索代替全面搜索的做法从理论上并不能一定保证所有的S1(n)=S2(n)，但在实际问题如模式识别中，这种做法还是很有效的，它将大大地减少同构判定的计算工作量，而且误判率几乎为0。我们将改进后的算法