基于结点间距离统计的无向无权图同构判别  

Undirected and Unweighted Graph Isomorphism Determination Based on Distance Statistics of Vertices

作　　者：陈伟平[1] 战荫伟[1] 

机构地区：[1]广东工业大学计算机学院,广州510006

出　　处：《计算机工程》2013年第6期316-318,共3页Computer Engineering

摘　　要：按照同构图的定义判断两个图是否同构,最坏情况下其时间复杂度是O(N!),当结点数N比较大时,计算速度非常慢,针对该问题,提出一种通过统计结点间距离和按照距离分层,计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法,该算法可以给出两个图的结点间可能的对应关系。如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应,其时间复杂度仅为O(N4),否则,根据结点间可能的对应关系,避免遍历所有结点序号的交换,计算量可以成倍地下降。To determine two graphs are isomorphic or not by the definition of graph isomorphism, at worst, the time complexity is O（N!）. Against this problem, it introduces an algorithm which is based on the distance statistics of the vertices. Vertices are stratified by distance, by counting the numbers of related edges and related vertices of vertices which are isometric. The algorithm shows the difference of the vertices, and points out the vertices correspondence of two graphs. If the vertices distance array and layer related vertices array of two graphs are not one-to-one, the time complexity of the algorithm is only O（N^4）. If they are one-to-one, swap the sequence of the vertices in one graph which may correspond to the vertex in the other graph, avoid swapping the sequence of all vertices, in this condition, the time complexity is reduced by many times.

关 键 词：图同构 结点距离 距离分层 距离统计 FLOYD算法 时间复杂度 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]