论文部分内容阅读
图的交叉数是近代图论中发展起来的一个重要概念,自从上个世纪五十年代初匈牙利数学家Paul turán根据其在一个砖厂碰到的实际难题(Turán’s brick factory problem),从而提出了交叉数的概念以来,图的交叉数逐渐成为国际上一个非常活跃的图论分支,使得很多图论专家对这方面进行了深入研究.
研究图的交叉数不仅具有重要理论意义,而且有较强的现实意义,如超大规模集成电路VLST中的圈布局问题、电子线路板设计中的布线问题等.1983年计算机科学家Garey和Johnson证明了确定图的交叉数是一个NP完全问题,由于其难度,我们能够确定交叉数的图类非常少,在许多情况下,即使找出图的交叉数的一个好的上界或下界也非常困难.目前,很多文献在研究一些特殊图类的交叉数,例如:完全图,完全2-部图,完全3-部图及笛卡尔积图等.本文研究几个连通五阶图与星图Sn的笛卡尔积图的交叉数.
第一章:交代了本文的写作背景,交叉数研究在国内外发展的动态,研究工作的意义以及本文中要解决的问题和创新之处.
第二章:给出一些基本概念和性质,介绍了阅读本文所需要的预备知识,并介绍了在后面章节中会出现的一些相关概念、性质以及常用到的一些引理,而部分使用较少的概念则放到了具体的章节中去交代.
第三章:着重研究了三个五阶图G12、G15、G18与星图Sn的笛卡尔积图的交叉数问题,分别确定它们各自的交叉数为:
1.cr(G12×Sn)=n(n-1),n≥1.
2.cr(G15×Sn)=Z(5,n)+2n+[n/2],n≥1.
3.cr(G18×Sn)=Z(5,n)+2n+[n/2],n≥1.
第四章:提出了研究工作在发展中的一些问题以及作者在以后将致力于前进的方向.