（电路与系统专业论文）任意图的同构判定及应用研究.pdf

任意图的同构判定及应用研究摘要 摘要 图的同构判定是图论学科的基本问题之一。所谓图的同构，就是指两个图的 拓扑结构完全相同。从定义看这个问题似乎并不复杂，但它却是一个世界性难题， 多数学者将其归为n p 完全问题。 本文从图邻接矩阵的特征系统这一角度入手，提出了针对任意图同构的判定 算法。在构建有效描述任意图邻接矩阵的基础上，分别计算两个矩阵的特征值所 对应的特征向量，并依据它们的极大无关组寻找可能的同构对应关系。通过对全 体特征值的逐一考察，实现图同构的判定并确定同构图的顶点对应关系。 文中详细介绍了算法和相关应用，完成的工作包括： 1 ) 对已发表文章中提出的同构算法进行了回顾，并指明存在的不足； 对与算法相关的新概念进行了阐述，主要包括：图的预处理、描述任意 图的邻接矩阵、权度序列、特征值序列、同序向量组和关系矩阵等。 对算法涉及的性质和定理进行了详细证明； 4 ) 提出了任意图的同构判定算法：特征向量法。文中给出详细的算法描述 同时，将本文算法与部分发表文献中方法进行了判定性能对比。 5 ) 将算法应用于电路、化学、机械等领域中，实现算法理论价值与应用价 值的结合。 大量同构判定实验表明，随着判定规模增大及图对称性增强，特征向量法与 已有一些方法相比，具有更高的同构判定效率，并且证实多数情况下此方法是快 捷有效的。 关键词：任意图；同构；邻接矩阵；特征向量 中图分类号：0 1 5 7 6 任意图的同构判定及应用研究 a b s t r a c t t h ei d e n t i f i c a t i o no fg r a p h s i s o m o r p h i s mi so n eo ft h eb a s i cp r o b l e m si ng r a p h t h e o r y i s o m o r p h i s m ，i nb f i e lm e a n st w og r a p h sp o s s e s si d e n t i c a lt o p o l o g i c a l s t r u c t u r e s t h o u g ht h ep r o b l e mi ss e e m i n g l ys i m p l eb yd e f i n i t i o n , a sa m a t t e ro ff a c t , i ti saw o r l d - d a s sd i f f i c u l tp r o b l e ma n dc h s s f f i e da sa l ln - p - c o m p l e t ep r o b l e mb y m o s te x p e r t s i nt h i sp a p e r , w et r yt oa p p r o a c ht h ep r o b l e mv i at h ee i g e n - s y s t e mo fag r a p h s a d j a c e n c ym a t r i xa n dp r o p o s eam e t h o da i m i n ga tt e s t i n gi s o m o r p h i s mo fa r b i t r a r y g r a p h s w i t ht h ec o n s t r u c t i o no fa d j a c e n c ym a t r i c e st h a tc a ne f f e c t i v e l yd e s c r h ，ea n a r b i t r a r yt o p o l o g i c a lg r a p h , t h ee i g e n v e c t o 鹧o ft h es a m ee i g e n v a l u e o ft h et w o m a t r i c e sa g ec a 】蛔l a l c dr e s p e c t i v e l ya n dt h ep o s s i b l ei s o m o r p h i cc o r r e s p o n d e n c e sa r e e s t a b l i s h e do nt h eb a s i so ft h e i rm a x i m u mi m p e r t i n e n tg r o u p s a f t e ra l lt h e e i g e n v a h e s h a v e b e e n c o n s i d e r e d , i s o m o r p h i s m w i l lb ed e t c r m i n e da n d c o 玎e s p o n d e n c eo f v e r t i c e si ni s o m o r p h i cg r a p h sc a nb eu l t i m a t e l yi d e n t i f i e d w ef o c u su p o nt h ed e t a i l so ft h ea l g o r i t h ma n di t sr e l a t e da p p f i c a t i o n si nt h e p a p e r t h em a i nw o r kc o m p l e t e d i n c l u d e s ： 1 ) a b r i e f r e v i e w o f t h e p u b l i s h e d m e t h o d s i n t h i s f i e l d a n d t h e i rs h o r t c o m i n g s ； i l l u m i n a t i o n so i lt h en e w l y - i n t r o d u c , e dc o n c e p t si nt h ea l g o r i t h m ，i n c l u d i n g t h ep r e t r e a t m e n to fg r a p h s ，a d j a c e n c ym a t r i xf o ra r b i t r a r yg r a p h s , w e i g h t e d d e g r e es e q u e n c e ，e i g e n v a l u es e q u e n c e , v e c t o rg r o u p sw i t ht h e i d e n t i c a lo r d e g r e l a t i o nm a t r i xe t c ， d e t a i l e dp r o o f so ft h ea l g o r i t h m - r e l a t e dp r o p e r t i e sa n dt h e o r e m s 钔t h ep r o p o s i t i o no ft h en e wa l g o r i t h m e i g e n v e c t o r - b a s e dm e t h o da n dt h e c o m p a r i s o no fp e r f o r m a n c e sa m o n g s e v e r a lp u b n s h c dm e t h o d s 鼬t h ea p p h c a t i o no ft h ea l g o r i t h mi ns e v e r a lf i e l d s ：c i r c u i t r y ，m e c h a n i c s ， c h e m i s t r ya n ds oo n , r e a l i z i n gt h ec o m b i n a t i o no ft h et h e o r e t i c a l a n d p r a c t i c a lv a l u e so ft h ea l g o r i t h m n u m e r o u si s o m o r p h i s mt e s t ss h o wt h a t ，w i t ht h es c a l ea n ds y m m e t r yo fg r a p h s i n c r e a s i n g , t h i sm e t h o de n j o y sa d v a n t a g e s i n e f f i c i e n c yc o m p a r e dw i t h s o m e p r o p o s e dm e t h o d s i th a sb e e ne x p e r i m e n t a l l yv e r i f i e dt ob ee f f i c i e n ta n de f f e c t i v ei n m o s tc a s e s k e yw o r d s ：a r b i t r a r yg r a p h s ；i s o m o r p h i s m ；a d j a c e n c ym a t r i x ；e i g e n v e c t o r c l a s s i f i c a t i o nc o d e ：0 1 5 7 6 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：盛盘日期：兰! 皇! ：三：鸷 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：盛盘导师签名日期：兰里= ：矽 任意图的同构判定及应用研究 引言 引言 本文研究的图是一种具有高度抽象和概括的图形，简单地说就是一些点以及 把这些点在适当地方连接起来得到的拓扑结构。图论正是研究这些图性质与应用 的学科。从1 7 3 6 年欧拉针对著名的七桥问题发表的论文 ，其中： v 一乃称为g 的顶点集，其元素称为图的顶点； e 称为边集，它是无序积v x v 的多重子集，其元素称为无向边； 无向边0 ，v ) 与连接顶点口，v 相关联，称u ，v 相邻接。 ( 2 ) 有向图 有向图( 图1 - 1 c o ) ) g 是一个有序二元组t y ，e ，其中： v a 称为g 的顶点集，其元素称为图的顶点； e 称为边集，它是有序积v x v 的多重子集，其元素称为有向边； 有向边t u ，与连接顶点1 1 ， ，相关联，称u 相邻接 ，且u 、 ，分别称为边的 起始顶点和终止顶点，用箭头表示有向边的方向。 ( 3 ) 混合图 (1)(2) e l ( 4 )( 3 ) ( a ) o ) ( c ) 图1 - 1 无向图，有向图和混合图 混合图( 图1 - 1 ( c ) ) 实际上是有向图与无向图的结合，图中的边可有向亦可无 3 任意图的同构判定及应用研究 第一章图和同构的基本概念 向。任意混合图均可分解为一个无向子图和有向子图，可见无向图和有向图均是 混合图的特例。图除了按边有无方向分类，还可按是否携带权值划分为含权图和 无权图。需要指出的是本文后面讨论的无向、有向以及混合图的边可含权可无权。 2 按图连通与否划分 定义1 - 2 路图g - ， v o ，v l ，v c v ， e o ，巳，e c e ，且岛是关 联q 。与q 的边a 称交替序列，e l ，1 , 1 ，e 2 ，巳，匕为联结v o 到v 的路。 根据图任意两点问路的存在性可以把图分为连通图与不连通图。在不连通图 中，利用连通这个等价关系可以把顶点集分划为若干个子集，每个子集内部的顶 点间都是连通的，而处在不同集合的顶点间必不连通。显然，每个集合对应着一 个连通子图，称它们为图的连通分支或连通片。 图1 2 就是一个连通图( 图1 - 2 ( a ) ) 与不连通图( 图1 - 2 0 , ) ) 的例子，可以看到不 连通图共有两个连通片。 1 2 2 自环，平行边和简单图 图1 - 2 连通图和非连通圈 1 自环 只关联一个顶点的边叫作自环，它既可以看作无向边又可以看作有向边，所 以规定它的方向是没有意义的。本文涉及的自环均不带方向。 2平行边 图论中的边集合元素允许冗余，即元素具有重复性。这样就会出现多条边同 时联结同一对顶点的情况。无向图中，这样的重边就叫做平行边；有向图中，只 有当这些边具有相同的起始顶点和终止顶点时才叫做平行边。 3简单图 ( 3 ) 图1 3 非简单图 4 任意图的周构判定及应用研究 第一章图和同构的基本概念 一个没有自环也没有平行边的图称为简单图，图1 - 1 所示的三幅图均为简单 图。而图1 - 3 所示的图由于顶点h 与屹、匕与屹间均连有平行边，顶点k 上还带 有白环，所以它不是简单图。 1 2 3 顶点的度 这个概念的阐述需要从无向图和有向图两种情况展开。 在无向图g v ，e ，中，我们把与顶点 ，相关联的边的数目称为顶点 ，的度。 在有向图g v ，e ，中，我们把与顶点，相关联的边中该点作为起始顶点的 边的数目称为顶点v 的出度，而作为终止顶点的边的数目称为顶点的入度。 以图1 - 1 ( a ) 所示无向图为例，四个顶点度数依次为； d e g ( v 1 ) - 3 ，d e g ( v 2 ) 一2 ，d c g ( v 3 ) 一3 ，d e g ( v 4 ) 一2 ； 以图1 1 嘞所示有向图为例，四个顶点度数依次为： 出度：d e g + 以) - 1 ，d e g + ( v 2 ) 一1 ，d e g + 他) - 2 ，d e g + “) - 1 ； 入度：d e g 一“) 一2 ，d e g 一( v 2 ) 一1 ，d e g 一心) - 1 ，d e g 一( v j - 1 ； 上述关于度的概念是图论给出的最基本定义，但这样定义的度不适合混合 图，而且不能携带含权边权值的信息，我们在第二章将对概念进行拓展。下面介 绍一下图的矩阵表示所涉及的基本概念。 1 2 4 图的矩阵表示 1关联矩阵 图g - 中，v - v o ，h ，v j ，e 一 e o ，e 1 ， ，定义它的关联矩阵m 。 同样要从有向图和无向图两种情况着手。 无向不含自环的图的关联矩阵肼的元素所。定义为： n h 关联p ， 。t 0 呖关妊， 有向不含自环的图的关联矩阵膨的元素定义为： f 1k 是e i 的起始顶点 一 - 1q 是p f 的终止顶点 1 0 h 与p ，不关联 以图1 - 1 ( a ) ， 所示图为例，得到的无向图和有向图的关联矩阵分别为： m a - 10011 110 0 o 0l1o1 0 011o m b - 1o 一11 01 0o o一11 00o 101 110 5 任意图的同构判定及应用研究 第一章图和同构的基本概念 易见，对于连通图，r a n k ( m ) - n 一1 ；对于不连通图，r a n k ( m ) - n w ，其 中w 为不连通图连通片的数目。当研究的图为连通图时，从前面构造的关联矩阵 中任意划去一行并不会影响图形信息的表达，因为图的秩表明此行是冗余的。 关联矩阵在表征重边方面有着独特优势，而且只要把有向图和无向图关联矩 阵的定义综合起来，就可以得到混合图关联矩阵的定义。但是，它无法描述含权 边和双端点重合的自环边且一般情况下关联矩阵不是方阵，这就在一定程度上限 制了其描述图的范围和应用。 2邻接矩阵 图g - t 矿，e ，为简单图，v - ，h ，屹) 的邻接矩阵4 。的元素定义为： r 1 v i 邻接y ， 嘞。1 0f ，或不邻接， 仍以图1 1 ( a ) 又b ) 所示图为例，得到的无向图和有向图的关联矩阵分别为： 4 - o1 1o 11 1o 11 10 01 10 4 - 01 0 0 1o 10 0 0 10 o1 o o 可以看到，这样得到的无向图邻接矩阵是对称的，但有向图邻接矩阵是非对 称的，且上述定义不适合表达含权边、重边( 包括平行边) 以及混合图。不过与 关联矩阵相比，邻接矩阵可以表达自环且成为方阵，这就使它具有一些关联矩阵 所不具备的重要性质。 关联矩阵与邻接矩阵在表达图形信息上各有利弊，但是它们在各自能及的范 围内都可以把图以矩阵形式有效表示出来，即根据图可列写唯一的矩阵，且根据 矩阵可画出唯一的拓扑图。本文重点关注邻接矩阵，在第二章中我们将会对邻接 矩阵定义进行修改和扩充，克服前面指出的邻接矩阵现有定义的缺憾。 1 3 同构的基本概念 ( 1 )( 2 )( 1 ) 回国 g ( 3 )( 4 )( 3 )( 6 ) g 图1 - 4 同构定义示意图 6 任意图的同构判定及应用研究第一章圈和同构的基本概念 我们研究的图是一种数学抽象，在讨论图时连线的长度、形状和点的位置往 往无关紧要，也就是说真正区分不同图即能够作为图身份表征的应该是拓扑结 构。这就要涉及图中顶点和顶点连接情况，也就引出了与图拓扑结构紧密联系的 概念同构。 先给出关于同构的一个直观定义：同构是指两图的拓扑结构完全相同，即它 们的邻接矩阵相同。能够正确识别图的拓扑特征是成功进行同构判定的关键。 根据定义，图1 4 中图g 和g 显然具有相同拓扑结构且对应邻接矩阵均为： 1234 5 6 7 8 1o 010 o 0 010 o10 o lo1o01o o1o o oo1 0 0 o o1o1 10 01010 010 o101 o o11o1o 所以可以得出g g 的结论。但是在多数情况下，待判定的拓扑图并不会那 样明显地将重要的拓扑信息呈现出来。比如图g 和g ”，按照上图编号写出g ”的 邻接矩阵，发现这两幅图实际上是同构的，但是从直观角度似乎很难迅速确定两 幅图问的同构关系，所以仅凭借前面的定义很难对一般图进行同构判定。可见， 我们需要对同构的定义和内涵的理解进行深化，这些工作将在第二章进行。 图1 - 52 度点内同构图 在同构研究中，有一种情况颇值得一提，那就是二度点内同构。原本不同构 的两图通过去除2 度点或把两条接续边视为一条边，这样两图就同构了。图1 5 就是两个2 度结点内同构图。借助这种同构概念，并依据库拉杜夫斯基定理【“， 我们就可以实现平面图的判定。 本文着重探讨的常规意义的同构，不过2 度点内同构的研究可以成为下面进 一步探索的方向。 7 任意图的同构判定及应用研究第一章图和同构的基本概念 1 4 图的不变量与同构的关系 一个与图相关的参量如果满足对于任意与该图同构的图，该参量的值均相 同，则此参量值称为图的一个不变量。而“不变量完全集”是可以完全确定一个 图同构的不交量组。我们之所以要给不变量完全集加上引号，表示它目前还只存 在于一种期望状态，相关的探索还在进行中。纵观其发展过程，可以看到对一般 的图寻求能完整表征同构的不变量完全集是一件非常困难的事情。 曾经有人提出这样一组“不变量完全组- a ”【1 4 1 ： ( 1 ) 图的顶点数； ( 2 ) 图的边数； ( 3 ) 度数相同的顶点数目( 在有向图中入度、出度相同的顶点数目) 但是实际上这三个参量只能够作为图的不变量，不足以构成不变量完全组， 图1 - 6 所示的异构图能够说明这个问题。 g 和g 均具有5 个顶点；均含有7 条普通边和1 个自环；两图的顶点度数 分别为：【3 2 4 43 】，【42 43 3 】，可见度数为2 的点均有1 个，度数 为3 的点均为2 个，度数为4 的点也均为2 个，上述“不变量完全组”要求达到。 ( 1 )( r ) ( 5 ) gg 图1 - 6 满足。不变量完全组- a ”条件的异构图 但若两图同构且以白环所在顶点为标志，屹和k 必为同构对应点，则与它 们相邻接的顶点中，度数相同点的数目应该相同。图g 中与k 相邻接的顶点和 h 的度数为2 和4 ，图g 中与b 相邻接的顶点心和k ，的度数为2 和3 ，与前面 结论矛盾，所以两图异构。可见，“不变量完全组a ”只是真正完全组的子集。 还有人提出引入邻接矩阵的特征值，得到“不变量完全组- b ”。这样似乎使 得“完全组”更加完备，但是图1 7 所示的图嘲将否定这个观点。 g 和g 均具有1 5 个顶点，均含有2 7 条普通边，两图的顶点中度数为2 的 点均为6 个，度数为4 的点均为6 个，度数为6 的点也均为3 个，它们拥有相同 的特征值。但是可以看到g 中同时关联两条2 度点所在边的顶点为k ，v ，v 6 ，g 中是心，屿，。如果两图同构则g 中的心，屹，的同构对应点必在g 中的 h ，屹，屹中产生。 8 任意图的同构判定及应用研究 第一章图和同构的基本概念 z g 图1 7 满足。不变量完全组b ”条件的异构图 g 圈1 8 心，k ，屹t ，v 6 的邻按圈 考察顶点屹，我们把它放置在一个圆的圆心上，在不让g 的边发生交叠的情 况下( 本例中只要边不发生交叠，n 相邻接的点的相对位置是确定的，顺逆时 针没有区别) ，按照顺( 逆) 时针顺序把图中与它邻接的点排列在圆周上且括号内 数字为顶点度数，于是得到以k 为圆心的邻接圆。同理得到以，v 5 ，为圆心的 邻接圆( 图1 8 ) 。 若g 与g 同构，则以u 为圆心的邻接圆至少应与以k ，吃，为圆心的邻接 圆中的一个相同( 这里所谓相同指圆周上权值相同且分布相对位置一样，顺，逆时 针并不影响) 。但实际上，以为圆心的邻接圆中，度数为2 的两点处于对位， 而以屹，k ，k 为圆心的邻接圆中度数为2 的两点均处于间位，这就与前面结论矛 盾，故两图异构。 最终，我们得到引入相同特征值这个条件的“不变量完全组b ”并不是真正 完全组的结论，即它不能作为同构判定的依据。 9 任意图的同构判定及应用研究第一章图和同构的基本概念 1 5 同构判定算法的进展 “不变量完全组”的尝试在同构判定中尚未取得成功，于是人们开始探询新 的同构判定方法。通过长时间的研究，目前已经提出了一些颇具有创新性的方法， 并在一些判定实验中取得了成功。本节主要对这些方法中具有代表性的进行介 绍。在讨论这些方法前，我们先介绍同构判定中存在着的一种原始方法，它是新 方法提出的基础。 1 5 1 顶点置换法 对于含有n 个顶点的拓扑图g 和g t ，要确定两图的同构关系，可以通过对g 的顶点编号进行若干次交换，每交换完一次分别列写两图的邻接矩阵a 和一- ， 并进行比较，相同则说明两图同构，否则继续进行交换，直到g - 中玎个顶点编 号全部可能交换都尝试过得出异构结论为止。每进行一次项点交换，实际上是对 邻接矩阵中两个顶点对应的行( 列) 进行交换，也就是完成了一次置换操作。为了 保证算法的效率，每经过一次顶点编号交换后产生的顶点新编号要互不相同。 这种方法拥有很好的准确率，同时只要对邻接矩阵定义稍加扩充，便可以实 现任意图的同构判定。但是采用此方法，同构判定的最坏情况和异构的判定均需 要进行厅! 次比较。顶点数目不大时；采用这种方法还是可行的，但是当图的规模 超过一定数量时，这种方法将不宜采用。导致这种算法效率低下的根本原因正是 顶点交换时的盲目性。 文献【1 6 】中提出了旨在降低顶点置换规模的改进型顶点置换法。具体规则 是：先依据顶点的度数进行分类即将度数相同的顶点归到同一组中，这样就可以 得到k 个分组，且第l o z 七) 组中包珥个顶点；然后在组内进行顶点交换，并 列写邻接矩阵进行比较。通过这样的改进，我们发现顶点交换规模从撑! 降至 i 兀“! ) 。虽然运算规模的确有所降低，但顶点交换的盲目性问题只是得到初步 ，0 缓解，并无实质性改观。不过，置换法的思想是非常重要的并且它为新算法的探 索和提出指明了方向降低顶点交换的盲目性和规模。 1 5 2 基于h o p f i e l d 神经网络的算法 基于神经网络的神经优化是一种能够模拟局部功能的超大规模并行运算。 1 9 8 5 年，h o p f i e l d 和t a n k 率先把h o p f i e l d 神经网络l ”。1 8 1 应用于n p 完全问题的 研究并取得喜人成果，而把h o p f i e l d 神经网络应用于同构判定的研究则始于马颂 德眇】，陈国良 ”- 2 q 等人。 任意图的同构判定及应用研究第一章图和同构的基本概念 h o p f i e l d 神经网络同构判定算法的基本思路是：对含有斗个顶点的简单拓扑 图g 和g - 构造一个含有 x 斗个神经元的网络并引入一个能量函数。运行该网络， 采用梯度法等方法对能量函数进行优化，促使其能量值趋向最小。通过不断迭代， 使得网络运行到平衡状态，保证网络进入到希望的吸引子中，得出判定结论。整 个算法运行的过程中，需要构造由约束项和惩罚项组成的能量函数且指定迭代步 长，这两个要件的选择会决定算法成败。 通过一些大规模同构判定的实验，基于h o p f i e l d 神经网络同构判定算法取得 了让人满意的结果。算法在获得正确的同构判定结论的同时，其时间耗费也是比 较低的，许多学者对这种新颖的判定方法给予关注。 但是，这种方法自身也存在着不足之处： 1 ) 算法是通过不断迭代使得能量函数趋于最优的，所以步长的选择就直接 影响到算法的运行速度与网络收敛速度。通过实验表明，如果取得过小或过大， 都会使得网络运行到希望吸引子的时间过长甚至引起发散。所以每次判定，都需 要在步长的选择上进行探索。 劲当网络进入到平稳态时，并不能立即作出结论。因为采用梯度法来优化 能量函数极有可能使网络运行到局部极小值点。如果发生这种情况，则需重新指 定参量的初值并重新运行网络，那么运行时间就势必会延长。要解决这个问题， 就要在能量函数的选取上以及参量初始值的选择上进行研究，使算法在运行中尽 可能避开局部最小值点。 后来的学者进一步探索步长选择的规律，对原基于h o p f i e l d 神经网络同构判 定算法进行了改进，工作集中在能量函数的构造以及减少确定进入局部最小点的 时间以迅速进行下次全新迭代上。但算法本身的收敛性和步长的制约依旧是影响 性能的瓶颈，并没得到彻底的解决。 1 5 3 基于图的图论特征的算法：关联度序列，出入度序列和度序列法 图顶点的度是图的一个基本特征。这一节介绍的三种算法均围绕着图各顶点 的度展开且均是基于判定图的关联矩阵进行处理的。 1关联度序列法【矧 在阐述这种方法之前，我们先介绍一些与算法相关的概念。 ( 1 ) k 点连通子图如果含有n 个顶点的图g 中七( 1 s k 皇甩) 个点以及连接于 这k 个点之间的边组成的子图是连通的，那么这个子图称为图g 的k 点连通子 图，记为g ( k ) ( k 是这k 个点的集合) 。 ( 2 ) k 点连通子图的关联度图g 中，与一七点连通子图g 以) 相连接的边( 不 包括g ( k ) 内部边) 称为关联边。关联边的数目称为g ( k ) 的关联度，记作d ( k ) 。 1 1 任意图的同构判定及应用研究第一章图和同构的基本概念 ( 3 ) k 点连通子图的关联度序列若图g 的k 点连通子图一共有p 个，则将这 p 个七点连通子图的关联度按从小到大的顺序排列起来所得到的有序集合称为 k 点连通子图的关联度序列，记为s ( k 1 。 ( 1 )( 1 ) ( 3 ) 2 ) ( 3 ) a )3 ) ( a ) gg ( 2 ，3 )( c ) g q 3 ) 图1 - 93 点无向拓扑图和它的全部2 点连通子图 l i l l - 9 ( a ) 所示的3 点拓扑图中，我们列出所有2 点连通子图0 - 9 0 ) ，( c ) ，( d ) ) 。可 见d 亿3 ) - 3 ，a 0 , 3 ) - 3 ，d 仉2 ) 一2 且s ( 2 ) - 1 2 ，3 ，3 】。 这种算法主要依据：弹点图g 和g 同构等价于s ( k ) - s 馋5 k n ) ，所以 整个算法主要就是执行k 点连通子图的关联度序列的计算与比较。如果某个k 点 连通子图关联度序列s 忙) 一s 协) ，那么两图就不同构。 它简单明了，特别对异构图判别尤为适宜。不过从计算量来看，对于一点同 构图判定，需要计算 个关联度序列，而且还要找出所有k o s k 量雄) 点连通子图， 颇有一番r 计算量。针对此点，在原基础上引入黄金分割搜索法。算法依次计算 s ( 1 ) ，s ( - 0 ，s ( 【o 6 1 8 ( n 一1 ) 】) ，s ( 【o 6 1 8 2 ( 一1 ) 1 ) ，s ( 【o 6 1 8 ( 1 - 0 6 1 s x n 一1 ) 】) ( i x l 是对变量x 取整) ，这里可取为适当大且比顶点数目小的整数。改进后， 待计算的序列对应子图的顶点数仅限于小于的黄金分割点，运算量大为降低。 2 出入度序列法瞄1 关联度序列法是针对无向图同构判别的，而出入度序列法可以看作是关联度 序列法的思想在有向图同构判定中的延伸。 在出入度序列法中，同样定义有k 点连通子图这个概念，其定义与关联度序 列法相同。但是由于有向图中，边携带方向，所以顶点度的定义就要分为入度和 出度，相应就产生k 点连通子图的出入度和k 点连通子图的出入度序列的概念。 ( 1 ) k 点连通子图同前面同名概念的定义； ( 2 ) k 点连通子图的出入度图g 中，g ( k ) 的关联边中指向这个子图的边称 为入边，入边的数目称为g ( k ) 的入度，记作成以) ；关联边中离开这个子图的 边称为出边，出边的数目称为g 以) 的出度，记作d 。以) 。 ( 3 ) k 点连通子图的出入度序列若图g 的k 点连通子图一共有p 个，则将这 p 个k 点连通子图的入度按从小到大的顺序排列起来所得到的有序集合称为k 点连通子图的入度序列，记为s 仕) ；把连通子图的出度按从d , n 大的顺序排列 任意图的同构判定及应用研究第一章图和同构的基本概念 ( 3 )2 ) - - (3)(2) ( 鑫) gg ( 2 ，3 )( c ) g 仉3 )( d ) g g 2 ) 图1 1 03 点有向拓扑圈和它的全部2 点连通子图 起来所得到的有序集合称为七点连通子图的出度序列，记为墨 ) 。 图1 - l o ( a ) 所示的3 点拓扑图中，我们列出所有2 点连通子图( 1 - 1 0 0 , ) ，( c ) ，( d ) ) ， 可见哦亿3 ) - 2 ，哦b 3 ) - 1 ，d i g2 ) - 1 ；d o 亿3 ) - 1 ，以q 3 ) 一2 ，d o “2 ) - 1 ； 且墨( 2 ) 一b 1 , 2 】，s o ( 2 ) - 鸭1 , 2 】。 此算法主要依据：t 点图g 和g 同构等价于墨 ) i 墨职) 且 & ) - s o 耻x l s 七蚪) ，故算法实质是执行k 点连通子图的出入度序列的计算与 比较。若某k 点连通子图关联度序列墨 ) - 墨耻) 或疋 ) 一s o 协) ，则两图异构。 3 度序列法i 驯 度序列法综合了关联度序列法和出入度序列法的思想，它对连通子图度的定 义进行了推广，实现了对混合图的同构判定，这样判定图的边可以有向亦可无向， 相应就产生k 点连通子图的度和k 点连通子图的度序列的概念。 ( 1 ) 七点连通子图同前面同名概念的定义； ( 2 ) k 点连通予图的度对图g 中的一个g 以) ，构造一三维空间且记存在于 此空间的向量d 以) - d i i + d 2 j + d 3 k ，其中分量噍表示g ( k ) 关联边中无向边的数 目，如表示关联边中出边的数目，以表示关联边中入边的数目a d ( k ) 称为g 以) 的度，它含括了关联度和出入度。 ( 3 ) 七点连通子图的度序列首先定义向量组的升序排列：向量组的元素均 为向量，将元素先按f 分量大小升序排列，再对i 分量大小相同的元素按j 分量大 小升序排列，最后对f 分量大小相同的元素按k 轴分量大小升序排列，即得向量 组的升序排列。若图g 的七点连通子图共p 个，则把由这些p 点连通子图的度组 成向量组的升序排列称为k 点连通子图的度序列，记为s 僻) 。 图1 - 1 1 ( a ) 所示的3 点拓扑图中，我们列出所有2 点连通子图( 1 1 1 ( b ) ，( c ) ，( d ) ) ， 贝d ( 2 ，3 ) 一i + ，+ 七，d ( l 3 ) 。2 i + j ，d o , 2 ) 一i + 七且s ( 2 ) - p + 七，i + ，+ 七，2 f + ，】a 这种算法主要依据：痒点图g 和g 同构等价于s ( 七) 一s 协x 1 i 七一) ，所以整个 算法主要就是执行k 点连通子图的度序列的计算与比较。如果某个k 点连通子图 度序列s 僻) 一s y 七) ，那么两图就不同构。 关联度序列法、出入度序列法和度序列法虽然处理不同类型的图，但思想是 八u 任意图的同构判定及应用研究第一章圉和同构的基本概念 (3)(2) - - - - _ (3)(2) ( 1 ) ( 1 ) ( 丑) gg ( 2 ，3 )( c ) g g 3 )( d ) g 仉2 ) 图1 - 1 13 点混合拓扑图和它的全部2 点连通子圈 相似的，即同构同序列。它们在判定速度上是具有明显优势的，运算时问复杂度 为d ( z ) ，远小于关联阵置换法的复杂度疗 61 ( 6 为边的数目) 。但这些算法作出 同构的结论时，并不能够明确给出一种顶点对应情况且同构判定判据的充分性还 需进一步考察和研究。另外，即便是三种方法中处理图范围最广的度序列法也只 能处理无权图，所以需要进一步对算法进行研究并对其进行拓广。 1 5 4 基于图的二维子图匹配的算法：v f 算法 v 】 算法是l e c o r d e l l a 等人于1 9 9 6 年提出的一种通用匹配算法1 4 堋，采用了 深度优先遍历算法思想，用于解决图的同构与子图匹配问题。算法中提出了了状 态空间( s s r ) 的概念：状态空间是由目前匹配成功的s q g 与t g 的点构成的顶点 对组成的，用以表明当前含有m 个顶点的提问图( q g ) 与含有厅伽s 露) 个顶点的目 标图f r 固间的顶点匹配情况。在算法处理过程中，状态空间的元素不断更新。 算法的基本思想是：在0 ( 3 取出一点，并在t g 中挑出一个未访问过的顶 点，使得它们相互匹配。如果这样的点没有找到，则回溯到上一顶点；如果找到， 则把新的顶点对加入已有的状态空间中，对状态空间进行扩充。当q g 的所个顶 点均出现在状态空问时说明两图匹配成功；当回溯n q g 的第一个顶点，而在t g 中找不到匹配点时，说明两图不匹配。 该算法可能需要深度遍历所有可能的s s r 才能得出结果，而遍历所有的s s r 需要极大的时间开销，这就使得对于规模大的问题，算法性能下降。 1 5 5 基于等效模拟的算法：电路模拟法 这类等效模拟的方法摆脱了传统就图论图的方法，而是采用了等效转化的思 想，将原本属于图论学科的同构判定问题转换为其它领域相对容易处理的问题。 电路模拟法 2 7 - 2 * 1 就是其中的代表。 这种方法主要为待判定的拓扑图构造对应的电路模型，通过施加激励，获得 节点电压值实现同构的判定。文 2 7 r 能处理无权无向图，而文【2 8 】发展了【2 7 】 1 4 任意图的同构判定及应用研究第一章图和同构的基本概念 的思想，已经被成功地把判定范围拓展到任意拓扑图，是一种不可多得的“全能” 方法。下面介绍几个算法相关的重要概念： i a l 3 s ( 3 ) 圈1 - 1 2 拓扑圈和它对应的伴随电璐 ( 1 ) 伴随电路对含有辟个顶点的图g 可按照下面规则构造含有万个节点的 伴随电路：顶点七，间若连有权值为w 的无向边，则在伴随电路具有相同编号的 节点间连入一个导纳为w 的电导；顶点k ，f 间若连有权值为w 的有向边，则在伴 随电路具有相同编号的节点间连入一个导纳为w 的电导并在两个节点间连入一 个大小为叫的电流源，它的方向与有向边相同。图1 1 2 为一示例。 ( 2 ) 全激励对伴随电路某一点的全激励定义为以此点为参考点，同时在该 点与其宜节点问连入大小为的电流源，方向均由参考节点指向其它节点。图 1 1 3 为上面得到的伴随电路对节点3 的全激励。 l ql 圈1 - 1 3 圈1 - 1 2 拓扑图对应的伴随电路对节点3 的全激励 该算法的主要思想就是通过对拓扑图构造对应的伴随电路，然后对每个节点 分别进行全激励。对每次激励得到的栉一1 个节点电压升序排列，得到该节点对应 的节点电压序列，并组成节点电压序列集。算法首先为待判定的图构造对应节点 电压序列集，然后通过对两序列集元素进行比较寻找同构对应关系。如果两元素 集存在无法对应的元素，则不同构。若相同，则把节点电压序列相同的点进行归 类，然后在同类点的内部进行全排列最终实现同构判定。 一般情况下，在同构判定中部分顶点的排列是在所难免的，但是与顶点置换 任意图的同构判定及应用研究 第一章图和同构的基本概念 法相比，这种方法已经使得排列的规模降低很多，减轻了顶点排列的盲目性。特 别对某些图，存在节点电压序列各元素互不相同的情况，这种情况下此方法可以 迅速作出结论。 但是，对于对称性强尤其是各点电压序列都相同的图，这种方法的效率将非 常低下。为此，在上述情况发生时引入了相对位序表的概念，依据电压序列中电 压的大小进行再次分类，并在判定效率上取得进展。 通过实验看到，随着图规模的增大和对称性增强，构造伴随电路和解电路节 点电压序列的时间开销( 时间复杂度o c n 4 ) ) 的增大连同相对位序表改善作用的 有限性均使得算法对规模大尤其是对称性强的图，同构判定耗时较长，性能不尽 如人意。另外，构造描述任意拓扑图的邻接矩阵时，采用的是三维矩阵，这就使 得图规模增大和复杂性增强时，矩阵的构造将成为一件非常麻烦的事情。 通过以上对算法的论述，可以看到这些方法处理问题的思考角度和切入点互 不相同，而且图的处理范围更是因法而异。它们在判定中体现着各自的优势的同 时，也表现出各自不足且还面对着一个共同的问题：随着规模的增大，一种方法 终有其失效的时候，这也正是同构问题是n p - 完全问题的一个体现。虽然不能完 全解决这个问题，但是可以肯定的是通过对现有方法进行改良或提出新的方法， 实现在现有基础上判定图范围的扩大和判定规模的增大是可能的，这一点也正是 指引我们提出本文算法的依据； 1 6 任意图的同构判定及应用研究 第二章图的同构 2 1 概述 第二章图的同构 引言部分介绍了图论中关于图的基本概念并对同构给出直观解释，本章在此 基础上给出图同构的标准定义，并对概念进一步深化到邻接矩阵置换的层次，这 种对原始概念的深入为本文算法的提出奠定了基础。另外，在本章的后半部分， 我们着重介绍与本文提出的同构判定算法；特征向量法相关的概念，并通过举例 降低概念的抽象性。 2 2 图的同构 设图g 与g t 的顶点集为y 与矿，边集为e 与e - ，则 定义2 1 图的同构“”4 捌若在v 与v 之间存在双射函数，使e 与f 。之问 对一切“，v v ，若帆v ) e ( 球， e e ) ，则必有o ：v e ( “： ， e i e ) ， 且在各自的图中有相同的重数；若o ，y ) 芒( t “，1 ，罐e ) ，则必有 ：p 岳e ( “：，e ) ，则图g 与g 同构，记作g _ g 。 上述图论中给出的严格定义还可以表述为：如果图g 与g 的顶点及边分别 一一对应，而且对应点与对应边之间保持相同的关联关系，则g 与g 同构。 2 3 同构的矩阵置换解释 结合1 2 4 节给出的邻接矩阵的描述和定义2 - 1 ，我们引入图同构的一种数学 等价表述：g g 等价于存在一个同阶初等行交换阵p 使邻接矩阵a 与a 满足 a - p a p 7 ，这也就是所谓两图同构的充要条件【铷。 下面我们对上述同构的充分必要条件给出证明。 证明： 充分性： 记a - p a 。户7 ，则a a ，即a h - a h ( 1 七，z 以) 。 由于尸是初等行交换阵， 则各行各列有且仅有一个1 元素，其余元素均为零； 于是按照下面规则构造双射函数，：考察p 的第t ( 1 s k 玎) 行时，如果第z 列 元素为l ，则定义， ) - l ，可见考察完全部n 行得到的函数厂必为双射函数； 而p a ，实际上是对彳t 的行列进行置换，即：p a 先完成把a 第k 行元素全 部移至，4 ) 行( 1 s k s 玎) 的工作，黝，再完成把以第，列元素全部移至 ，4 p ) 列( 1 z 一) 的工作， 1 7 任意圈的同构判定及应用研究 第二章图的同构 这样4 ，。1 i ) ，即口，l i ，盯) - 4 h ； 因为- 4 目， 所以一口，隹) ，u ) ； 由定义2 1 ，存在双射函数，且- 口，驻) ，f f ) ，又由定义2 - 2 知，有( 无) 向边 的边重数最多为1 ，而同时存在有、无向边时可以通过邻接矩阵实部部和虚部加 以区分，那么对应边重数相同，故两图同构。 必要性： 由于图g 伊，根据基本定义，设双射函数为， 则有 1 ，( 1 ) 厂( 2 ) ： ，o ) ，故4 ，耻，p ) ； 于是按照下面规则构造p ：构造第_ | ( 1 墨露墨开) 行时，除了珊耻，置为1 ，其余 元素均置为0 ，当r 1 行构造完时，得到的方阵是一