论文部分内容阅读
本文对图的同构判定提出了独特的思路,即将图的同构问题转化为电路的相同问题,从而得到了两图同构的又一必要(几乎充分)条件。
本文分析了判定图的同构所需要的条件,目前存在的图的同构判定算法以及这些算法的有效性;提出了一种新的同构判定算法,电路模拟法,并介绍了此方法所涉及的新概念,相同电路、图的伴随电路、全激励、节点电压序列以及节点电压序列集;详细介绍了电路模拟法的基本算法以及改进后的算法实现步骤,算法实现的框图,并将本算法与别的判定算法有效性进行了比较;利用电路模拟法对几组图进行了同构判定,证明了本算法的有效性,在大多数情况下都能快速有效的进行判定。
本文从节点电压序列内部的电压值是否相等和节点电压序列之间是否相等两个方面着手确定图的顶点之间的对应关系,因此本文的算法对判定绝大多数图是否同构是有效的且快速的。