论文部分内容阅读
图的交叉数问题,起源于二战期间Pual Turán在砖厂碰到的一个实际问题,后来逐渐发展成为了图论学科中非常活跃的一个分支,吸引着大批国内外学者的关注和研究.然而,确定一般图类的交叉数是一个NP-完全问题.因此,到目前为止有关图的交叉数的结果比较少,仅限于一些特殊简单图的交叉数.甚至在许多情况下,试图找出图的交叉数的一个好的上界或者下界也是很困难的.本文运用归纳思想以及反证法,确定了两个特殊图:一个六点图G1与路Pn的联图,以及一个五点图G2与路Pn的联图的交叉数的精确值,并试图研究了关于完全二部图K5,n的一般性质.全文由5个章节组成.
第一章介绍了交叉数的起源,交叉数研究的理论与实际意义,以及目前交叉数研究在国内外的发展情况.同时还简要介绍了本文的主要结构.
第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和预备知识.
第三章得到了图Gj(j=1,2)与路Pn的联图的交叉数.
第四章讨论了关于完全二部图K5,n的一些性质.
第五章给出了本文的总结.