算法

维普资讯

第4 5卷第 4期2 0年 8月 06

复旦学报 (自然科学版 )Junlf ua n e i N tr c ne o rao F dnU i rt a aSi c) v sy( u l e

VO . 5 No. 14 4 Au g.2 06 0

文章编号： 4 77 0 ( 0 60—4 00 0 2—14 2 0 )40 8—5

任意图同构判定及其应用李锋，韬陆(复旦大学电子工程系，上海 20 3 ) 0 4 3摘要：立了任意图的伴随电路模型，建使用电路分析方法求解伴随电路，通过解出的节点电压来确定原图拓

扑结构的对应顶点，由此提出了可应用于任意图的同构判定算法 .并 关键词：图论；任意图；同构；伴随电路；算法复杂性中图分类号： 17 6 O 5 .文献标识码： A

图的同构判定问题是图论学科中的基本问题之一 .所谓图的同构，就是两个图的结构完全相同.有人

试图用图的一组不变量来确定图的同构，如回路数、树数、连通片数等，这些尝试都归于失败，因为不同构

的图也会出现完全相同的不变量，有人曾经认为图的邻接矩阵的特征多项式和特征值可能是图的同构判据，结果依然失败了，因为不同构的图也可能有相同的特征多项式和特征值.多年来，人们一直在寻找一种有效的同构判定方法[5, 1]因此图的同构判定依然是值得探索的重要课题 . -本文将任意图的同构问题转化为电路相同问题，从而得到了任意图同构的又一更为严格的必要条件， 在大多数情况下可有效判定两图是否同构 .

1任意图的同构所谓图 G与G同构， 是指两个图的拓扑结构完全相同，即它们的顶点之间保持一一对应，边之间保持一对应，而且对应顶点与对应边之间保持相同的连接关系，记为 G G . 本文讨论的任意图中，可以包含无向图，有向图，带权图以及由它们组成的混合图.混合图中，边可以 是有向的，也可以是无向的，可以是带权的，也可以是不带权的.在此定义下，其它图均是它的特例 .不失一

般性，以下的讨论均针对混合图.

用 E表示有向边集合， 0 d E表示无向边集合.从顶点指向的有向边用[,表示， 其权值用叫表示( 若无权值则规定叫=1. )顶点与之间的无向边用 (, ) 表示，其权值用 m表示， 对无向 边显然有 m=m ( 若无权

值规定 m:m ) j=1 .定义 l任意图的邻接矩阵具有个顶点的混合图，其邻接矩阵 D是×阶矩阵，阵中元素 矩为

fw0, 2…, ( 1wo,叫； j, ,, mi m 2… m咖)[, 1 1 0[,

∈ E (, ) E, d ∈ 0 U E (, ) E0 d n;

其中， k和P分别表示k重有向边和P重无向边，权值叫与 m按从小到大顺序排列. 玎如果和间仅有条权值为 1的有向边， 指向，叫=l w 0由则 , j= .一

根据以上定义， G与 G同构的充要条件是它们有相同的邻接矩阵， D=D . 即

定义 2顶点与 a条无向边，十y条有向边相接( 表示背离顶点的有向边， 其中 y表示指向顶点的有向边)亦即顶点的无向边度数为 a,,有向边出度为，人度为 y,于是该顶点的度数集=

{,, . a y} 收稿日期： 0 51—5 2 0—21作者简介：李锋 (9 6 )男， 1 4一，教授，士生导师；陆博

韬( 9 1 )男， 18一，硕士研究生

算法

维普资讯

第4期

李

锋等：任意图同构判定及其应用

以上定义不失一般性地包含了所有可能的图， i当=J时[,] (, ) 或 表示的就是一个自环，特别地，自环的情况将在算法部分末尾加以说明，带因此下面讨论的任意图建模将暂不考虑自环情况 .

如图 1中的混合图 G与G,按上述规则它们对应的邻接矩阵分别是 D与D . 11

2

3

4

1;

2。

3。

4

() (1 ( ) 0;) 0 () (; 0 1)

(1;) (1;)

( ) (1 ( ) 0;) 0 ( 1 () (;;) 0 1 ) ( 1 ( 1 (1;);); )

(1;) (1;) () 0

2 (1 ;) D= 3 () 0

(; () (,;) 2 ) 0 12 1

( ) (; ( ) (,;) 0 2 ) 0 12 1

图中有 4个顶点，邻接矩阵是 4×4阶矩阵，在顶点 3 到顶点 4之间有一条权值为 2的有向边，一条无权值的有向边，一条无权值的无向边，于是 d4 12 1 . 3=(,;)显然这里D=所以这两个图同构 . D,本例中的两个图对应的顶点刚好是 1’2’ 3’ 4’但一般而言，—1

,—2,—3,D,—4待判定,

④

图顶点对应关系是未知的，同构判定正是要找出这样的而= 1 2 3 4 对应关系.一个原始的算法是，先写出 G与G的D与D, , ,,,

()G a

()G b

然后调整 D的行序和列序 (的交换与列的交换)如能 行，使 D=D, GC G,则 O如所有可能的行交换与列交换都不

图 1任意图同构的例子Fg. I mop i o ri ay g a h i 1 s o r hs fabt r r p s m r

能使 D=则判定不同构. D,所有可能的行的交换与列的交换可能意味着行与列的全部排列，最坏情况下需要进行！次行与列的交换(为图的顶点数 )显然这是指数时间复杂性的算法， .不是一个高效算法 .

2任意图的伴随电路和全激励定义 3如果电路 N与N对应的拓扑图 G与 G是同构图， N与 N对应支路上有相同的电路元 且 件，那么 N与N称为相同电路， 记为 N=N . 定义 4将任意图 G的边用电导替代，电导为该边的权值 W ( m, 或 对有向边按其方向加上并联

电流源，电流为该边的权值 W ( m )这样所得电路 N称为 G的伴随电路 .或 ,伴随电路中电流源是与电导并联的，需要将电流值设为该边的权值 (即电导值)这样电流源和电导才，能对应起来，唯一的确定一条有向边，而没有对应电流源的电导，则表示一条无向边 .显然，定义 4建立按的伴随电路与原任意图的对应是唯一的. 定理 1同构图的伴随电路是相同电路 . 图1中的 G与 G对应的伴随电路如图 2 所示，中为避免电导值与电流源值混淆，其图中电流源电流

值后加上符号“’”,显然 N与N是两个相同电路 .由定义 4及定理 1判定两个图是否同构就等，价于判定两个伴随电路是否相同.这样图的同构问题就转化成了电路的相同问题 .

定义 5全激励在个节点(电路的节点即 . 拓扑图的顶点)的伴随电路 N中，以节点 i为参考点， i在与其余一1个节点间分别施加激励电流

④

源，=1电流方向都是从 i ,指向其余节点，这样一种激励方式称为节点 i的全激励 . 定理 2相同的伴随电路 N和 N, 对应节点的全激励所产生的节点电压对应相等 .()N a ()N b

图 2伴随电

路Fg. C n o tn i ut i 2 o cmi tc c i a r s

根据电路理论，相同电路在相同的激励下应有相同的响应.所以相同伴随电路 N与N对应节点的全激励所产生的节点电压必然一一对应相等 . 这里以图 2中电路为例，如在节点 l 1以全激励，,与 施。如图 3见第 4 2所示 . ( 8页)

算法

维普资讯

复旦学报(自然科学版)

第4 5卷

列出和求解这两个电路的节点电压方程，从结果可以看出，各节点电压对应相等 .V2= v2= 1 3 7 8, . 7 V3= V3一= 1 0 8 9。 . 8 V4= V4,= 1 6 2 2 . 2

定义 6节点电压序列与节点电压序列集在伴

随电路 N中，将节点 i全激励时的节点电压按增序排列起来(如有数值相同的节点电压，则把它们排在一

起 )这样所得的有序集合称为节点 i的节点电压序，列，记为 S,并将 N中所有的节点电压序列组成的集合称为电路N的节点电压序列集，记为 S=[ ,i N S](:12…, .,, )

在图 3中节点 1和节点 1的节点电压序列分别 为2 3 4

() a N

()N b

图 3节点 l 1) (全激励的伴随电路Fg 3 F lec ai f o cmi n r ia n d ( i. ul xi t no no t t i ut t oel 1)— t o c a cc

S=[.7,.8,.2] 1 13 7 10 89 1622, 82 3 4

S,[.7,.8,.2] 1= 13 7 1089 1622 . 8 定理 3若 G与G同构， 则它们的伴随电路 N与 N中的对应节点有相同的节点电压序列，与 N N有相同的节点电压序列集， S即 N=S, N.

证明

因为 G与G同构， 它们的伴随电路 N和N是相同电路，而相同电路对应节点的全激励所产

生的节点电压对应相等，于是 N与N中的对应节点有相同的节点电压序列，与N N有相同的节点电压序列集， S=S即 N

这一定理是本文将要讨论的算法的基础，是两图同构的又一更为严格的必要条件 . S≠S,图若 N N, 则G与 G不同构； S=S, G与 G可能同构. 若 N N,则 在可能同构的情况下，有两种情况：若 S① N中没有相

同的节点电压序列，则对应顶点全部被确定；若 S② N中

有相同的节点电压序列，只有这部分节点电压则序列的顶点对应关系未被确定.对情况①,按确定的对应顶点重新排列 D, D=D, G与 G同构，如则 否则不同构 .对情况②,按确定的对应顶点重新排列 D,对部分尚未确定的对应顶点， D中相应行与列作对

所有可能的排列并与D作比， D=D则 G与 G同构，较若 否则不同构.

3同构判定算法假设待判定的任意图 G与 G满足同构的 3 个必要条件：顶点数相同；边数相同；具有相同度①②③数集 J;【的顶点数相同( J见定义 2;;【 )则因为这 3个条件是非常容易检验的，如不满足，即可判定 G≠G . 假设 G与 G是连通的， 因为对不连通的图，可以分别对各连通子图进行判定. 设 G与G含有个顶点，条边， b顶点编号分别为 12…, 1,, .,,, 2…, 在上述假设下，提出图的同构判定算法如下 .

第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 3 5 6 l 4丁 一

S 1=[,,,,, j S,=[,,,,, J 12 345 6, 2 12 3 4 5 6

则两图中顶点的对应关系为 1 2—3, 4 5 6 7 —2, 3—5,—6,—1,—4,—7.

算法

维普资讯

第4期

李

锋等：意图同构判定及其应用任

/NH2.

N-￣ -,

I H一

H N一

\\ N

C\ N一

H 一N C一一 m咄藤 C H一

C1\ H/

\

⑩

() b

图 5分子结构对应的拓扑图Fg. C rep n igtp lgclg a h fmoeua tu trs i 5 o rs o dn o oo i rp so l l sr cu e a c r

算法

维普资讯

复旦学报(自然科学版 )

第4 5卷

图5是含有 1个顶点，1 9 2条边的混合图.在这样的拓扑结构上运用本文所述的方法，可判得 () a与

() c两图不同构，a与( ) () b两图同构，两组判定耗时均小于 00 PV30G z内存 1 B, .5 ( I . H, s )可见该方法是 G高效的. 事实上， 5 a和() 2 6二溴一. 135图 () b是，. 4氯一，,三氮杂苯，而图 5c是 24二溴.. 135 (),. 3氯.,,三氮杂苯，

分子式都是 C】】 5 Ir, 1 2 CB2但具有不同的分子结构. H N 本文将电路理论运用于图论中，电路元件的物理性质与任意图的拓扑结构对应起来，将建立了伴随电路，从而确保电路计算的结果能高效的寻找同构任意图的可能的对应顶点 . 图的同构问题属于 N完全问题， P j要彻底解决这个问题目前尚无可能，但本文对这个问题提出了比 已有算法更好的算法 .该算法对大多数图是快速有效的. S当Ⅳ中无相同的节点电压序列时，绝大多数时间是用于解线性方程组，如果图有个顶点，则节点电压方程的阶数是一1伴随电路是线性直流电阻 .

电路，因此节点电压方程是一1阶的线性代数方程组，求解该方程组，其时间复杂性为 0(一10 . ( ))本算法至多需要求解 2个伴随电路，因而时间复杂性至多为 O(一10<o( )所以在大多数情况 ( )) .下本算法是一个多项式时间复杂性算法. S当中含有相同的节点电压序列时，只有部分顶点无法确定对应关系，此时仅需调整这部分顶点在 D中的排列顺序， 所以，在最坏情况下，本算法比盲目交换 D中序列 的算法也要优越得多.参考文献：[]李 i锋，晓艳 .李图的同构判定算法：关联度序列法及其应用[]复旦学报 ( J.自然科学版 )2 0,0 3:1—,0 1 4 ( ) 383 5 2 .

[]李 2

锋，慧亮 .向图的同构判定算法：商有出入度序列法[]应用科学学， 0, () 2820 J.报 2 22 3: 5— . 0 0 6

[] G r M, gii Sri . x c

a dapo i t gahmaci s gr d m l J .E E T a P t 3 oi Mag atL E at n rxmae rp t n ui o wa s[] I E rm a— n M, p hg n a n kt nAnl c ne,0 5 2 ( ) 101 1 . e a hIt l2 0,7 7:10—1 1 r Ma l

[]许 4

进，军英，张保

铮.基于 H pe网络的图的同构算法[ . ofl id J电子科学学刊， 9, (2: 1— 1] 1 61 1) 161 . 9 8 2

[] C ahaV, aePM, oe A pi t n f rpster l r h 5 hcr Ghr Mor M. p lai so ah oya oi ms[ . w r . l ve ot J c o g h g t M]Ne Yok Es i N r e r hHol d,9 9. l n a 17

[] K r Reaii ya n mb aoi rb ms[ . e Y r:Peu Pes17: 38 . 6 apR M. dc l mogc i tr po l bi t o n a l e M] N w ok l m rs,9 2 8—5 n

Io r h s J d me to b ta y Gr p sa d IsAp l a in s mo p im u g n fAr ir r a h n t p i to cL e g. U T o I n L a F

( eat n l t nc n ie ig, u a iedy,h n h i 0 4 3 C ia D p r t fEe r iE gne n F d nUnvr t S a ga 0 3, hn ) me o co r 2

Ab t c:A e c n mi n ic i mo e o r i a y g a h i u d d Th i u ta a s t o sd t let e sr t a n w c o o t tc u t d l fa b t r p sf n e . ecr i n l i meh i u e o s v h a r r r o c y s d s o

cruta d n a otgso tie eue oacran tecrep n ign e ft eo gn ltp lgcl a h . ae i i, o l l e ban a sd t seti h rs o dn o so h r ia o oo i p B sd c n d v a d r o d i ag s r o hs d e,n a oi m rd tr nn h o rhs o r i ayga h

rp s . n timo la l rt f eemiig tei mop i g h o s m fabt r p i p o e r r s s o d Ke wod:ga h ter rbtayga h smop i;c no tn i ut loi m o lxt y r s r p h oy;a i r p;i r r o rhs m o cmi t ri;agrt cmpe i a cc h y