论文部分内容阅读
自Paul Turan于上世纪七十年代提出交叉数的概念以来,研究图的交叉数逐渐成为国际上一个非常活跃的数学分支,吸引了国际上众多的数学家和计算机科学家们的关注,尤其是很多图论专家对这方面进行了深入的研究。然而,M.R.Garey等已经证明确定图的交叉数是一个NP—完全问题。因此,到目前为止有关图的交叉数的结果甚少,其研究前景非常广阔,但其难度也比较大,一直以来进展缓慢。目前,关于图的交叉数研究主要集中在以下两个方面:其一,确定一些特殊图类的交叉数;其二,研究图的交叉数的性质。本文确定了一些五阶图与路的联图的交叉数以及一些六阶图与星图Sn的笛卡尔积图的交叉数。主要研究内容如下:
第一章详细地介绍了交叉数的起源,交叉数研究的理论与实际意义,交叉数在国内外研究情况,同时简要介绍了本文写作背景,以及将要解决的问题和文章的创新之处。
第二章给出一些与交叉数有关的基本概念和性质,同时介绍了阅读本文所需要的预备知识。
第三章确定了4个五阶图与路Pn的联图的交叉数。
第四章着重研究了K2,4与星图Sn的笛卡尔积图的交叉数。
第五章简要地介绍了作者今后研究的方向和重点,同时指出了一些有待解决的问题。