一种基于高次幂邻接矩阵hash比对的图同构判定方法

摘要

本发明公开了一种基于高次幂邻接矩阵hash比对的图同构判定方法，包含如下步骤：利用高次幂邻接矩阵计算各长度的图路径信息；用hash函数统计高次幂邻接矩阵中的顶点路径信息；根据顶点的路径信息对候选顶点匹配集进行划分；从而实现2个图的快速同构判定。本发明能够在比对的过程对候选顶点匹配集进行划分，大大地降低了图同构判定的时间复杂度。利用图从局部到全局的特征信息来进行图同构判定适用范围广，在不同类型、不同大小的图同构判定都获得了较高的判定效率。因此本发明具有较高的使用价值。

主权项

一种基于高次幂邻接矩阵hash比对的图同构判定方法，其特征在于：对需要判定的两个具有相同顶点个数的拓扑图G_A和G_B执行以下操作：步骤1、分别获得拓扑图G_A和G_B的邻接矩阵A和B，并且设定邻接矩阵A和B的高次幂邻接矩阵的幂系数初始值k＝1；步骤2、判断A和B是否相等，若相等则判定两图同构并结束操作；若不相等，则向下执行步骤3；步骤3、获取拓扑图G_A和G_B的k次幂邻接矩阵AP^k和BP^k，利用hash函数统计AP^k和BP^k获得各顶点的路径信息；步骤4、根据顶点的路径信息将顶点划分至各个候选顶点匹配集中；步骤5、对各个候选顶点匹配集中的顶点进行检查，若至少有一个候选顶点匹配集中的来自G_A和G_B的顶点个数不相等，则判定两图不同构并结束操作；若相等，则向下执行步骤6；步骤6、根据步骤4中的顶点划分结果，将A和B进行同构变换，获得调整后的邻接矩阵A′和B′，判断A′和B′是否相等，若相等则判定两图同构，若不相等则向下执行步骤7；步骤7、当k满足小于G_A或G_B的顶点个数时，k增加1并返回步骤3；否则，对G_A和G_B中仍然无法区分的顶点，进行枚举匹配，最终判断图是否同构。