论文部分内容阅读
图的交叉数是在近代图论中发展起来的一个重要概念,主要研究如何把图画在一个平面上,使其交叉数目最少.由于其理论的实用性,吸引着许多学者的关注和研究.但确定一般图的交叉数是NP-完全问题.因此,到目前为止,有关图的交叉数方面的研究结果较少.但在一些特殊图和简单图的交叉数方面的研究结果还是比较丰富的.与此同时,国内外许多学者在研究交叉数的过程中,也得到了许多与图的交叉数相关的性质,比如交叉临界性等. 本文确定了联图S5∨Gn的交叉数,通过用一个图替换另一个图的顶点,构造了一个4正则的交叉数临界图.同时确定了用K4,4,K4,4-e替换另一个图的边得到的图的交叉数. 本文主要结构如下: 第一章:绪论,介绍研究背景及本文的结构. 第二章:本文用到的预备知识和一些基本的概念,以及在后文中用到的定义、性质. 第三章:确定了联图S5∨Cn的交叉数. 第四章:用特殊图替换顶点及边的方法构造了几类交叉数临界图. 第五章:总结本文工作并对未来工作进行展望,提出一些有待进一步解决的问题.