同构图判定:改进的电路模拟法  

Improved circuit simulation method for testing isomorphism

作　　者：赵愉[1] 李锋[1] 商慧亮[1] 

机构地区：[1]复旦大学电子工程系,上海200433

出　　处：《信息与电子工程》2011年第4期478-482,共5页information and electronic engineering

摘　　要：针对无向图的同构判定,提出一种改进的电路模拟法。该算法在原电路模拟法的基础上,通过添加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.

关 键 词：无向图 同构判定 电路模拟法 算法复杂度 

分 类 号：O157.5[理学—数学]