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

摘要

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