关于图的交叉数问题研究

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 1. 绪论
• 1.1 交叉数问题的起源
• 1.2 基本概念
• 1.3 交叉数问题研究现状
• 1.4 本文结构
• 2. 拉链积
• 2.1 引言
• 2.2 拉链积性质及其证明
• 2.3 拉链积性质在积图中的应用
• m×P_n的交叉数'>3. K_m×P_n的交叉数
• m\e的交叉数下界'>3.1 K_m\e的交叉数下界
• m\e的交叉数'>3.2 K_m\e的交叉数
• m×P_n的交叉数'>3.3 K_m×P_n的交叉数
• m\e×P_n的交叉数'>4. K_m\e×P_n的交叉数
• m-2K₂的交叉数下界'>4.1 K_m-2K₂的交叉数下界
• m-2K₂的交叉数'>4.2 K_m-2K₂的交叉数
• m\e×P_n的交叉数'>4.3 K_m\e×P_n的交叉数
• 3,3、K_2,2,2与星的积图交叉数'>5. K_3,3、K_2,2,2与星的积图交叉数
• 5.1 相关引理
• 3,3×S_n的交叉数'>5.2 K_3,3×S_n的交叉数
• 2,2,2×S_n的交叉数'>5.3 K_2,2,2×S_n的交叉数
• 2,3\e与路、圈的联图交叉数'>6. K_2,3\e与路、圈的联图交叉数
• 6.1 相关引理
• 2,3\e+nK₁的交叉数'>6.2 K_2,3\e+nK₁的交叉数
• 2,3\e+P_n的交叉数'>6.3 K_2,3\e+P_n的交叉数
• 2,3\e+C_n的交叉数'>6.4 K_2,3\e+C_n的交叉数
• 6.5 小结与猜想
• 3,3-2K₂与路、圈的联图交叉数'>7. K_3,3-2K₂与路、圈的联图交叉数
• 3,3-2K₂)+nK₁的交叉数'>7.1 (K_3,3-2K₂)+nK₁的交叉数
• 3,3-2K₂)×S_n的交叉数'>7.2 (K_3,3-2K₂)×S_n的交叉数
• 3,3-2K₂)+P_n的交叉数'>7.3 (K_3,3-2K₂)+P_n的交叉数
• 3,3-2K₂)+C_n的交叉数'>7.4 (K_3,3-2K₂)+C_n的交叉数
• 7.5 小结与猜想
• 8. 两个交叉数递推不等式
• m,n\e的交叉数递推不等式'>8.1 K_m,n\e的交叉数递推不等式
• 4,n\e的交叉数'>8.2 K_4,n\e的交叉数
• 1的交叉数递推不等式'>8.3 G+nK₁的交叉数递推不等式
• 1,3,n的交叉数'>8.4 K_1,3,n的交叉数
• 9. 总结与展望
• 9.1工作总结
• 9.2 工作展望
• 参考文献
• 附录一 攻读博士学位期间发表学术论文情况
• 附录二 致谢