论文部分内容阅读
图的交叉数是在近代图论中发展起来的一个重要概念,主要研究如何把图画在一个平面上,使其交叉的数目最少。通常这项研究都采用纯数学方法证明。然而,确定一般图的交叉数是一个NP-完全问题,因此,到目前为止有关交叉数的结果比较少,仅限于一些特殊图和简单图的交叉数.甚至于在许多情况下,试图找出图的交叉数的一个好的上界或下界也很困难。本文运用组合方法和归纳思想以及反证法,确定了一些特殊图类与路的笛卡尔积的交叉数,并且研究了联图的交叉数,还探讨了将图画在胎面上的交叉数问题,求出了K4,n在胎面上的交叉数等。
第一章较为详细地交代了交叉数的起源,交叉数研究的理论及实际意义,以及这项研究工作在国内外发展的动态.同时还简要介绍了本文的写作背景,将要解决的问题和文章的创新之处。
第二章对与交叉数有关的一些基本概念和性质进行了解析,同时介绍了阅读本文所需要的预备知识,并介绍了在后续文章中将会出现的定义、记号以及常用到的一些性质.对于部分使用较少的概念放到具体的章节中来交代。
第三章着重研究了与笛卡尔积交叉数有关的问题,确定了两类具体图与路Pn的笛卡尔积的交叉数,分别是完全2-部图K2,m与8阶循环图C(8,2)。
第四章探讨了与联图有关的交叉数。一方面,在假定zaurankiewicz猜想成立的基础上得到了圈与路的联图的交叉数;另一方面,计算出了一类特殊图与一个点的联图的交叉数。
第五章讨论了如何把一个图画在胎面上,使其交叉的数目最少,同时计算出完全2-部图了k4,n在胎面上的交叉数。上述内容充实和发展了图的交叉数的研究成果,并为交叉数的研究提供了新的方法和思路。
最后一章简要地介绍了作者今后研究的方向和重点,同时指出了一些有待解决的问题。