摘要
针对无向图的同构判定,提出一种改进的电路模拟法。该算法在原电路模拟法的基础上,通过添加1个参考节点,从而使原来需求解2n个n-1阶的线性代数方程组变为求解2个n阶的线性方程组(n为图的顶点数)。与原有算法相比较,算法复杂度大大降低,对于大规模图的同构判定具有明显的优势。
The problem of determining isomorphism of non-directional graph is solved through the method of circuit. Based on the circuit simulation method, a new method is proposed. It is realized by adding an extra node, so that solving 2n linear system of equations of order n-1 transforms into solving 2 linear systems of equations of order n. Compared with the existent approach, the complexity of the proposed algorithm in this paper is much lower, and this will be an advantage in determining isomorphism of the large graphs.
出处
《信息与电子工程》
2011年第4期478-482,共5页
information and electronic engineering
关键词
无向图
同构判定
电路模拟法
算法复杂度
non-directional graph
isomorphism
circuit simulation method
algorithm complexity
