图同构的一个充分必要条件

• 来源期刊: 计算机工程与应用
• 学科: 数学
• 关键词: 子图同构 母图同构 对应点无限衍生技术
• 年，卷（期）: 2009,（30）
• 所属期刊栏目: 研究、探讨
• 页码范围: 57-61
• 页数: 5页
• 分类号: O157.5
• 字数: 7649字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2009.30.018

摘要

图同构的判定性问题是图论理论中的一个难问题,至今没有得到彻底解决.Ulam曾经提出过一个判定图同构的猜想,也称为图的重构猜想.提出了一个新的判定图同构的充分必要条件,即在子图同构的前提下,根据新增顶点及相应关联边的关系,判断母图同构的充分必要条件.基于具有同构关系的对应点无限衍生技术,采用数学归纳法证明了这个充分必要条件的成立.