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

摘要 摘要 图的同构问题一直受到数学界与工程技术界的关注，其原因主要来自两个方 面：第，从理论上讲，一般认为该问题属于n p 一完全问题；第二，图的同构问 题具有很好的应用前景，在化学、运筹学，计算机科学、电子学、网络理论等诸 多领域都有应用，但指数时间复杂度的算法以及算法本身适用对象的局限性使得 涉及到复杂图形同构判定的应用问题难以入手。 本文提出了面向任意图的同构判定算法并系统的讨论了实际应用中基于任 意图的建模方法。 在实现上述算法与应用过程中，本文完成了以下工作： 1 在分析了简单图拓扑结构描述的基础上提出了新的任意图拓扑结构描 述方法和相应的同构判定条件。 2 建立了任意图的伴随电路模型，采用节点电压方法求取电压，将其作为 同构判定的参数，使用物理方法解决图论问题。 3 针对部分特殊图形提出了相对位序表的概念，以改进算法在处理这类图 形时的效率。 4 在具体应用中引入任意图建立模型，从而为一类很难采用单一拓扑图建 模的复杂问题提供了一种新的解决方案。 区别于目前已有的同构判定算法，该算法对于待判定的拓扑图没有附加限定 条件，能有效的应用于无向图，有向图，带权图以及由它们组成的混合图，因而 适用于各类涉及到图的同构判定的应用领域。 关键词：任意图，同构，伴随电路模型，相对位序表 中图分类号：t n7 1 1 6 a b s t r a cc a b s t r a c t t h ep r o b l e mo fg r a p hi s o m o r p h i s mh a sb e e nc o n c e r n e db yt h ef i e l d so f m a t h e m a t i c sa n de n g i n e e r i n gf o ry e a r s t h em a i nr e a s o nc o l ：1 1 e sf r o mt w oa s p e c t s ：f o r o n et h i n g ，t h e o r e t i c a l l y ，t h ep r o b l e mi sg e n e r a l l yc o n s i d e r e dt ob en p c o m p l e t e ；f o r a n o t h e r , g r a p hi s o m o r p h i s mp r o m i s e s aw i d e a p p l i c a t i o n ，s u c h a s c h e m i s t r y , o p e r a t i o n a lr e s e a r c h ，c o m p u t e rs c i e n c e ，e l e c t r o n i ce n g i n e e r i n ga n dn e t w o r kt h e o r y , b u tt h ee x p o n e n t i a lc o m p l e x i t yo ft h ea l g o r i t h m sa n dt h e i rh a r s hl i m i t a t i o n sp u to n t e s t i n gg r a p h sm a k e i td i f f i c u l tt os o l v es o m e a p p l i e dp r o b l e mr e f e r r i n g t o c o m p l i c a t e dg r a p h s i nt h i sp a p e r , a na l g o r i t h mf o ri s o m o r p h i s mt e s t i n go fa r b i t r a r yg r a p h si sp r o p o s e d a n dt h em e t h o do fm o d e l i n gf o ra p p l i e dp r o b l e m sb a s e do na r b i t r a r yg r a p h si s d i s c u s s e ds y s t e m a t i c a l l y t h ef o l l o w i n gw o r k sh a v eb e e n d o n ei nt h ei m p l e m e n t a t i o no ft h ea l g o r i t h ma n d i t sa p p l i c a t i o n 1 t h et o p o l o g i c a ls t r u c t u r eo fs i m p l eg r a p hi sa n a l y z e d ，t h e nan e wd e s c r i p t i o n o ft o p o l o g i c a ls t r u c t u r eo fa r b i t r a r yg r a p ha n dc o r r e s p o n d i n gc r i t e r i o n sf o r i s o m o r p h i s mt e s t i n ga r ee s t a b l i s h e d 2 ，t h ec o n c o m i t a n tc i r c u i tm o d e lo fa r b i t r a r yg r a p hi sb u i l t ，t h en o d a lv o l t a g e s a c h i e v e da r et h e nu s e da sp a r a m e t e ro fi s o m o r p h i s mt e s t i n g ，t h u st h ep r o b l e m o fg r a p ht h e o r yi ss o l v e db yp h y s i c a lm e t h o d 3 c o m p a r a t i v es e q u e n c et a b l e ( c s t ) i sp r o p o s e dt oe n h a n c et h ep e r f o r m a n c eo f a l g o r i t h mf o rs o m es p e c i a lg r a p h s 4 a r b i t r a r yg r a p hi si n t r o d u c e di n t om o d e l i n gi na p p l i c a t i o nf i e l d ，t h u sp r o v i d e s an e ws o l u t i o nf o rt h ec o m p l i c a t e dp r o b l e m st h a tc a nh a r d l ym o d e lw i t h s i n g l et o p o l o g i c a lg r a p h k n o wf r o ma l lt h ea l g o r i t h m sp r e s e n t e dt i l ln o w , t h i sa l g o r i t l m aa p p e n dn o r e s t r i c t i o nt ot h eg r a p h sf o rt e s t i n g i tc a nb eu s e df o ru n d i r e c t e dg r a p h s ，d i r e c t e d g r a p h s ，w e i g h e dg r a p h sa n dm i x e dg r a p h sc o m p r i s e do fa i la b o v e ，t h u si t sa p p l i c a b l e t ov a r i o u sp r o b l e m sr e f e r r i n gt og r a p hi s o m o r p h i s m k e yw o r d s ：a r b i t r a r yg r a p h ，i s o m o r p h i s m ，c o n c o m i t a n tc i r c u i tm o d e l ，c o m p a r a t i v e s e q u e n c et a b l e c l cn u m b e r ：t n7 11 6 4 0 f 言 引言 自然界和人类社会中的大量事物以及事物间的关系，常可用图形来描述。例 如，物质结构，电气网络，城市规划，交通运输，信息传送，工作调配，事物关 系等等都可用点和线连接起来的图模拟。研究图的基本概念和性质，图的理论及 其应用，构成图论的主要内容。 图论通过由点和线组成的图形，构成模拟物理系统的数学模型，并根据图的 性质进行分析，提供研究各种系统的巧妙方法。任何一个包含了某种二元关系的 系统都可以用图论的方法分析，而且它往往还有形象直观的特点。图论中应用的 线形图与几何图不同，每条边都可以有方向有权值，用以研究系统特性，进行决 策分析，确定最优设计，调整经济管理等等。 图的同构判定问题是图论学科中的基本问题之一，所谓图的同构，简单的 说，就是两个图的结构完全相同，一般认为判定同构的问题属于n p 一完全问题 j 。， 从而使得该问题与3 0 0 多个类似的问题建立了联系，这类问题是等价的，即如果 其中一个问题能找到多项式时间复杂度的算法，其他问题就都能找到多项式时间 复杂度的算法，因此，图的同构判定问题直为图论研究人员所关注。同时，图 的同构判定还有着广泛的应用前景，但指数时间复杂度的算法以及算法本身适用 对象的局限性往往使得涉及到复杂图形同构判定的应用问题难以入手。 过去3 0 年来寻找高效的同构判定算法的努力从来没有中断过。对一些特殊 的图，例如树、二分图以及顶点度数满足一定条件的图，已经有了较为高效的算 法 2 。一般的无向图同构算法中，常用的思路是出图的邻接矩阵的特征值和置换 矩阵入手来确定图的同构”r ，这样的方法在数学上是严密的，效率却不够高。 自h o p f i e l d 5 将神经网络的方法应用于图论以来，出现了很多利用神经网络解 决同构问题的新方法 6 ，“，然而这类方法往往局限于规模不大的图，且存在收敛 性的问题。虽然近年来，在同构判定问题上还出现了很多新方法【8 _ qj o ，但至今 仍未找到普适性的多项式时间复杂度算法，而在有向图以及带权图等复杂图形的 同构判定问题上更是存在大量问题有待探索。因此，找到一个能普遍适用于任意 图同构的判定方法，提高算法效率使之尽量接近于多项式复杂度依然是当前图论 研究中的重要课题。 第一章图的删构及其应用概况 第一章图的同构及其应用概况 为了便于展开图的同构问题的讨论，本章先引入图论中的一些基本概念，在 此基础上简单介绍目前已有的一些较为成熟的同构判定算法，最后举出一些涉及 到同构判定的具体应用。 1 1 基本概念 在系统的介绍图的同构判定问题之前，先就图论中的一些基本概念做如下 说明。 图论所研究的对象是事物间晟一般的关系的相互联系，事物和事物间之关 系抽象为点、线集合的图。现给出图论中通用的与本文中任意图同构判定问题相 关的概念，定义如下。 定义1 1 一个图g 定义为一个偶对( y ，e ) ，记作g = ( y ，e ) ，其中 ( 1 ) v 是一个非空集合，其中的元素称为项点。 ( 2 ) e 是无序积v x v 中的一个子集合，其元素称为边；集合v v 中的元素 可在f 中出现不止一次。 根据以上定义，分别用v ( g ) 和e ( g ) 表示图g 的顶点集合与边的集合。如 果v ( g ) 和e ( g ) 都是有限集合，则g 称为有限图；否则称为无限图。比较无限图 的同构是没有意义的，因此以下讨论的同构图都是指有限图。 通常，定义1 1 是针对无向图而言，对于有向图，需要对无向图概念作一些 拓展。 定义1 2 一个有向图q 定义为一个偶对q = ( v ，e ) ，其中 ( 1 ) v 是个非空集合，其中的元素称为顶点。 ( 2 ) e 是有序积v v 的一个子集，其元素称为有向边( 或叫做弧) ；集合v v 中的元素可在e 中出现不止一次。 根据有向图的定义，与一条有向边相关联的两个端点具有一定的次序关系， 即有向边e = ( “，v ) 是顶点“和v 的有序对。称材为有向边p 的起点，v 为终点。 如果对有向图倪= ( v ，e ) 的每一条有向边( “，v ) 从起点“到终点v 作一矢线，方 向是从“指向v ，那么有向图的每一条有向边都有确定的方向。因此有向图就是 每条边都有一定方向的图。 关于点和边的相互关系有以下概念，边与它的两端点称为关联的；与同一 第一章朗的同构及其应用概况 条边关联的两端点或者与同一个顶点关联的两条边称为相邻的：两端点相同的边 称为环；有公共起点并有公共终点的两条边称为平行边或者重边；两端点相通但 方向互为相反的两条有向边称为对称边。 有了上述定义和概念，立即可以看出，有向图与无向图的差别仅在于v v 中元素是矿中元素的有序对还是无序对。然而，无序对饥v ) 可以视为两个有序 对( “，v ) 和( v ，“) 。也就是说，对于无向图g ，将g 中每条边e 用两条与p 有相同 端点的对称边来替代后得到个有向图q 。这样得到的有向图q 称为g 的对称 有向图。由此可见，无向图可以视为特殊的有向图。图1 1 ( a ) 和( b ) 中所示的图就 是这样的两个图。 图论中研究的部分内容常与边的方向没有关系，故在讨论与边方向没有关 系的有向图q 时，人们通常去掉边上的方向，这样得到的无向图g 称为g ，的基 础图。反之，任给一个无向图g ，将g 的边指定个方向从而得到一个有向图g ， 称这样的有向图玩为g 的一个定向图，如图1 1 ( c ) 所示。 v ，义 ，!毪 ( a ) 无向图g( b ) g 的对称有向图q ( c ) g 的定向图氓 图1 1 定义1 3 对无向图( 或有向图) ，在各条边加上相应的权值w ，则构成了带 权图。可以认为，不带权的图中各条边的权值均为1 。 定义1 4 设v v ( g ) ，g 中与顶点v 关联的边的条数称为v ( 在g 中) 的度数。 相应的，对于有向图而言，与顶点v 关联的边中方向指向这个子图的边称 为入边，方向离开这个子图的边称为出边。入边的数目称为入度，出边的数目称 为出度。 定义1 5 设有个顶点的无向图g = ( 矿，e ) 的顶点集为g = v ，v 2 ， ， 用略表示g 中v 与之间的边数。称其对应的矩阵d = 【毛 。为g 的邻接矩阵。 其中： 吒= k叶和v ，邻接，且v 和v ，间有k 重边( 0 ) 4 ，= 0v 和v ，不邻接 0 第一章图的同构及e 应用概况 图的邻接矩阵有以下明显的性质： ( 1 ) d 是一个对称矩阵； ( 2 ) 若g 为无环图。则d 中第f 行的元素之和等于顶点v 的度数。 ( 3 ) 当且仅当图的邻接矩阵可以分块为 d ：i2 堕k 一旦一l l 0l d ( q ) j 时，图g 是一个具有g ，和g ：两个连通片的非连通图。d ( g 。) 是对应连通片 g 的临界矩阵，d ( g ) 是对应连通片g 的邻接矩阵。 而对于有向图和带权图，显然以上关于无向图邻接矩阵的定义很不合适， 具体的定义方法将在以后的章节中讨论。 利用以上基本概念考察以下两幅无向图( 图1 2 ) 。 爪 么：查：! 左：竺：! 盐 一 么：! 查兰 v i e 6 ( a ) g 原始同 ，p ：和e 鹾 小 e ；火。； v ，么二。 图1 3 变形后的同构图 ( b ) g 3 第一章图的司构及其应用概况 很明显，直观上看g l 和g 3 结构上完全一致，而由变化过程可知图q 和g 3 是 同一个图，由此可得g 1 和g 2 结构上完全一致，即同构。 对照图l - 3 很容易得出g l 和g 3 ( g 2 ) 顶点与边的对应关系为： q 停吩e j 停e 3 v 2h 屹岛hf 2 b ”ie he l v 4 七v 4e 4 be 4 ”岛 h 由上，可以得到图的同构定义。 定义1 6 如果两个图g 与g 的点之间一一对应，边之间一一对应，而且 对应点与对应边之间保持相同的关联关系，那么g 与g 同构。 该定义直观的表述了图的同构概念，对于一些回溯算法可以采用这种定义 判断同构，但在计算机处理中更为一般的是使用矩阵的方法来判断图的同构，相 应的，可以使用置换矩阵的概念来描述图的同构。 定理1 1两个图g 与g 同构的充要条件是存在一个置换矩阵p ，使得邻 接矩阵有 d = p 7 d 尸 即经过一定的行、列变换能够使g 与g 对应的点处于邻接矩阵中行与列的 相同位置。 考察如下g 和g ，的邻接矩阵。 v 1 d 1 ：v 2 屹 v 4 巧吩 o1 10 11 ll 屿蟾 一 11 1l o1 l0 v 。1v 2v 3v 4 o111 1oll 1 101 1l1o 这里无需经过任何行列变换，可以直接从两个图的相同的邻接矩阵得到两图 同构的结论。 实际上，上面的例子是一类特殊的无向图完备图，它的每一对不同的顶 点之间均有一条边相连，因此无论顶点编号如何改变，它都具备唯一的邻接矩阵。 具有n 个顶点的完备图中，每个顶点的度为即一1 。相同顶点数的完备图的邻接矩 阵无需经过行、列交换即是相等的。还有一种图，每一个顶点都具有相同的度， 这种图被称为正则图。每个顶点的度均为k 的正则图称为知正则图。完备图是一 类特殊的正则图，即即一1 正则图。 4 v v v v = 现 第章图的同构及其应用概犹 1 2 算法简介 在大多数情况下，顶点的编号并不是事先确定的，因此对于两个非完备图而 言，即使它们是同构图，对应的邻接矩阵也往往不是一开始就相等的，如图1 4 所示。 g g 图1 4 两个具有不同邻接矩阵的同构图 它们的邻接矩阵如下。 巧吩哆吩吩 ol1l1 1o 1 01 1101o 10 101 110lo v lv2 v3v4v5 o1101 10 ll1 1l0lo 0l1ol 11o10 经过比较分析，可以找到两幅图顶点的一种对应关系为：v 1h v ：，v 2hv ， v ；v ，v d v 。，嵋v 。应对邻接矩阵就是将d 的第1 行与第2 行交换， 第3 行与第5 行交换，再将第l 列与第2 列交换，第3 列与第5 列交换，可得到 变换后的d 等于d 。 遗憾的是，对计算机而言，并不能直接“看”出点与点之间的对应关系， 一个古老而严密的算法是：先写出两个图的邻接矩阵d 与d ，然后对d 进行所 有可能的行、列交换，如果能使d = d ，则判定同构，否则不同构。而“所有 可能的行、列交换”意味着行的全排列与列的全排列，在最坏情况下可能需要”! 次行、列交换，这种算法在点数稍大时就无法忍受了。这种算法的一种改进算法 是对相同度数的顶点进行全排列，即如果图g ( g ) 有”个度数为i 的顶点，那么 第一章图的同构披其应用概况 需要重新排列的运算量就减少至m ! n 21 喝h ，当比较幸运时，数量会得到一定 程度的限制，但并不能保证对每一个图都适用，例如对于每个顶点度数都相同的 正则图就毫无作用，因此这种改进是相当有限的。 同时，以上篇幅介绍的同构还仅是无向图范围内的同构，对于有向图和带 权图以及更广义上的任意图的同构判定的研究也还只是处于探索阶段。这里对一 部分现有的同构算法做简单的介绍。 1 2 1v f 算法 lpc o r d e l i a 等人提出的v f 算法 1 0 3 是一种经典的图匹配算法，用于解决无 向( 子1 图同构问题。 算法的基本原理为：假设提问图q g 有m 个顶点，目标图t g 有”个顶点， m 5 ，根据定义的匹配原则，在q g 与z - g 间可建立映射c ，c 是q g 和丁g 中 相互匹配的顶点对的集合，c 中的元素q = ( m ，n j ) 表示q g 的顶点m ，与t g 的顶 点n j 相互匹配。c 也反映了q g 与t g 中边的对应关系，即如果c 中含有两元素 ( ，n j ) 与( m p ，) ，并且( 碍，州，) 是9 g 中的一条边，则( 疗，) 必定是t g 中的一 条边，并且边( ，m ，) 和边( 打，) 匹配。如果c 中包含q g 中的所有顶点，即c 中含有m 个顶点对，则表明q g 是丁g 的子图( 子结构匹配) ，否则q g 与z t g 不 是子结构匹配。 算法中引入状态空间( s s r ) 的概念来描述匹配过程，状态空间s 是c 的一个 子集，代表局部匹配，向s 中加入新的满足条件的顶点对，j 就转变成下一一个更 大的状态空间s 。 算法采用了深度优先遍历的方式，在判定过程中，首先将状态空间晶设为 空，表示不存在任何匹配的顶点。对于q g 中的任一顶点，在t g 中寻找满足匹 配原则的顶点，如果找到则将该顶点对加入到s o 中，如果找不到则回溯到上个 顶点，直到回溯到第一个顶点，如果在丁g 中找不到与q g 的第一个顶点匹配的 顶点，表明两图不匹配。其步骤如下： 1 ) 赋初值：s = 。 2 ) 如果s 中包含m 个顶点对，则q g 与丁g 匹配，输出s ，算法结束。 3 ) 如果q g 的当前顶点是q g 的第一个顶点且在t g 中找不到与之匹配的 顶点，则q o 与t g 不匹配，算法结束。 4 ) 选择q g 中下一个顶点现。 5 ) 选择粥中下一个未访问过的顶点”，如果不存在这样的顶点则回溯到 第一章图的同构搜其成用概况 上一级顶点，转到步骤3 ) 。 6 ) 如果所。与疗，满足上述条件，记为( 卅。，n ，) ，将其加入到s 中，并将状 态空间记为s ，如果不满足条件，则转到步骤5 ) 。 7 ) 令s = s ，转到步骤2 ) 。 在最好的情况下，每次匹配只有一对顶点满足条件，匹配过程中需要访问 的状态空间数与该图顶点数相同，此时，算法是具备多项式时间复杂度的；在。 些较坏的情况下，需要遍历所有可能的状态空间才能得出结果，而所有的状态空 间数正比于图中顶点数的阶乘，进而可能需要较大的开销的才能得到结果。 1 2 2 基于h o p f i e l d 网络的图的同构算法 自从h o p f i e l d 网络被成功的用于解决t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 这类 困难组合问题以来，许多学者也尝试应用神经网络来解决图的同构问题，提出了 一些基于神经网络的图的同构算法。其中文 7 】的作者通过简化能量函数，并建 立相应的数学理论，给出了一种新的神经网络求解无向图同构的改进方法，并通 过进一步分析h o p f i e l d 网络的拓扑结构，给出了电路实现图。 对于两个满足顶点数与边数相等条件的n 阶无向图，算法首先构造了一个含 个神经元的h o p f i e l d 网络，由这些神经元组成置换矩阵，构成两个图之间 的映射。根据置换矩阵的性质可以构造相应的能量函数。由于h o p f i e l d 网络算法 是一种梯度算法，有可能求得能量函数的局部极小，即网络有可能运行至不希望 的吸引子或吸引环内，文中所提出的能量函数，当且仅当满足一定条件时达到能 量函数的最小值0 ，因此在网络进入稳态之后通过判断能量是否接近于0 来判断 该稳态是否是希望的吸引子，若不是则重新产生初值并运行网络。如此循环反复 直到网络进入希望的吸引子，得出两图同构，并由网络稳态输出两图顶点之问的 对应关系；或者网络运行的迭代次数太多，大于事先给出的门限，得出两图不同 构的结论为止。 该算法的独到之处在于基本上避免了对顶点进行排列运算的情况，因而克服 了其他算法普遍存在的部分顶点全排列的问题。使用该方法处理不同的图可能需 要选取不同的步长，不恰当的取值可能会导致迭代次数过多造成的误判。 1 2 3 顶点度数序列法 该算法实际上是由文章”3 先后提出的两个不同的算法，分别称为关联度 第一章| 呈| 的同构及其应用概况 序列法和出入度序列法，前者用于解决无向图同构的问题，而后者用于解决有向 图同构的问题，算法涉及到连通子图，连通子图的( 出入) 度数，连通子图的( 出入) 度数序列等概念。 首先，算法定义了聆点连通子图的概念，即如果由n 个点以及连接于这h 个顶点之间的边组成的子图是连通的，该子图就被称为n 点连通子图。随后，算 法引入了顶点合并的概念，即将两个任意顶点i 与，重合，并使原来接于i 的边 都接于，最后再消去这一过程中出现的自环。文章认为对于同构的有( 无) 向图 而言，对由各自对应的几个顼点组成的n 点连通子图作顶点合并，得到的新图也 是同构图。n 点连通子图作顶点合并后的那个顶点对应的( 出入) 度数，被称为连 通子图的( 出入) 度数。所有n 点依次取1 到的所有整数，为原图顶点数) 连通子图的( 出入) 度数集合被称为连通子图的( 出入) 度数序列。对于同构图而氰 必然具有严格相等的( 出入) 度数序列，因为该序列反映了各个n 点连通子图层次 卜的点与边的关系，如果两图在结构上有稍许细微的差别，必然造成某一层次n 点连通子图( 出入) 度数的差别。反之，具有相同的( 出入) 度数序列的两图也必然 同构。这一结论是该算法判定两图同构的基本依据。 1 3 应用简介 生产管理、军事、交通运输、计算机和通讯网络等方面许多离散问题的出 现，大大促进了图论的发展。进入7 0 年代以后，特别是大型电子计算机的出现， 使大规模问题的求解成为可能。图的理论及其在物理、化学、运筹学，计算机科 学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科 领域中各方面应用的研究都得到“爆炸性发展”。主要有一下三个原因： 1 图论提供了一个自然的结构，由此而产生的数学模型几乎适合于所有科 学( 自然科学和社会科学) 领域，只要这个领域研究的主题是“对象”与 “对象”之间的关系。 2 图论己形成自己的丰富词汇语言，它能简洁地表示出各个领域中“对象一 关系”结构复杂而又难懂的概念。图论的思想和方法越来越被许多科学 领域所接受，并已发挥且将日益发挥它的重要作用。反过来，这些得益 于图论的科学领域又向图论提出新的研究课题、新的概念和新的研究方 法。 3 图论提供了大量令人跃跃欲试的智力挑战性问题，小到初学者的简单习 题，大到能使所有资深数学家感到棘手且悬而未决的难题。 第一章图的同构及l 应用概况 作为图论研究的一个重要课题，图的同构判定也在许多应用领域中发挥着 重要的作用。 1 3 1 运动链的同构识别 任何机构的结构都可以用运动链结构简图表示，机构中构件与运动副的类 型，数量及相互关系，在运动链图上都有明确的表示。机构运动链同构的识别是 机构学中的基本概念之一，对机构的结构类型综合及优选结构类型有重要意义： 若将非同构的运动链误判为同构，则可能丢失有价值的新运动链：若将本为同构 的运动链视为不同，则可能会造成机构类型的重复而失去意义。 机构学在应用图论进行类型综合时，通常把机构的运动链抽象成拓扑图， 也称线图。拓扑图中每一个顶点对应机构运动链的一个构件，每一边对应运动链 的一个运动副，与顶点关联的边数称为顶点的度数，即为该构件所含运动副数， 如图1 5 所示。 ( a ) 运动链简图 图1 5 ( b ) 拓扑结构图 有了以上模型，再利用运动链的一些特征，即可按照一些现有的运动链同 构判定算法n 3 ，“1 进行判别。 1 3 2 汉字的自动识别 汉字已有千年的历史，也是世界上使用人数最多的文字，对于中华民族灿 烂文化的形成和发展有着不可磨灭的贡献，并将继续发挥重要的、其它文字形式 难以取代的作用。然而，汉字是非字母化、非拼音化的文字，在当今高度信息化 的社会里，如何快速高效地将汉字输入计算机，已成为影响人一机交流信息效率 第一章图的一构披其应用概况 的一一个重要瓶颈，用计算机来自动识别汉字或者其他象形文字，是当前比较热门 的一个研究领域，而且取得了长足的进展。汉字的数量繁多，笔画复杂，而且有 许多字形相近的字。 如图1 6 所示的两个汉字，字形就很相似。区分、识别这一类汉字，图的同 构判定算法是一个有力的工具。这类汉字，字型虽然相近，但从图的拓扑结构t 看，它们并不同构。 杭抗 ( a )( b ) 图1 6 两个相似的汉字 可以将这两个汉字抽象成无向图，并利用关联度序列法1 进行图的同构判 断，具体的应用到这两个字上，则给出了它们对应的关联度序列作为这两个字的 特征识别码。这种方法已经被作者成功的应用于汉字( 包括印刷体和手写体) 的识 别中“引6 ，”】，并取得了很好的识别效果。 第一二章任意图同构判定的基本理论 第二章任意图同构判定的基本理论 图论中很多关于图和同构的定义与讨论往往仅限于不带权值的无向图。在 这样的定义下，实际应用中针对不同的应用还需要对具体的图做相应的限定以使 之能与定义相符合。 本文将在任意图的框架下展丌同构问题判定及其应用的讨论，研究的对象 是任意图，这就需要重新定义图论中的一些基本概念，以建立一个完备的对任意 图的描述，如任意图邻接矩阵以及顶点的度等等，然后从这些对拓扑结构的描述 中分析出同构的任意图所具有的一些性质。同时，因为本文将在电路理论的框架 下讨论图论中的同构问题，在本章中，也会对需要用到的电路相关理论( 主要是 节点电压法) 做详细的介绍。 2 1 任意图的基本定义 本文所讨论的图的同构判定的对象是任意图，任意图包含了无向图，有向图， 带权图以及由它们组成的混合图。混合图中，边可以是有向的，也可以是无向的， 可以是带权的，也可以是不带权的。在此定义下，其它图均是它的特例。不失一 般性，以后的讨论均针对混合图。 在混合图中，本文用历表示有向边集合，匕表示无向边集合。从顶点v ，指 向v ，的有向边用( v 。，v ，) 表示，其权值用，表示( 若无权值规定w ，可，x 为该图最 大权值的两倍) 。顶点q 与v ，之间的无向边用 v i ，v ，) 表示，其权值用。，表示，对 无向边显然有m ，= m 。( 若无权值则规定m 。= 州。= 。 定义2 1 任意图邻接矩阵：具有n 个顶点的混合图g ，其邻接矩阵d 是p 阶矩阵，矩阵中元素厦为： ，i ( 嘞，w g k , m # ，m 归，m 妇)( h ，叶) 目或 v j ，o ) g o “1 0( v i , v ，) 萑日且“，v ，) 萑e o 其中，k 和p 分别表示该图有k 重有向边和p 重无向边，w 。表示第k 重有 向边的权值，m ，。表示第p 重无向边的权值，权值与m 。内部分别按从小到大 的顺序排列( 无权边的x 靠前) ，这里w l ， 2 ( ，n o ， m 啦 m j ；p 。 与m ，之间用分号隔开，以显式的区分有向边和无向边。如果两顶点之间只有有 向边没有无向边，则使用( ，w ，缸；) 表示，只有无向边没有有向边则使用 ( ；m 心删啦，m ，) 表示，如果既没有有向边又没有无向边，则简单的以0 表示， 第一二章任意蚓同构判定的基奉理论 而不再繁琐的使用( 0 ；o ) 表示了。 由于任意图邻接矩阵仅涉及顶点与顶点的关系，在后面的图中，边就不再 独立标号了，对于带权边则仅使用数字标出其权值。为避免混淆，顶点使用数字 加圈的形式表示，如顶点1 使用表示。 如图2 1 中的混合图g 与g ，按上述规则它们对应的任意图邻接矩阵分别是 d 与d 。 1 2 d = 3 4 ( a ) 图g( b ) 图g 图2 1 两个任意图同构的例子 ( 0 ) ( ；1 ) ( ；1 ) ( 0 ) ( 0 ) ( 2 ；) ( ；1 )( ；x ) ( 0 )( ；1 ) ( 1 ；)( ；x ) ( 0 ) ( x ，2 ；x ) ( ；x )( 0 ) 1 d ：2 3 4 ( 0 ) ( ；1 ) ( 0 )( ；1 ) ( ；1 ) ( 0 ) ( 1 ；)( ；x ) ( 0 ) ( 2 ；) ( 0 ) ( x ，2 ；x ) ( ；1 ) ( ；x ) ( ；x )( 0 ) 图中g 与g 各有4 个顶点，于是它们的任意图邻接矩阵是4 4 阶矩阵，以 g 为例在顶点到顶点之间有一条权值为2 的有向边，一条不带权值的有向边， 以及一条不带权值的无向边，这里最大的权值为2 ，所以x - = 4 于是d 3 。：( x ，2 ；x ) 。 显然这里无需作任何行、列交换，两图的邻接矩阵d = d ，所以可以直接判定 这两个图同构。观察图2 1 ，可以发现本例中的两个图对应的顶点刚好为 l 一1 ，2 2 ，3 3 ，4 4 ，这和刚才的d = d 是等价的。 定义2 2 顶点v l 与毒条无向边，d 。+ 屈条有向边相接( 其中口。表示背离顶点 叶的有向边，屈表示指向顶点q 的有向边) ，亦即顶点v 的无向边度数为毒，有 向边出度为口，入度为屈，于是该顶点的度数集 = 口，屈；毒 。 以上两个定义不失一般性的包含了所有可能的图，当f - ，时( v ，v ，) 或 v ，v ， 表示的就是一个无向自环或有向自环，特别地，带自环的情况将在第四章算法部 分末尾加以说明，因此下面讨论的任意图建模将暂不考虑自环情况，因此，邻按 矩阵的对角元素保持全0 。 第二章任意图同构判定的基t 本理论 由定义2 2 对顶点度数集的定义，可知图2 1 的g 中4 个顶点的度数集分别 为：丑= 0 ，0 ；2 ) ，五= 1 ，1 ；2 ) ，也= 3 ，1 ；1 ) ，丑= o ，2 ；3 ) ，很明显，g 中顶点的 度数集与g 一一对应相等。 实际上，定义任意图顶点的度数集为任意图同构的判定提供了一个重要的 必要条件，即两个同构的任意图所含相同度数集的顶点数相同。 由于采用了无向边与有向边及其对应的度分别定义的形式，同时在矩阵元 素的定义上又将权值和边的重数分离开来，以上两个定义所规定的任意图邻接矩 阵和度数集唯一的确定了一个混合图，第一章所介绍的基础图，对称有向图和定 向图，都可以通过这种方法唯一的确定，如图2 2 所示，它们对应的任意图邻接 矩阵分别是d ，b 与协。 ( a ) 基础图g 7 心入 绺厶匈 ( b ) 对称有向图g d ( c ) 定向图g 。 图2 2 123 1 d2 d3 d 1 i ( 0 ) ( ；1 ) ( ；1 ) l d i ( o ) ( 1 ；) ( 1 ；) d = 2 i ( ；1 ) ( 0 ) ( ；1 ) id = 2 d i ( 1 ；) ( 0 ) ( 1 ；) 3 l ( ；1 ) ( ；1 ) ( o ) j3 。m ) ( 1 ；) ( o ) g ，q 和q 中各顶点的度数集分别为： = 0 ，0 ；2 ) 4 = 2 ，2 ；0 ) 如= ( o ，0 ；2 以= 2 ，2 ；0 如= o ，0 ；2 ) 五= 2 ，2 ；0 根据以上定义，得到以下定理。 1 h2 3 1 小o ) ( o ) ( 1 ；) 1 d = 2 。if 1 ：) ( 0 ) ( 0 ) j3 ：l i o ) ( 1 ；) ( o ) j = l ，1 ；0 如= l ，1 ；0 ) 厶= 1 ，1 ；0 ) 定理2 , 1 两个任意图g 与g 同构的充要条件是存在一个置换矩阵p ，使 得任意图邻接矩阵有 d = p d j p 即经过一定的行、列变换能够使g 与g 对应的点处于邻接矩阵中行与列的 相同位置。 显然，同构图经过一定的行、列变换后必然具有相同的任意图邻接矩阵。 第二章任意图同构判定的基率理论 为了便于表述，在后面的讨论中，直接用邻接矩阵指代定义2 1 所规定的任 意图邻接矩阵。 将定义1 6 拓展到任意图，得到如下同构定义 定理2 2 如果两个图g 与g 的点之间一一对应，边之间一一对应，对应 点与对应边之间保持相同的关联关系，同时对应边上具有相同的权值，那么g 与g 同构。 定理2 2 中所指的边包含了有向边与无向边，权值包含了有向边权值与无向 边权值。 由定理2 1 ，经过一定的行、列变换能够使同构图g 与g 。对应的点处于邻 接矩阵中行与列的相同位置。所以g 与g 的邻接矩阵的“行列式”的值也相等。 因为定义2 1 所规定的邻接矩阵并不是一个二维矩阵，无法直接得到对应的行列 式的值，需要对它作以下规定。 定义2 3 将邻接矩阵d 按有向边和无向边的分类分为两个矩阵d 和d ， 将n 和n 的空白处用0 填满，使这两个矩阵中所有元素的维数均达到各自矩阵 中包含的最大有向边重边数k 和无向边重边数p ，称口为有向边邻接矩阵，皿为 无向边邻接矩阵，当k 与p 都不为1 时，d 1 和n 是两个三维矩阵，按第三维分 别将d l 和d 2 两个矩阵分为k 个两维矩阵和p 个二维矩阵q ，d l ：，d l 。与 d 2 ，d 2 ：，d 2 。，如k 或p 等于1 ，则相应的矩阵不需要再做细分，于是d 的行 列式集i d l = f 日。i ，id 1 ：卜，i d , 。i ；i d ，卜，ld 2 ，j 。 如邻接矩阵只含有向边或无向边，则与邻接矩阵的表达一样，直接留空， 分号照写。 定理2 3同构图邻接矩阵的行列式集相等 对照定理2 2 ，定义2 3 规定的行列式集实际上是将求取任意图的行列式问 题变成了求取有向图行列式和无向图行列式两个问题，因为邻接矩阵元素中有向 边和无向边如果带重数的话，权值是分别按增序排列的，而这里的每一个二维矩 阵实际上都是一组相同排序的边( 位于相同重数层次上的边) 对应的邻接矩阵的 行列式，所以两个同构图必须满足所有细分出来的二维矩阵都要一一1 。对应相等， 所以它们的行列式集是相等的。 这是一个必要条件，不同构的图也可能有相同的行列式集，而且对细分的 有向边子图和无向边子图而言，在混合图中并没有保证它们分别连通的限定，此 时每个子图对应的邻接矩阵行列式的值实际上都是0 ，但使用行列式集作为判据 对于大量实际应用中涉及到的图而言，依然是较为有效的，可以用于初步筛选待 判定的图。 以下页图2 3 ( a ) ( b ) e og 与g 为例，而显然原拓扑图是不同构的，其中存在 釜三量堡童里塑塑型塞竺苎查型堕 连通的无向子图，于是在这里使用它们的邻接矩阵d 和d 构造行列式集l d i 与 i d f 是有效的，并可直接得到不同构的结论，具体过程如下所示。 ( a ) 图g 1 l ( 0 ) ( ；l ，2 ) ( ；1 ) d = 2 j ( 1 ，2 ) ( 0 ) ( ；1 ) j 3 l ( 2 ；1 ) ( 2 ；1 ) ( o ) j 图2 3 ( b ) 图g l 1 l ( 0 ) d = 2 j ( ；1 ) 3 l ( o ；2 ) 2 3 ( 2 ；1 ) ( 1 ；2 ) ( 0 ) ( ；1 ，2 ) j ( 1 ，2 ) ( 0 ) j 将d 按有向边和无向边分为两个矩阵，并将矩阵空白处用0 填满，使每个 元素的维数均达到该矩阵中包含的最大重边数，得到有向边关联矩阵口，和无 1 l ( 0 ) ( 0 ) ( 0 ) |1 ( 0 ，o ) ( 1 ，2 ) ( 1 ，o ) d f = 2 ( 0 ) ( 0 ) ( 0 ) i砬= 2 2 ) ( 0 , 0 ) ( 1 ，0 ) 3 l ( 2 ) ( 2 ) ( o ) j3 l ( 1 ，0 ) ( 1 ，0 ) ( o ，0 ) i 对d f 矩阵，叱中不含重边，直接写成以下形式 1 10 0 0l d ij = 2 100 0l 对d 2 矩阵，d 2 ，中含两个重边，先后分两次提出d 2 。中的边，组成下面两个 第二章任意幽同构判定的基本理论 昕卜弼o i d i 。i = ol d 2 ，i _ 2i d 2 ：i - o ， t & i d l = 0 ；2 ，0 ) 。 重复相同的步骤可得l d l _ 0 ；4 ，0 j ，i d l i d l ，所以可直接判定g 与g 不 2 2 线形时不变网络的节点电压分析法 在用“网络拓扑”理论研究网络时，首先将电网络抽象成反映网络结构的线 性图( 拓扑图) 。即用一个线段代替两端元件，且称之为支路，并用b k 表示第k 条 支路，用一个点代替元件问的连接点，且称之为节点，并用胛表示第f 个节点。 一个节点和支路的集合，并且其中支路仅在节点相交，则此集合称为线性图或简 称为图。 电学和电路的基本理论告诉我们： 对集中参数网络的任一节点，流入或流出电流的代数和为零。这就是克希霍 夫电流定律( k c l ) 。 对集中参数网络的任一回路，其电压降的代数和为零。这就是克希霍夫电压 定律( k v l ) 。 节点电压法是以节点电压为求解电路的未知量，利用k c l 和支路的伏安关 系( v c r ) 导出仰一1 ) 个独立节点电压为未知量的方程，联立求解，得出各节点电 压，然后进一步求出网络各待求量的方法。 节点电压法适用于结构复杂、非平面电路、独立回路选择麻烦、以及节点少、 回路多的电路的分析求解。对于行个节点、坍条支路的电路，节点电压法仅需 m 一1 ) 个独立方程。 在网络中，任选一个节点为参考节点( 一般选取编号最大的一个节点) ，其余 每个节点与参考节点之间的电压，分别称为该节点对应的的节点电压。节点电压 的参考极性均以所对应节点为正极性端，以参考节点为负极性端。显然，节点电 压数比节点数少一个。对于具有h 个节点的网络，有n 一1 个节点电压，其中节点 心对应的节