论文部分内容阅读
判断一个图是否有哈密顿路的问题是图论中的一个经典问题,而判断一个图是否能被划分成一些给定数目路的并问题是哈密顿路问题的一个重要推广,后者被称为点不交路的划分问题。路的划分问题在现实中有着许多的应用。而这个问题在一般图中都是NP-完备的,一个可能解决这个问题的方法就是找出哈密顿路或者路划分存在的充分性条件。
本文将对图中路划分存在性问题展开讨论,重点讨论2-连通图和二部图中路划分存在的充分性条件,主要是引入了邻域并型的条件来解决这个问题。
本文的研究内容及成果主要包括下面几章:
第一章:回顾了问题的由来,理论的形成,给出了到目前为止的一些研究成果。
第二章:对文中所出现的定义、概念和符号等给出了说明。
第三章:给出2-连通图中路划分存在的一个充分性条件及其证明。
第四章:给出二部图中路划分存在的一个充分性条件及其证明。
第五章:给出相关结论及未来研究的方向。