论文部分内容阅读
图的交叉数问题起源于一个实际应用问题,其理论在电路板设计,草图识别与重画以及生物工程DNA的图示等领域有广阔的应用.国内外许多学者都从事过交叉数问题研究.但是,已经被证明计算图的交叉数是个NP-完全问题.由于其难度,到目前为止有关交叉数的结果并不丰富,且能确定其交叉数的图类基本上结构都比较特殊,故很多方法都无法推广到更一般的情形.有时候,我们就连试图找出一个图的交叉数上界或下界都比较困难.本文尝试用一些新的方法去研究积图、联图等一些典型图类的交叉数.确定了若干积图、联图等图类的交叉数,以及得到了一些交叉数的性质.具体如下:(1)得到了一个拉链积性质,作为性质的一个直接应用,证明了:对于任意包含4个支配点的图G,都有,(2)利用“局部加边法”得到了Km\e的交叉数(m≤12).进而,确定了Km×Pn的交叉数(m≤10),这也就证明了郑文平和杨元生等提出的关于Km×Pn的交叉数猜想对于m≤10成立.(3)Klesc得到了K4\e×Pn以及K5\e×Pn的交叉数.杨元生和杨希武得到了K6\×Pn的交叉数.用与他们不同的方法,我们得到K7\×Pn以及K9\×Pn的交叉数.(4)修改了Klesc常用的收缩手术,证明了cr(K3.3×Sn)=cr(K3,3,n)+ 3n,以及cr(K2,2,2×Sn)=Z(6,n)+6n(5)灵活利用K2,3\e的结构特征,得到了K2,3\e与路、圈的联图的交叉数.证明过程是简洁的.(6)确定了K3,3-2K2与路、圈的联图的交叉数,以及与星的积图的交叉数.虽然用的是“边集划分”法,但巧妙地利用6圈的结构特征,避免了穷举K3,3-2K2的所有画法.(7)运用组合计数方法,给出了两个交叉数递推不等式.作为不等式的应用,确定了K4,n\e的交叉数.并且给出了确定K1,3,n交叉数的一个简单方法.除了以上内容外,本文还比较详尽地综述了交叉数问题研究现状.特别是积图的交叉数研究现状.