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

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

Elementary Operations on a Matrix to Determine the Isomorphism of Graphs

One helpful way to determine the isomorphism of graphs is to use elementary operations on a graph adjacency matrix so as to transform one matrix into another.Unfortunately the failure of some elementary operations is not able to show that the two graphs are not isomorphic because there may be other operations to show the isomorphism.On the other hand,there are n!possible ways(n is the number of vertices of a graph) to make an exhaustive inquiry for operation.Testing each such operation to see whether the two graphs are isomorphic is impractical and become a NP-complete problem if n is at all large.This paper presents a simple and effective method to determine the isomorphism of graphs.First,a row code XOR distance matrix and a row code AOR distance matrix are computed in terms of the graph adjacency matrix.Second,an identical row-row set between matrices is sought.If such a row-row set exists,then the two graphs are isomorphic.Otherwise they are not isomorphic.Third,an isomorphic function is obtained from the identical row-row set with the property of one-to-one correspondence between vertices of the two graphs that preserves the adjacency relationship.