计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (30): 57-61.DOI: 10.3778/j.issn.1002-8331.2009.30.018

• 研究、探讨 • 上一篇    下一篇

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

侯爱民   

  1. 东莞理工学院 计算机科学与技术系,广东 东莞 523808
  • 收稿日期:2008-06-16 修回日期:2009-03-12 出版日期:2009-10-21 发布日期:2009-10-21
  • 通讯作者: 侯爱民

Necessary and sufficient condition of graphic isomorphism

HOU Ai-min   

  1. Department of Computer Science and Technology,Dongguan University of Technology,Dongguan,Guangdong 523808,China
  • Received:2008-06-16 Revised:2009-03-12 Online:2009-10-21 Published:2009-10-21
  • Contact: HOU Ai-min

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

关键词: 子图同构, 母图同构, 对应点无限衍生技术

Abstract: How to determine the isomorphism of graphs is a difficult problem of graph theory,which is not completely solved so far.S.M.Ulam has proposed a conjecture concerning graphic isomorphism,named graph reconstruction.In this paper a new necessary and sufficient condition of graphic isomorphism is proved which is stated as following: two graphs are isomorphic if and only if their subgraphs are isomorphic and the new vertices as well as their adjancy edges are corresponding with the property of isomorphism.Based on the technique for unlimitedly generating the corresponding pairs of vertices,this condition is proved with the method of mathematical induction.

Key words: subgraphic isomorphism, graphic isomorphism, technique for unlimitedly generating the corresponding pairs of vertices

中图分类号: