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

图的同构判别主要有以下 5类方法(下文中 N为图的结 点数): (1)基于图的邻接矩阵的运算。对一个图中结点的序 号进行交换,同时交换其邻接矩阵中对应的行和列,判断 与另一个图的邻接矩阵是否相同,相同则两个图同构,如 果不同,则继续交换,遍历所有结点序号的交换,如果邻 接矩阵都不相同,则两个图不同构。这种方法虽然是判断 两个图同构的等价条件,但是采用了结点序号的全排列, 时间复杂度是 O(N!)。 (2)基于图的连通子图及其连通子图的关联度序列的角 度观察,计算结点数从 1~N−1 的子图,以及各个连通子 图的度数,从小到大排成序列,因为关联度序列与结点的 顺序无关,根据组合原理,其时间复杂度为指数级 O(2)。 (3)按照矩阵的特征值或者特征向量进行判别,若两个 图同构则有相同的特征向量序列,其时间复杂度为 O(N) 或 O(2N(N–1))。 (4)根据结点与其他点的距离判断,当结点间距离统 计结果不同时的时间复杂度仅为多项式级,但是如果统计 结果一样,就需要交换结点的序号,时间复杂度是 O(N!)。 (5)基于仿生和模式识别算法的同构判别,例如利用 DNA、遗传算法和神经网络等的图同构判别算法,这些 算法主要问题是构造模型的时间复杂度较高。近年来,基 于仿生和模式识别的同构判别算法逐渐增加。 以上方法各有优劣,有些方法在结点数较少的情况下 容易实现,有些方法则能给出图某方面的特性。除了方法(1) 是判断图同构的等价条件外,其他方法在证明等价条件时, 均缺少严格的数学证明。本文针对这些问题,提出一种通 过统计相关参数来研究图中各结点差异的算法。