论文部分内容阅读
图的交叉数是在近代图论中发展起来的一个重要概念,主要研究如何把图画在一个平面上,使其交叉数的数目最少.通常这项研究都采用纯数学方法证明.然而,确定一般图的交叉数是一个NP-完全问题.因此,到目前为止有关交叉数的结果比较少,仅限于一些特殊图和简单图的交叉数.甚至于在许多情况下,试图找到图的交叉数的一个好的上界或下界也很困难.本文运用组合方法和归纳思想以及反证法,确定了一些六阶图和五阶图与n个孤立点的联图的交叉数,并且研究星的笛卡尔积的交叉数. 本文主要结构如下: 第一章:绪论.包括交叉数的研究动态、研究背景及意义和本文拟解决的问题. 第二章:基本概念、性质和引理.主要介绍了研究过程中所需要的预备知识,未介绍的相关内容在文中会有特别说明. 第三章:确定了一个六阶图分别与n个孤立点的联图、星图Sn笛卡尔积的交叉数. 第四章:确定了一个五阶图与星图Sn的笛卡尔积的交叉数. 第五章:确定了一个不连通六阶图与n个孤立点联图的交叉数. 第六章:结语.包括工作总结以及研究展望.