论文部分内容阅读
图的交叉数是在近代图论中发展起来的一个重要概念,起源于二十世纪四十年代,是图的非平面性的一个重要参数.自Paul Turn提出交叉数的概念后,对图的交叉数的研究渐渐成为近代图论中的一个重要研究方向,它主要研究图在一个平面或曲面上最优画法下的最小交叉数,是拓扑图论中的前沿问题.它的理论在电路板设计(见文献[1])、草图识别以及生物工程DNA图示等领域有广泛的应用,因此吸引了国内外众多专家和学者的关注与研究.但Garey和Johnson已确定一般图的交叉数是NP-完全问题(见文献[2]),即多项式复杂程度的非确定性问题.由于其难度,到目前为止有关交叉数的研究结果并不丰富,主要集中在具有特殊结构的图或小阶图上,这些图多为连通图,不连通图的结果并不多. 本文主要确定了一个特殊六阶不连通图和n个孤立点的联图的交叉数并给予证明. 本文主要结构如下: 第一章:绪论,阐述了图的交叉数的起源和实际意义,介绍了图论及图的交叉数的研究背景及本文的基本结构. 第二章:简述本文用到的图论的一些基本的概念,以及在后文中常用的定义、性质、引理. 第三章:确定了一个特殊六阶不连通图和n个孤立点的联图的交叉数并证明,并总结六阶不连通图常用的证明条件. 第四章:总结本文和展望未来工作.