无向图同构的快速算法  

Fast Algorithm for Undirected Graph Isomorphism

作　　者：侯爱民[1] 郝志峰[1] 胡传福[1] 陆海鹏[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510006

出　　处：《华南理工大学学报（自然科学版）》2011年第10期79-83,共5页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61070033);广东省自然科学基金重点项目(9251009001000005);广东省科技计划项目(2010B050400011;2010B080701070)

摘　　要：规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断;要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使用高效的必要条件筛选同构函数候选集,采用基于子图同构判断超图同构的策略,提出一种新的无需回溯的快速算法,用于降低时间开销,保证判断正确.通过理论论证和实际案例测试,验证了该算法的有效性.The two important methods of distinguishing undirected graph isomorphism,namely the canonical labeling algorithm and the vertex partition algorithm,both have their own disadvantages.Specifically,the former can not work for those graphs which cannot be canonically labeled,and,this latter has to backtrack and try again and again,which results in exponential time cost.For any two isomorphic undirected graphs,new supergraphs can be constructed by adding a new vertex and its incident edges to each graph.The supergraphs are isomorphic if and only if ths neighbors of the new vertexes preserve the isomorphic relation in the original isomorphic graphs.Based on this necessary and sufficient condition,a candidate set of isomorphic functions is selected with the help of an efficient necessary condition.Then,by distinguishing the supergraph isomorphism according to the subgraph isomorphism,a fast algorithm without backtracking is proposed to reduce the time cost and guarantee the distinguishing results.Theoretical and experimental results on some real cases demonstrate that the proposed algorithm is effective.

关 键 词：子图同构 快速算法 规范标记算法 顶点划分算法 

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