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

摘要：

按照同构图的定义判断两个图是否同构，最坏情况下其时间复杂度是O(N！)，当结点数N比较大时，计算速度非常慢，针对该问题，提出一种通过统计结点间距离和按照距离分层，计算同层结点间的关联边数以及关联结点数来研究图中各结点差异的算法，该算法可以给出两个图的结点间可能的对应关系。如果两个图的结点距离数组及对应结点的层结点关联数组不能一一对应，其时间复杂度仅为O(N4)，否则，根据结点间可能的对应关系，避免遍历所有结点序号的交换，计算量可以成倍地下降。

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

分类号：TP391.41(计算技术、计算机技术)

在线出版日期：2013-10-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：316-318