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

• 作者: 战荫伟 陈伟平
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 图同构 结点距离 距离分层 距离统计 Floyd算法 时间复杂度
• 年，卷（期）: 2013,（6）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 316-318
• 页数: 3页
• 分类号: TP391.41
• 字数: 2551字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2013.06.070

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	战荫伟	广东工业大学计算机学院	53	451	12.0	19.0
2	陈伟平	广东工业大学计算机学院	1	3	1.0	1.0