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