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

摘要：

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

关键词：行码距异或矩阵、行码距同或矩阵、行-行置换、图同构

所属期刊栏目：42

分类号：TP319;O157.5(计算技术、计算机技术)

在线出版日期：2006-08-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：51-54