图同构中的一类顶点细分方法  

A Vertex Refinement Method for Graph Isomorphism

作　　者：邹潇湘[1] 戴琼[2] 

机构地区：[1]国家计算机网络与信息安全管理中心,北京100029 [2]中国科学院软件研究所,北京100080

出　　处：《软件学报》2007年第2期213-219,共7页Journal of Software

基　　金：中国科学院计算技术研究所青年基金No.20056600-4~~

摘　　要：提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.In this paper, a vertex refinement method is proposed. The new vertex invariant is defined based on the number of the paths for a given length. A comparison between this vertex invariant and some other general vertex invariants has been made. It is proved that this method is as fine as other methods, and examples are given to show that this method is better than others in some case. This vertex refinement method can be used in graph isomorphism algorithms to reduce the number of mapping between the vertexes.

关 键 词：图同构 精确图同构 划分 稳定细分 顶点不变函数 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]