论文部分内容阅读
图论是数学的一个分支,它以图为研究对象,其中图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。
现代图论研究的主流方向是有向图,在有向图的研究领域中,有向图的Hamilton性质是有向图研究的核心内容。有向图的Hamilton圈问题可以看作是Euler环游问题的一个延续,但是到目前为止Hamilton图的非平凡的充分必要条件上没有找到,它是图论中尚未解决的主要问题之一。一个多世纪以来,人们从不同的角度对这个问题进行研究得到了很多判断Hamilton图的充分条件,例如著名的Ore定理、Fan-型条件,以及Chvatal于1972年用图的度序列判断Hamilton图的一个充分条件(并且给出了一类度极大的Hamilton图)。竞赛图是一类非常有用的有向图,对于它的Hamilton性的研究有着十分重要的意义,二部竞赛图是竞赛图中比较典型和特殊的一类,研究它的Hamilton性质也具有很重要的地位。
本文主要是对二部竞赛图Hamilton性质进行研究,在王建中提出二部竞赛图为Hamilton图的一个新充分条件及李桂荣提出二部竞赛图为Hamilton图的充分条件等前人所研究的主要结果的基础上,得到一系列Hamilton二部竞赛图的充分条件。此外,还对一些特定的二部竞赛图进行研究,找出它的圈所具有的性质。
本文包含四个章节:
第一章概述图论研究的历史,提出本文所做的工作。
第二章介绍本文中涉及的一些基本的图论概念和术语。
第三章讨论二部竞赛图为Hamilton图的一个新的充分条件。即:如果二部竞赛图满足W(n-3)条件,则T是H amilton图,除非T同构于四种特殊的图类。并且得到的一些推论。
第四章研究了一类特殊的二部竞赛图,并且得到这类图所包含圈的一些结论。