论文摘要
Seymour猜想即任何5-连通的不可平面图都含有一个K5剖分,它和Hamilton问题是图论中的二个重要问题。本文通过研究边最小的5-连通图和Hal图（自定义）,得到了有关Seymour猜想的一个重要结论及判断Hamilton圈和Hamilton路存在性的二个充分条件,进一步完善了Bondy和Chva′tal的结论。其中关于Hamilton问题的研究是我们的重点之所在。本文所做的主要工作及相应的研究成果如下:1、研究了边最少的5-连通图,通过考察其去掉任意一边后所得图的4-分割集的性质,得出了一个重要结论,即任何5-连通图都包含一个K5?-{e1,e2}剖分,其中e1,e2为K5中任意二个不相邻的边。2、通过定义一类Hal图,并利用该类图的一些重要性质,证明了对于顶点数大于等于6的简单图,当满足一定条件时,一定存在一个同构于某类Hal图的生成子图,进而得到了二个有关判断Hamilton圈Hamilton路存在性的充分条件,并分别给出了满足这一条件的最小值。另外,在给出主要结果之前,先简单介绍了图论的应用,发展历史和现状,以及研究问题的背景和本文的主要工作,最后还介绍了与我们研究密切相关的一些基本概念和符号。