论文部分内容阅读
图的交叉数问题起源于二战时期PualTurán在砖厂碰到的一个实际问题，后来逐渐发展成为图论学科中非常活跃的一个分支，吸引着大批国内外学者的关注和研究，其理论在电路板设计，草图识别与重画以及生物DNA的图示等领域有广泛的应用.但是，k确定一般图类的交叉数问题已经被证明是一个NP-完全问题.因此，至今为止有关图的交叉数问题的结果还非常少，且已被确定交叉数的图类大多数都是一些比较特殊的图类，故很多方法都不能推广到一般情况.甚至有的时候找出图的交叉数的一个比较好的上界或下界也很困难.本文运用归纳法的思想以及反正法确定了两个特殊图类的交叉数：一个六阶图H与路Pn的联图的交叉数以及一个四阶不连通图G与路，圈联图的交叉数本文一共由五个章节组成。
第一章，主要介绍了交叉数的起源，交叉数研究的理论与实际意义，目前关于交叉数的一些研究现状，同时本章节还简要的介绍了本文主要结构。
第二章，介绍了阅读本文时所必须的一些关于交叉数方面的基本概念以及一些重要结果。
第三章，本章节主要得到关于图H与n个孤立点nK1的联图的交叉数，以及此图与路Pn的联图的交叉数及与圈的联图的交叉数的上下界。
第四章，本章主要介绍一个四阶不连通图G与路，圈的联图的交叉数。
第五章，给出本文的总结。