图同构中的一类顶点细分方法-软件学报.pdf

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@ Journal of Software, Vol.18, No.2, February 2007, pp .2 13−219 http://www.j DOI: 10. 1360/jos1 80213 Tel/Fax : +86-10 © 2007 by Journal of Software. All rights reserved. ∗ 图同构中的一类顶点细分方法 1+ 2 邹潇湘 , 戴 琼 1( 国家计算机网络与信息安全管理中心,北京 100029) 2( 中国科学院 软件研究所,北京 100080) A Vertex Refinement Method for Graph Isomorphism ZOU Xiao-Xiang1+, DAI Qiong2 1(National Computer Network and Information Security Administration Center, Beijing 100029, China) 2(Institute of Software, The Chinese Academy of Sciences, Beijing 100080, China) + Corresponding author: Phn: +86-10 E-mail: zxx@ Zou XX, Dai Q. A vertex refinement method for graph isomorphism. Journal of Softwar e, 2007,18(2) :213−219. /1000-9825/18/213.htm Abstract: 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. Key words: graph isomorphism; exact graph isomorphism; partition; stable refinement; vertex invariant 摘 要: 提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该 方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基 于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同 构算法,能够降低所需比较的顶点数,达到快速有哪些信誉好的足球投注网站的效果. 关键词: 图同构;精确图同构;划分;稳定细分;顶点不变函数 中图法分类号: TP301 文献标识码: A [1]