无向图同构的判定研究

• 作者: 施键兰
• 来源期刊: 软件
• 学科: 数学
• 关键词: 无向图 同构 图同构 关联矩阵
• 年，卷（期）: 2018,（11）
• 所属期刊栏目: 基金项目论文
• 页码范围: 64-67
• 页数: 4页
• 分类号: O157.5
• 字数: 2153字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6970.2018.11.015

摘要

在图论中,图同构是一个非常重要的问题,是一个N-P问题,在现实中有非常广泛的应用.根据许多的研究结果表明,这类问题应该有多项式时间复杂性的算法.只要其中一个问题能够解决,其他的问题都能够迎刃而解.本文针对无向图,根据图和图之间的关联矩阵,提出了一个实用的算法.在度数相同的顶点范围内,利用图的相邻顶点的度数序列,讨论其对图同构的影响.该算法降低了时间复杂性,具有一定的应用价值;但也有局限性,在判定的时候有一定的拒绝率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	施键兰	福建农林大学东方学院	17	37	4.0	5.0