论文部分内容阅读
图的交叉数是在近代图论中发展起来的一个重要概念,起源于19世纪五十年代,是拓扑图论中的前沿问题。它主要研究图在一个平面或曲面上最优画法下的最小交叉数目,是图的非平面性的一个重要参数。由于其在电路板设计和生物工程DNA图示等领域的广泛应用,吸引着众多国内外的专家和学者的关注与研究。但Garey和Johnson已确定一般图的交叉数是NP-完全问题。因而,到目前为止,有关图的交叉数方面的研究结果较少。但在一些特殊图类和简单图的交叉数方面的研究结果还是比较丰富的。 本文主要确定了一个不连通六阶图和特殊的六阶图分别与孤立点、路及圈的联图的交叉数并给予证明。 本文主要结构如下: 第一章:绪论,简述图的交叉数的起源及应用,介绍了图论及图的交叉数的研究背景及本文的结构。 第二章:给出本文用到的图论的一些基本的概念,以及在后文中常用的性质、引理。 第三章:不连通六阶图与孤立点、路及圈的联图的交叉数的确定及证明。 第四章:特定六阶图与孤立点、路及圈的联图的交叉数的确定及证明。 第五章:总结本文和展望未来工作。