图同构的矩阵初等变换判定及算法设计

• 作者: 侯爱民
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 行码距异或矩阵 行码距同或矩阵 行-行置换 图同构
• 年，卷（期）: 2006,（20）
• 所属期刊栏目: 学术探讨
• 页码范围: 51-54
• 页数: 4页
• 分类号: TP319|O157.5
• 字数: 4502字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2006.20.016

摘要

判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵.不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等.另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题.文章提出了一个简单有效的判断图同构的方法.首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构.最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	侯爱民	东莞理工学院计算机科学与技术系	8	46	4.0	6.0