无向无权图同构判别算法

On Algorithm for Isomorphism Identification of Undirected and Unweighted Graphs

首先,分析判别同构图的一种常用实现方法:基于邻接矩阵存储,并讨论其存在的时间复杂度为O(N!).接着,针对两图中结点数、边数、每个结点的度均相同的特殊图形提出无向无权图同构判别的另一算法:采用结点之间距离及关联边进行判别.最后通过实例进行算法测试和比较,证明了该算法是完全行之有效的.

First,a commonly implemented method for judging isomorphism,which is based on the adjacency matrix storage,has been analyzed,and its time complexity（O（N!））has been discussed.Thus in order to solve the isomorphism identification of the undirected and unweighted graphs,which are both the special graphs with the same nodes number,the same edges and the same degree for each node,another algorithm is proposed which adopts the distance and the incident edges between nodes to judge.At last,the algorithm is tested and compared through instances and it is proved that the algorithm is effective.