求解图同构的判定算法

• 作者: 侯爱民
• 来源期刊: 计算机工程与应用
• 学科: 数学
• 关键词: 子图同构 图同构 对应点无限衍生技术 判定算法
• 年，卷（期）: 2011,（16）
• 所属期刊栏目: 研究、探讨
• 页码范围: 52-57,103
• 分类号: O157.5
• 字数: 9511字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2011.16.017

摘要

图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决.受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件:在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件.基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立.设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	侯爱民	东莞理工学院计算机科学与技术系	8	46	4.0	6.0