基于线性方程组右端向量修改的拓扑图同构判别

Isomorphism identification of topological graphs based on dynamic modification to right-hand vector term of linear equation systems

为了提高拓扑图同构判别速度,借助邻接矩阵动态修改法的拓扑图同构判别思想,即利用素数对拓扑图顶点动态赋值以获得线性方程组解向量的改变,从而找到拓扑图同构的映射关系。为进一步减少计算量,简化判别过程,提出保持邻接矩阵不变,仅修改线性方程组右端向量以获得解向量的改变的方法,给出了该方法的初步理论依据。与邻接矩阵动态修改法相比,该方法无须重新形成邻接矩阵,在每次右端向量修改中省去了形成邻接矩阵的运算量,且判别算法变得更为简单。拓扑图同构判别实例表明,该方法有效、可靠。

A mapping between two topological graphs was established by varying the solution vector of linear equation systems to increase the velocity of isomorphism identification.The variation of solution vector results from a dynamic assignment of primers to vertex of topological graphs.This identification method is similar to the one in dynamic modification of adjacent matrix.The method results in various solution vectors by changing right-hand vector term of linear equation systems under unchanged adjacent matrix in order to simplify the isomorphism identification.Compared with the method of dynamic modification to adjacent matrix,this method reduces a calculation to generate a new adjacent matrix during the modification of right-hand vector term so that it simplifies the algorithm of isomorphism identification.More applied examples turn out that this improved method is effective and reliable.