免费文档

用矩阵判断无向图同构的几种方法

第 3卷第 6 2期 2 1 1 1年 0 2月

衡阳师范学院学报 J u n lo e g a gNo ma ie st o r a fH n y n r lUnv riy

No 6 1 3 . Vo . 2 De c.2 0 11

用矩阵判断无向图同构的几种方法 张磊,李世群 4 10 ) 1 2 1

(湖南科技大学数学与计算科学学院,湖南湘潭 摘

要:给出了用无向图的邻接矩阵及关联矩阵判断两个图是否同构的两种新方法。

关键词:合同变换;邻接矩阵;关联矩阵;同构

中图分类号:O17 5 5 .

文献标志码:A

文章编号:1 7—3 3 2 1 ) 60 1—3 6 30 1 (0 10—0 90

0引言

,: V,— 使得 (, ) (;∈E当且仅当 ( (, ), 7) f( )∈E1且 (, ) (口 ) 2, f,与 f( ,

到目前为止,于判断两个图是否同构没有一对

f v)的重数相同。不妨对两个图重新标记和标 (i ) 号 . V一{,,设 1 2… ) V一{1 i, i},1 i,… ,f:— k (一1是… )即

般方法,只能用定义判断,时判断很难。文献[]有 I 等讨论了特殊图的同构问题,用矩阵判断图中的有

关问题有利于计算机计算,文[]论了用邻接如 2讨矩阵判断树的问题,文用图的邻接矩阵和关联矩本阵来解决讨论一般无向图的同构问题,方法简洁其新颖,而且便于计算机计算。 本文用 M。表示图 G的邻接矩阵, M (表用 G)示图 G的关联矩阵。没有说明的记号及术语,参见

厂(==

)

由于每个置换必可写成一系列对换的乘积,以, 所 G 的顶点集 V一{,, )经一系列顶点的对换成 1 2…n可为 G的顶点集{,, , i i…i)由之前所述事实: 。交换 一

个无向图 G的两个顶点的顺序相当于 G的邻接

文献[] 3。若第 i与第行对换,行同时, i与第第列 列对换,记一 则。 1用邻接矩阵判断两个图同构首先注意到一个事实:换一个无向图 G的两交个顶点的顺序,当于 G的邻接矩阵 Mc交换一次相 相应的行,同时交换一次相应的列。也

矩阵 M。交换一次相应的行,

同时交换一次相应也的列。从而 MG可经一系列第一种合同变换化为另 一

个图的邻接矩阵 M。。 反之, G( E) G (, 是两个无向图,设 V,与 V E )

且 MG可经一系列第一种合同变换化为另一个图的 邻接矩阵 M。。设 MG为 M。的经过一系列第一,化,种合同变换为:1 i; 2 i; i,这里惫一是一 是一 2…惫一 (

对一个矩阵 A的行作一次初等变换,同时对 A的列作相同的初等变换称为对矩阵作合同变换 E 。

M。的 k,行, i 同时交换对应的列 )这一系列合则

同变换等价于 G的顶点经过相应的顶点顺序交换 成为 G, 从而可知 G( E) , 。 V,竺G ( E )

定理 1两个无向图同构当且仅当其中一个图 的邻接矩阵可经一系列第一种合同变换化为另一个图的邻接矩阵。

推论

若图 G( E) G (, 同构,们 V,与 V E )它

的邻接矩阵分别是 MG MG,,,则在实数域 R上有 () 1 Me与 M。相似;当然特征值也相同), (。

证明若图 G( E) V,兰G。, , ( E )则有双射 收稿日期:0 10—8 2 1-72

基金项目:南省学位与研究生教改重点项目 (G20 A 1 )湖 J 0 9 0 7作者简介:磊 (9 6)男,北廊坊人,士研究生,究方向:群基础理论 .张 18一,河硕研半

用矩阵判断无向图同构的几种方法

相关文档
热门文档
你可能喜欢
  • 图形的面积公式
  • 图形的认识
  • 图形的初步认识
  • 视频矩阵方案
  • 观察图形
  • 图形的个数
  • 需求矩阵
  • 矩阵表
评论