算法

维普资讯

第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同 …… 此处隐藏：5090字，全部文档内容请下载后查看。喜欢就下载吧 ……