（电路与系统专业论文）图的同构判定算法研究.pdf

摘要 f7 7 2 5 2 8 图的同构是图论学科中的基本问题之一，属于图论中多个n p 完全问题之 一。所谓图的同构，简单地说，就是二个图的结构完全相同。“同构”的概念看 起来如此简单，但是，要判断两个图是否同构却是一件不简单的事情。 本文对图的同构判定提出了独特的思路，即将图的同构问题转化为电路的相 同问题，从而得到了两图同构的又一必要( 几乎充分) 条件，在大多数情况下可 有效判定两图是否同构，此时算法时间复杂性为o ( 2 n 4 ) 。 在算法实现过程中，本文完成了以下工作： 分析了判定图的同构所需要的条 牛，目前存在的图的同构判定算法以及这些 算法的有效性。 提出了一种新的同构判定算法，电路模拟法，并介绍了此方法所涉及的新概 念，相同电路、图的伴随电路、全激励、节点电压序列以及节点电压序列集。 详细介绍了电路模拟法的基本算法以及改进后的算法实现步骤，算法实现的 框图，并将本算法与别的判定算法有效性进行了比较。 最后本文利用电路模拟法对几组图进行了同构判定，证明了本算法的有效 性，在大多数情况下都能快速有效的进行判定。 本文从节点电压序列内部的电压值是否相等和节点电压序列之间是否相等 两个方面着手确定图的顶点之间的对应关系，因此本文的算法对判定绝大多数图 是否同构是有效的且快速的。 关键词；图的同构，算法复杂佳，伴随电路 a b s t r a c t g r a p h si 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 sa n dn pp r o b l e m si ng r a p h t h e o r y g r a p h s i s o m o r p h i s mm e a n st h a tt h eg r a p h s a r c h i t e c t u r e sa l et h es a m e t h e c o n c e p ti ss i m p l eb u ti t sn o ts oe a s yt od e t e r m i n ew h e t h e rt w og r a p h sa r ei s o m o r p h i c o r n o t au n i q u em e t h o di sp r o p o s e dh e r e ，w h i c ht r a n s f e r st h eg r a p h s i s o m o r p h i s m p r o b l e mi n t ot h ei d e n t i c a lc i r c u i t sp r o b l e m w eg e tan e c e s s a r yc o n d i t i o n ( a l m o s tf u l l c o n d i t i o n ) f o rg r a p h s li s o m o r p h i s m m o s to ft h et i m ei t se f f e c t i v et oj u d g eg r a p h s i s o m o r p h i s ma n dt h et i m ec o m p l i c a t i o ni so ( 2 n 4 ) t h ef o l l o w i n g j o b sh a v eb e e nd o n ei nt h ei m p l e m e n t a t i o no f t h i sa l g o r i t h m a n a l y z e dt h ec o n d i t i o n sn e e d e dt oj u d g eg r a p h s i s o m o r p h i s m ；a n a l y z e dt h e e f f i c i e n c yo f e x i s t e dm e t h o dt o j u d g eg r a p h s i s o m o r p h i s m p r o p o s e dan e wm e t h o d ，c i r c u i ts i m u l a t i o nm e t h o d ；d e s c r i b e dt h en e wc o n c e p t s o ft h i sm e t h o d ，i d e n t i c a lc i r c u i t s ，f o l l o w i n gc i r c u i tf o rg r a p h ，f u l ls t i m u l a t i o n ，n o d e s v o l t a g es e q u e n c e ，c o l l e c t i o no f n o d e sv o l t a g es e q u e n c e 。 d e s c r i b e dt h ec i r c u i ts i m u l a t i o nm e t h o da n dt h ei m p l e m e n t a t i o no f t h em e t h o di n d e t a i l ；c o m p a r e dt h ee f f i c i e n c yo ft h i s m e t h o dw i t ha d v a n c e dn o d e se x c h a n g e m e t h o d j u d g e dt h ei s o m o r p h i s mo fs e v e r a lg r o u p so fg r a p h sw i 1t h i sm e t h o d ；p r o v e d t h ee f f i c i e n c yo f t h em e t h o dt om o s tg r a p h s t h i sm e t h o dd e t e r m i n et h ec o r r e s p o n d i n gn o d e si nt h et w og r a p h st h r o u g h c o m p a r i n gt h ev o l t a g ei nas p e c i a ls e q u e n c ea n dc o m p a r i n gt h es e q u e n c ei nt h e c o l l e c t i o n ，w h i c hr e s o l v e st h a ti t se f f e c t i v ea n dq u i c kt oj u d g em o s tg r a p h s i s o m o r p h i s m k e y w o r d s ：g r a p h s i s o m o r p h i s m ，a l g o r i t h mc o m p l i c a t i o n ，f o l l o w i n gc i r c u i t s 引占 引言 图论是一个应用十分广泛而又极其有趣的分支，物理，化学、生物、科学管 理、计算机等各个领域都可以找到图论的足迹。图论与数学的其他分支，如群论、 矩阵论、概率论、拓扑、数值分析、组合数学等都有着密切的关系。 在历史上，又很多科学家对图论学科的形成作出过贡献，特别耍提到的是欧 拉( e u l e r ) 、基希霍夫( k i r o h h o f f ) 与凯莱( c a y l e y ) 。 欧拉在1 7 3 6 年发表了第一篇图论的论文。解决了有名的七桥问题。拓扑学 中著名的欧拉公式同时也是图论中的重要公式。 基希霍夫对电路网络的研究( 学过电路的人一定知道著名的基希霍夫定律) 及凯莱在有机化学的计算中都应用了树、生成树等图论概念。 很多有趣的数学游戏与谜语也促进了图论的发展，哈密顿的周游世界的游戏 就是其中著名的一个。对四色定理的研究也曾很大地促进了图论的发展。 图论所研究的对象是事物阃最一般的关系的相互联系，事物和事物阊之关系 抽象为点、线集合的图。因此，可以用多种方法对图进行定义。但是，定义的叙 述虽不相同，其实质则是一致的。无非是说明什么是边和顶点，以及边和项点的 二元关系。 图的同构是图论学科中的基本问题之一，也是很难解决的多个n p 完全问题 之一。所谓图的同构，简单地说，就是二个图的结构完全相同。“同构”的概念 看起来如此简单，但是，要判断二个图是否同构却是一件不简单的事情。有人 试图寻找图的组不变量( g r a p hi n v a r i a n t ) 来确定图的同构，如回路数、树数、 连通片数等，但这些尝试都失败了，因为不同构的图也可能有完全相同的不变量。 有人【1 】曾经认为图的邻按矩阵的特征多项式和特征值可能是图的同构判据，但结 果也失败了，因为不同构的图也可能有相同的特征多项式和特征值。虽然近些年 来，又有不少专家学者对图的同构判定问题进行了探索研究【1 ，2 j a ”，找到了一些 图的判定算法，但是迄今为止，图的同构判定多项式算法仍未找到，这一问题仍 未彻底解决。因此图的同构判定仍然是值得图论学者和算法研究人员探索的重要 课韪。 第一素凹的同构判定问题的简介 第一章图的同构判定问题的简介 1 图的基本概念 图的同构判定所涉及的图论中的基本概念主要包括：边，顶点，图，顶点的 度和邻接矩阵。 定义l 一1 边、顶点和图 一个图是由一个非空集合v ( g ) = 叶 和v ( g ) 中元素的无序对的一个集合 e ( g ) = 略 所构成的二元组( v ( g ) ，e ( g ) ) 。v ( g ) 中的元素v 叫做顶点；e ( g ) 中 的元素“，叫做边。若v ( g ) ) 和e ( g ) 是有限集合，则g 称为有限图：否则，称 为无限图。图论中通常讨论的是有限图。 由上所述，对于图g 来说。两个端点之间连接的线段就是边，边的端点就 是顶点。除在顶点外，两条边都不相交。边的两端连在一起，共一个顶点，叫做 自环。两条边以端点相并连接，叫做并行边。不含并行边和自环的图，称为简单 图。若边e = f ，v ，) ，就说边e k 连接顶点v 和v j ，而u 邻接v j ，或说边e l ：和顶 点v ，v j 相关联，而v j 是v i 的邻居。两条边关联相同的顶点，叫做邻接边。 图用符号g 表示，e l ，e 2 表示边v l ，v z ，v 3 表示顶点。有时为了同 时表示几个图，则用g l ，g 2 区别之。 定义l 一2 顶点的度 图中顶点的度，是指该顶点所关联的边的数目。度数为0 的顶点称为孤立项 点。由图中顶点的度，可以看到有两种特殊的图：完备图和m 阶全图。 完备图，是图中任一对相异顶点之间均有一边相连的图。具有| v 个顶点的 完备图中，每个顶点的度为一1 。如图1 一l 中的图g 就是一个完备图，图中 共有有4 吟顶点，其每个顶点的度是：4 1 = 3 。 n g 1 图1 1 四个顶点的完备图 第一章圈的同构判定问题的简介 搠阶全图，是图中任一对相异顶点之间均有川条边相连它的每个顶点的 度是m ( n 一1 ) 。如图1 2 所示。图g 是具有四个顶点的二阶全图。可见图中每 个顶点的度是2 ( 4 - - 1 ) = 6 。若m = l ，则上图便是完备图，即完备图是m 阶 全图当m = l 的特殊情况，如图1 1 所示。 g 2 图1 2 四个顶点的二阶全图 定义1 3 邻接矩阵 一个具有个顶点、e 条边的无向图g ，可由图g 的顶点集v 中每两点问 的邻接关系唯一决定。其对应的矩阵d = d , j 是- - 个n n 阶方阵，叫做邻接矩 阵。 其中： 砘= 1 v ，和v j 邻接( i = l ，2 ，：j = 1 ，2 ，n ) d i j = ov i 和v j 不邻接( 或i = j ，且无自环) 肛摊uai 1 0 1 0引0 第一章图的同构判定问题的简介 虬n g 图1 - - 35 点连通图 观察上例，可见邻接矩阵有以下特点： ( a ) 一个无向图g 当且仅当没有自环时，其邻接矩阵是左对角线元素均为0 ， 以左对角线为对称轴的对称( o ，1 ) 矩阵。( 若v i 点出现自环，则西i 等于顶点v ，出 现自环的个数。) ( b ) 邻接矩阵d 的每- - f t 或每一列中的“l ”的个数之和，是图g 中相应顶 点的度。 ( c ) 邻接矩阵的行和列是按相同的顶点次序排列，置换矩阵中的各行和相应 的列，即重新安排顶点次序。于是，当且仅当有以下关系式： d ( g 2 ) = r - l d ( g o r ( r 为置换矩阵) 两个没有平行边的图g l 和g 2 是同构的。 事实上，邻接矩阵是由标定图作出的，若d l 和d 2 是相应于同个图g 的 两种不同的标定的邻接矩阵，则必存在一个置换矩阵r ，使得 d 2 = r - i d i r 。 ( d ) 当且仅当图g 的邻接矩阵可以分块为 即，一p 导矧 时，图g 是一个具有g 1 和g 2 两个连通片的非连通图。d ( g 0 是对应连通片g 的邻接矩阵，d ( g 2 ) 是对应连通片g 2 的邻接矩阵。 第一章图的间构判定问题的摘介 2 图的同构问题简介 在描绘一个图的几何形状时，由于顶点被安排的位置以及线段的形状等的 不同，从而使得两个相同的图，可以看上去却完全相异。在这种情况下，我们需 要有一个办法能够确定即使两个图的画法和编号不同，它们实际是相同的。 例如，观察图l 一4 所示的图g l ，g 2 和g 3 ，我们注意这三个图全是6 条边 和4 个顶点，而且每个顶点的度均为3 我们也看到a 和c 的外形是相同的，而 在形式上和g l ，g 3 完全不同。 新 l a ) 图l 一5 图l 一4 变形 i b ) 如果去掉标号上的一点，则其与图0 4 和g l 完全相同。另外，考虑图g 3 ( 如 图i - - 4 ( c ) ) ，把点、边按以下规则交换，则可得到和g 1 一样的形式- 第一常图的同构判定问题的简介 对于顶点： 寸v ? ”2 _ u 吩_ 巧 吩吩 则得图g 5 ( 见图1 5 ( b ) ) 。如把“妒号去掉，则g 5 ( 见图i 5 ( b ) ) 将变成o ( 见图l 4 ( a ) ) 。 综上所述，我们在下面对图的同构进行定义。 定义1 4 同构 若图g l 和g 2 同构，则必须满足下列条件： ( a ) 它们有相同数目的顶点： ( b ) 它们有相同数目的边； ( c ) 它们的点和点、边和边之间一一对应，并保持点和边之间的关联关系不 变。 显然，在定义l 一4 里，条件( c ) 意味着条件( b ) 和( a ) ，如果条件( a ) 、( b ) 不能 满足，就无须进一步考察条件( c ) 。事实上，条件( c ) 是一个充分和必要条件，而 条件( a ) 、( b ) 仅是必要条件。( 有的作者把同构口q 做全等。) 铡1 2 让我们观察图1 4 中的g i 和g ，显然，同构的三个条件均能得到满足两 图的顶点和边的关联关系，列表如下： “岛幽，函如以 呻 哼 1 、 哼 斗 呻 。毛。吃。岛。气。 边于对 6 lg 3 一 # 1 一旷 第l 行 h 一气“ 辱一一 毛 吩、 第2 行 吃一e 之_一e ；i e 5 一一号： 打e 3 卜 _ p - 一 第3 行 v z 一e 5 。、 冬一一口： 2 _ 一飞 第1 行 i ：i 一气- 暑。一一e ； g i 的顶点n 和e l ，自，p 6 相关联，g 3 的顶点v i ”和e 4 pe t le 6 ”相关联，两 点关联的边一一对应，同理可知其它三行的对应关系。由定义可知，0 3 和g ，是 同构的。 从这个例子，可以看出：两图同构，其对应顶点的度数必须相同，这也是必 要的条件之一。 3 图的同构判定算法简介 如果y ( g ) = 以席) 。e ( g ) = ( 日) 和如= 九( 其中v ( g ) 是非空的顶点集， e ( g ) 是不与v ( g ) 相交的边集，而九是关联函数，它使g 的每条边对应于 g 的无序顶点对) ，两个图g 和h 是恒等的( 记为g ：h ) 。显然两个恒等的图 可用同个图来表示，但不恒等的图也可能具有实质上相同的图形。如图l 一6 中的两个图所示一这两个图看起来完全一样，差别在于它们的顶点和边有不同的 第一章图的同构判定问题的简介 标号，图g 和h 不恒等但同构。 d ： g h 图l 一6 同构但不恒等的图 一般说来，两个图g 和h 称为同构，如果存在两个一对一映射日： v ( g ) 斗v ( h ) 和毋： ( g ) = e ( h ) ，使得当且仅当妒。( ( e ) ) = o ( u ) e ( v ) 时 ( e ) = v ：这样一个映射对( 口，毋) 成为g 和h 之间的一个同构。 要证明两个图是同构的就必须证明它们之间的一个同构。下面给出的映射对 ( 0 ，庐) ： o ( v i ) = y ，o ( v 2 ) = x ，a ( v 3 ) = “，o ( v 4 ) = v ，o ( v 5 ) = w 和 妒( p 1 ) = h ，庐( p 2 ) = g ，妒( e 3 ) = b ，妒( p 4 ) = a ， 妒( p ，) = e ，( 口。) = c ，( e ，) = d ，( 8 。) = f 是上图g 和h 之间的一个同构；显然g 和h 有相同的结构，差异只是顶点和边 的名称不同。 3 1 顶点顺序交换法及其改进 两个图g l 与g 2 是同构的，则意味着它们的边、顶点及其关联关系都是一一 对应的。 图形同构问题可以很直观地由邻接矩阵或关联矩阵的排列来解决。两个图 g l 与g 2 同构的充分必要条件就是经过行、列的交换能使它们的关联矩阵及邻接 矩阵相同。但若真的应用这种方法来判定两个图是否同构，在最坏情况下需要1 1 1 ( n 为图g l 与g 2 的顶点个数) 次交换，这在1 1 稍大一些时就无法实现了。人们 显然希望能找到一个精巧的算法来解决这一问题，最终能得到一个多项式算法。 重新排列邻接矩阵及关联短阵的方法在一般情况下是可以得到简化的，这就 是改进后的顶点顺序交换法。例如，如果固g i 与g 2 是同构的，那么一一对应的 第一章图的同构判定问题的简介 顶点只能是那些度数相同的顶点。如果图g i ( g 2 也是同样) 有n ，个关联度为i 的顶 点，那么需要重新排列的运算量就减少至 啊! ，z 2 h h 对于每一个数目i 仅需排列其中n i 个顶点的对应行与列。当比较幸运时。 数量会限n n 很d , 。但是却不能保证这一点，对于图中各顶点度数相同的正则图 就毫无作用。尽管如此，根掘顶点的不同性质来对图进行分解。这毕竟是一个很 好的开端。我们可以再进一步找出能够分辨不同顶点的其它性质，使每组的划分 更细，逐步减少需要重新排列的运算量，得出一一对应的顶点关系。但是尽管出 现了许多精巧的设想，对每一种给出的算法，总能找出使其计算时间不能少于指 数时间的图。 由上述讨论，人们自然联想，能否找出一些图形的不变量来确定两个图的同 构。所谓图形g 的不变量，是指涉及g 的一组数，对于同构的图，则肯定是完 全相同的。如顶点数、边数、秩、零度、连通片和块的数目、顶点的连通度、树 的数目等等。但对于所有这些不变量都存在这种情况，即不同构的图也可能有完 全相同的不变量。因此它们只能告诉我们，当两个图的对应不变量不相同时，它 们是不同构的，却不能保证它们相同时两个图一定同构。我们需要的是一种图形 的完全不变量，当且仅当这两个参数相同时，两个图同构。人们一度咀为图的邻 接矩阵的特征多项式会是一组图的完全不变量，但不幸的是也发现特征多项式与 特征值并不唯一地确定一个图。 与图的同构紧密关联的问题就是对图编码的问题，一个图的一组码是对图的 一个本质的描述，它完全不依赖图是如何标号的。因而两个图同构的充分必要条 件即为它们的编码完全相同。如果能够找到一组完全不变量，可以认为它们即是 一组码。对图的任何一种概括了它的全部信息的描述都将表述为一串符号，而任 何有限的符号都能译成一组整数。我们可以不失一般性地定义编码过程为，图到 一组非负整数的映射m ( m a p p i n g ) 。图g 在m 下的映像将是图的编码，因而两 个图g l 与g 2 同构的充分必要条件则为m ( 6 1 ) = a g 2 ) 。编码的方法在一些图上 已经有效，如树形图、平面图等等。 3 2 一种无向图的同构判定算法：关联度序列法 关联度序列法中作者1 2 】定义了一些新概念：n 点连通予图，n 点连通子图 的关联度，n 点连通子图的关联度序列，顶点合并。 定义1 5珂点连通子图 如果图g 中h ( 1 托 n ，n 为g 的顶点数) 个点以及连接于这n 个点之 9 第一章图的同构判定问题的简介 间的边组成的子图是连通的，那么，这个子图称为图g 的 点连通子图，记为 g ( v 。) ，v 。是这疗个点的集合。 定义1 - - 6甩点连通子图的关联度 在图g 中，与一个h 点连通予图g ( v 。) 相连接的边( 不包括g ( v 。) 的内 部边) 称为关联边。关联边的边数称为g ( v 。) 的关联度，记作d ( v 。) 。 定义l 一7h 点连通子图的关联度序列 若图g 的一点连通予图一共有p 个，则将这p 个一点连通子图的关联度按从 大到小的顺序排列起来所得到的有序集合称为r 点连通子图的关联度序列，汜为 s ( 月) 。 定义1 8顶点合并 将顶点i 句重合，并使原接于i 的边都连接到，再消去这一过程中可能出 现的自环，这样一个操作，称为顶点i 与7 合并。 综合上面介绍的几个概念，可以得出以下凡个定理： 定理1 1设g l 与g 2 是同构图，如果g l 中”个点与g 2 中胛个一对 应那么这月个点合并后所得的新图g t 与g 2 仍是同构图，且原有的点之间保持 一一对应，合并所得的新点之侧保持互相对应。 定理1 2设g 1 与g 2 同构，如果g 。中有一个月点连通子图的关联度为 d l ( v n ) ，那么g 2 中必有一个”点连通子图的关联度与之相同，即 d 2 ( v 。) = d i ( v 。) 。 定理1 3 如果g i 与g 2 同构，g i 与g 2 的i l 点连通子图的关联度序列分 别为s l ( n ) 与s 2 ( n ) ，那么对所有的打都有：s l ( n ) = s 2 ( 以) ，n = 1 2 n - 1 ，这里 是图g 1 或g 2 的点数。 作者【2 l 认为定理3 的逆定理也是成立的，即如果两个图g l 与g 2 的n 点连通 子图的关联度序列都相等，即s ，( n ) = s ，( 仃) ，? = 1 ，2 ，一1 ，那么，g i 与g 2 同 构。因为关联度序列跹脚反映了各个子图层次上的点与边的关系。如果g 】与g 2 在结构上有稍许细微的差别，都将造成某一层次或某些层次的s ( ”) s ：( n ) ，这 与假定条件相矛盾。定理3 及其逆定理可以作为图的同构判据，即如果 s 1 ( 珂) = s 2 q ) ，n = l ，2 ，n 一1 ，则判定g i 与g 2 同构，只要有一个s i ( n ) s 2 ( h ) ，则 立即判定图g i 与g 2 是不同构的。 下面我们举一例子，试用本算法判定图1 - - 7 q 6 g l 与g 2 是否同构。先计算g 与g 2 的蜀( 1 ) - 与s 2 ( 1 ) ，可得s 。( 1 ) = 【3 ，3 ，2 ，2 ，1 ，1 】，s 2 ( 1 ) = 【3 ，3 ，2 ，2 ，1 ，l 】，可见 & ( 1 ) = s 2 ( 1 ) 再计算s l ( 2 ) - 与s 2 0 ) ，得到 0 第一章图的同构判定问题的简介 s l ( 2 ) = 4 ，3 ，3 ，3 ，2 ，2 ，l 】，s 2 ( 2 ) = 【3 ，3 ，3 ，3 ，2 ，2 ，2 1 ，可见s ( 2 ) s 2 ( 2 ) ，因此判定 g l 与g 2 不同构。 g 图1 7 两个不同构的图 3 3 有向图判定算法：出入度序列法 这是一种与上面关联度序列类似的算法，不同之处在于它是用来解决有向图 的同构判定问题，所以这里仍要应用上面方法中的定义l 一5 和定义1 8 ，定理1 1 和定理1 2 ，这里不再赘述。这种算法中涉及的新概念包括：n 点连通子图的 出入度，并点连通子图的出入度序列。 定义1 1 0 一点连通子图的出入度1 3 i 在图g 中，与一个h 点连通子图g ( v 。) 相连接的边( 不包括g ( v 。) 的内部 边) 称为关联边。关联边中方向指向这个子图的边称为入边，方向离开这个子图 的边称为出边。入边的数目称为g ( v 。) 的入度，记作d ，( ) ：出边的数目称为 g ( v 。) 的出度，记作d 。( v n ) 。 定义1 1 1n 点连通子图的出入度序列 若图g 的一点连通子图一共有p 个，则这p 个”点连通子图的出度按从大到小的 顺序排列起来所得到的有序集合称为n 点连通子图的出度序列，记为s 。( ”) ；将这 p 个一点连通子图的入度按从大到小的顺序排列起来所得到的有序集合称为 点 连通子图的入度序列，记为s ，( ，1 ) 。 定理1 4 如果有向图g 与g 同构。g 与g 的n 点连通子图的入度和出度序列 分别为s ( 刀) ，e ( 砷和爿( 功，s o ( 丹) ，那么对任意n 都有s ( 力) = 一( 珂) ， 瓯( 叻= s ：( n ) ，r t = l ，2 ，一l ，这里是图g 与g 的顶点数。 定理i 一4 揭示了同构有向图的重要拓扑性质，作者删认为定理4 的逆定理也 是成立的，即如果两个图g l 与g 2 的i 1 点连通子图的出入度序列都相等。即 s ，( 推) = s z , ( 玲) ，s l 。( h ) = s 2 。( h ) ，h = l ，2 ，| 一l ，那么g l 与g 2 同构。因为入度 和出度序列反映了各个子图层次上的点与边的关系，如果g l 与g 2 在结构上有 稍许细微的差别，都将造成某一层次或某些层次的s ( n ) s ：，( ，和( 或) 凳一章幽的间构判定问题的简介 。( 野) 岛。( ，1 ) ，这与假定条件相矛盾。 定理】一4 及其逆定理可以作为有向图的网构判据，即如果 s 。0 ) = s 2 ，q ) ，s 。( h ) = s 2 e ( n k n = 1 ，2 ，n l 则判定g i 与g 2 同构只要有一个 墨，翻) 品 ) 和( 或) 墨。0 ，是。( 月) 则立即判定g 与g 2 不同构。 3 4 基于h o p f i d d 网络的凰的同构判定算法4 l 基于神经弼络的神经优化是一种能够模拟局部功能的超大规模并行计算，自 从1 9 8 5 年h o p f i c d 和t a n k 两人开拓性她采用h o p f e i l d 神经网络模型对困难的 t s p ( t r a v e l i n gs a l e sm a np r o b l e m ) 这个n p 完全问题进行了研究，取得了传统方 法无法取得的可喜的结果之后，有许多学者应用神经网络的方法求解组合优化间 题。应用h o p f i e l d 网络研究圈的同构问题，始于马颂德1 6 ，陈国良【7 ，8 j 等人。这 秘方法是在文献1 6 8 1 的基础上，通过简化能量函数，并建立相应的数学理论， 给出了一种新的神经网络求解图的同构问题的改进方法，并通过迸一步分析 h o p f i l e d 网络的拓扑结构，给出了电路实现图。 对于两个图g ，g 2 是否同构的问题，首先判断两图的顶点数目是否相等， 边数目是否相等，只要有一项不相等，立即得出g 。与g 2 不同构的结论；潜两图 的顶点数和边数均分趴相等，则构造一个有p x p 个神经元的h o p f i e d 网络，通 过网络运行的结果得出g j 和g 2 是否同构的结论。由于h o p f i e l d 网络的算法是一 种梯度算法有可能求得能量函数的局部极小，即网络有可能运行至不希望的吸 引子或吸引环内，但由予这里所提出的能量函数，当且仅当满足一定条件对达到 能量函数的最小值0 ，因此在网络进入稳态之后，通过判断能量是否接近予0 来 判断该稳定状态是否是希望的吸引子，若不是则重新产生初值并运行网络。这样 循环反复，直到网络进入希望的吸引子，得出g l 、g 2 同构，并由网络稳态输出 g i 、g 2 顶点之间的对应关系；或者网络运行的迭代次数太多，大于事先给出的 门限，得出两图不同构的结论为止。 2 第二章圈的同构判定新方法：电路横= c i 法 第二章图的同构判定新方法：电路模拟法 1 线性电路网络地一般分析方法：节点电压法 节点分析法是以节点电压为电路变量，直接列写独立节点的k c l 方程，先 解得节点电压，进而求得响应的一种网络分析法。 在网络中，任选一个节点为参考节点，其余每个节点与参考节点之间的电压， 就称为该节点的节点电压。习惯上节点电压的参考极性均以参考节点为负极。显 然，节点电压数比节点数少一个。对于具有”个节点的网络，有( 圹一1 ) 个节点电 压。在如图2 1 所示的电路中，若选节点4 为参考节点，则其余三个节点与参 考节点之间的电压v 。v 。v 。即为这三个节点的节点电压。 图2 1 节点电压分析法示例 对于网络中的任意一条支路，如果它与参考节点相关联，则该支路电压或 等于与该支路关联的独立节点的节点电压或差一负号( 视支路电压的极性而定) ； 如果不与参考节点相关联，则支路电压可表示为支路所连接的两个独立节点的节 点电压的差。如图2 一l 所示电路有 v l = v n lv 5 = 一v 2v 2 = v 们 。 v 4 = v “2 一v h lv 3 = v n i v 月，v 6 = v h 3 一v n 2 v i ，v 2 ，v 3 ，v 4 ，v 5 ，v 6 为电导g l ，g 2 ，g 3 ，g 4 ，g 5 ，g 6 上的电压值。 可见，节点电压一旦求得，所有支路电压随之可求出，因此节点电压具有完 备性。另外，与参考节点相连的各支路不能构成闭合回路，因此各节点电压相互 间不受k v l 约束，具有独立性。所以节点电压是一组独立的且完备的电压变量a 第二章圈的同构判定新方法：电路模拟法 为了求出( ，广1 ) 个节点电压，必须列出( 一1 ) 个以节点电压为变量的独立方 程。由于节点电压不受k v l 约束，因此只能根据k c l 和支路的伏安关系建立方 程。由前已知，对于具有n 个节点的网络，除参考节点外有( ，r 1 ) 个独立节点， 各独立节点的k c l 方程是一组独立方程，因此若利用节点电压的完备性以及支 路的伏安关系，将这些k c l 方程中的各支路电流用节点电压表示，则可得n ( n 1 ) 个以节点电压为变量的独立方程，该组方程就称为节点方程，联立求解节点 方程。即可求得各节点电压。以图2 一l 所示电路为例，独立节点1 、节点2 和 节点3 的k c l 方程为 节点l ： 一i 。i + i l + i ，+ i d i 4 = 0 节点2 ：i4一i5一is=0(2-1) 节点3 ： 一i 。2 + i 2 一i 3 一i ，3 + i 6 0 将上式中各支路电流用节点电压表示： f 1 = g 1 v 。l ，f 2 = g 2 v 。3 ， i 3 = g 3 ( v 。i v 。3 ) i 4 = g 4 ( ，2 一v n i ) = 一g 5 v 。2 ， i 6 = g 6 ( v 帕一y 。2 ) 代入式( 2 一1 ) 可得 ( g 1 + g 3 + g 4 ) v m g 4 v 。2 一g 3 v 硒= i ，1 一i ，3i g 4 v 。i + ( g 4 + g s + g 6 ) h 2 一g 6 v 。，= 0(2-2) 一g 3 v 。i g 6 v 。2 + ( g 2 + g 3 + g 6 ) k j = i ，2 + i 。3j 上式就是图2 1 所示电路的节点电压方程，联立求解节点方程，可得节点 电压v m ，v 。2 ，v n 3 。 为了找出系统化地列写节点方程地的方法，将式( 2 1 ) 改写为如下一般形 式： g i i v d l + g 1 2 v n 2 + g i3 v 。3 = f 枷i g 2 l v n l + g 2 2 v 2 + g 2 3 v n ，= i 2 ( 2 - - 3 ) g 3 1 v m + g 3 2 v * 1 + g 扎v 3 = i 州 j 式中方程左边对角线上各项的系数为 g l l = g l + g 3 + g 4 ，g 2 2 = g 4 + g 5 + g 6 ，g 3 3 = g 2 + g 3 + g 6 分别称为节点l 、节点2 和节点3 的自电导，其值分别为与各节点相连的所有支 路的电导之和：方程左边非主对角线上各项的系数为 g 1 2 = g 2 l = 一g 4 ，g 1 35 g 3 l = 一g 3 ，g 2 3 = g 3 2 = 一g 6 分别称为节点l 与节点2 、节点1 与节点3 和节点2 与节点3 的互电导，其值为 对应两节点间的公共支路电导之和的负值。方程右边各项为 第二章图的同构判定新方法：电路模拟法 i i = i ，l i ，f h 2 = 0 ，i m ，= i _ 2 + j ，3 分别为流入各节点的电流源电流的代数和。 由上可得，从网络直接歹l j 写节点方程的觌则为： 自电导x 本节点的节点电压+ 互电导相邻节点的节点电压 = 流入本节点电流源电流的代数和 对于具有n 个节点的网络，若以节点n 为参考节点，则节点方程可一般表示 为： g 1 1 v 月i + g 1 2 v 2 + g 2 t v m + g 2 2 v 。2 + - i - g l ( 一1 ) v 月( 一i ) = f m l + g 2 ) v t 。一1 ) = g 一i ) l v n l + g 扣一i ) 2 v h 2 + + g ( 。一l m 月一1 ) v n ( n i ) = f 帅( 月一l 2 电路模拟法涉及的颟概念 本文对解决图的同构判定问题提出了独特的思路，即将图的同构问题转化为 电路的相同问题，从而得到了两图同构的又一必要( 几乎充分) 条件，在大多数 情况下可有效判定两图是否同构，其算法时间复杂性为o ( 2 n 4 ) 。 由于本文提出的算法是将图的同构问题转化为电路的相同问题，因此将本文 提出的算法称为电路模拟法。在此算法中本文提出了如下新概念：相同电路，图 的伴随电路，全激励，节点电压序列和节点电压序列集，并在此基础上推出了四 个定理。 定义2 1 相同电路： 如果电路n 与n 对应的拓扑图g 与g 是同构图，且n 与n 对应支路上有 相同的元件。那么n 与n 称为相同电路，记为n = n 。 定义2 2 图的伴随电路： 如果将图g 的每一条边均用1 f 2 的电阻元件替代，这样所得电路n 称为图g 的伴随电路( 注意：均用lq 的电阻替代) 。 1 4 g 2 3 图2 2 两个回构图 4 g 3 第二章图的同构判定新方法：电路模拟法 4 n 3 q 3 图2 3 图2 2 中两图的伴随电路 国2 3 中的电路n 与n 对应的拓扑图如图2 2 所示，因为图2 2 中g 与g 为同构图，n 与n 对应支路上对应的电路元件均为1o 的电阻，所以n 与 n 为相同电路。 对于图2 2 中的g 与g 来说，图2 3 中的电路n 与n 分别是g 与g 的 伴随电路，因为电路n 与n 中每条边上的元件均为电阻元件，且元件值为lq 。 每条边均采用1q 的电阻来替代，是为了在不知道待判定图对应边的情况下保证 同构图的伴随电路是相同电路。 根据定义2 1 和定义2 2 可以得出如下结论： 定理2 1 同构图的伴随电路是相同电路。 显然，同构图保证了生成的伴随电路的拓扑结构是相同的，由于每条支路上 添加的都是lq 的电阻，也就保证了两个伴随电路中对应支路的电阻值楣等，所 以同构图的伴随电路是相同电路。例如，图2 - - 2 中两图的伴随电路就是相同电 路( 如图2 3 所示) 。 定理2 2 同构图的邻接矩阵的行列式值相等。 同构图的邻接矩阵经过定的行列交换之后相等，所以它们的行列式的值也 相等，因为同时交换行列式的行与列并不会影响行列式的值。 图2 - - 2 中的图g 与g 为同构图，现改变图g 中各顶点的顺序，得到图2 4 中所示两同构图： 2 4 2 g 图2 4 两个同构图 图2 - - 4 中g 与g 的邻按矩阵分别为： g 3 第二二章图的同构判定新方法：电路模拟法 l 2 0 2 d 。孤 34 0 o 0 l l lo 2 1 20 其行列式值分别为i d l = 1 6 ，i d 1 = 1 6 。 l d = 2 3 4 l 2 o2 2 o 1o l0 3 1 4 _ 11 0 0 0 2 20 为了应用图的伴随电路来判定图的同构，下面来研究伴随电路的性质。 定义2 3 全激励： 在1 个节点( 在图中，节点称为顶点，下同) 的伴随电路n 中，以节点i 为参考点，在i 与其余珂一1 个节点间分别施加激励电流源1 ，= l ，电流方向都是 从i 指向其余节点，这样一种激励方式称为节点i 的全激励。图2 5 给出了电路 全激励的例子。 ( a ) ( b ) 图2 5 全激励举例 如图所示，图2 - - 5 ( b ) 中的电路就是图2 5 ( a ) 中伴随电路节点4 的全 激励。同理可画出以图2 - - 5 ( a ) 中其它三个节点为参考点的全激励电路。 定理2 - - 3 在相同的伴随电路n 和n 中，对应节点的全激励所产生的节点 电压l l 对应相等。 电路理论告诉我们，相同电路在相同的激励下有相同的响应。所以对应节点 的全激励所产生的节点电压1 1 对应相等。 举一个例子： 图2 - - 3 中电路是相同的电路，对应节点编号为i = i ，i = l ，2 ，3 ，4 ，如以对应 节点l 与l 施加全激励，如图2 - - 6 所示， 第= 带凹的同构判定新方法；电路模拟法 4 n 3 1 f ；：二j 慝 = 嘲 ；：! ； 习= 豳 定义2 4 节点电压序列与节点电压序列集 在伴随电路n 中，将节点i 全激励时的节点电压按从d n 大的顺序排列起来 ( 如有数值相同的节点电压，则把它们排在一起) ，这样所得的集合称为节点i 的节点电压序列，记为s ，并将电路n 中所有的节点电压序列组成的集合称为 电路n 的节点电压序列集，记为s 。= i s , l ，扛1 ，2 ，打。 在图2 - - 6 中节点1 的节点电压序列为s ，= 【1 5 ，2 5 ，2 5 ，节点1 的节点电压 序列s ，= f 1 5 ，2 5 ，2 5 】。同样以节点2 ，3 ，4 作为参考点，可解出两图的所有节点 电压序列s ：，s ，s 。和s 2 ，s 。只。所以图2 - - 3 中电路n 与n 的节点电压序列集 为： = s s 2 s s 4 s = 割 有了定义2 4 ，定理2 3 也可表述为： 在相同电路n 与n 中，对应节点有相同的节点电压序列，n 与n 有相同的 节点电压序列集。 由定理2 一l 和定理2 3 可得如下定理： 第二章圈的i 耐构判定新方法：电路模丰5 【法 定理2 - - 4 若g 与g 同构，则它们的伴随电路n 与n 中的对应节点有相同 的节点电压序列，n 与n 有相同的节点电压序列集，即晶= 乱。 显然这一定理是两图同构的又一必要条件，根据定理2 4 得出电路模拟法 的基本思路： 首先求出待判定的图的伴随电路的节点电压序列集，若伴随电路n 与n 的节点电压序列集不相等，则图g 与g 不同构：若s 。= s 。 则g 与g 可能同构，需进一步判断。 在相同度数的点集内，若两图中存在两点对应的节点电压序列唯一 相等，则这两点的对应关系可确定，对于两图中几点对应的电压序 列相等的情况，可留待后面进行处理。按照两图中已经确定的对应 点重新排列关联矩阵d 和d ，若d = d ，可判断g 与g 同构，否 则对于剩余不确定点的顺序进行重排，并依此次序重排d 和d ，判 断g 与g 是否同构。 电路模拟法的具体实现步骤将在下一章详细叙述。 9 靖三章电路模拟法的算法实现 第三章电路模拟法的算法实现 有了前章的理论准备，本章提出图的同构判定算法电路模拟法，并详细 叙述该算法的实现步骤。 对待判定的两图g 与g 作出如下几个假设： 首先假设g 与g 满足同构的三个必要条件： ( 1 ) 顶点数相同 ( 2 )边数相同 ( 3 )相同度数的顶点数相同 如果o 与g 不能满足上述关系，则可以立刻判断这两图是不同构的，而这 三个条件又非常容易检验，所以在本文中假设等待判定的两图满足同构的上述三 个必要条件。 同时假设g 与g 是连通的，因为对不连通的图，可以分别对各连通子图进 行判定，若各个连通子图皆为1 1 同构则可判定两图同构，否则即可判定两图 不同构。 假设g 与g 不含自环，如含有自环，后面再作处理。 假设0 与g 含有n 个顶点，b 条边，顶点的编号分别为1 ，2 ，”：l ，2 ，”