论文部分内容阅读
图的交叉数问题是在近代图论中发展起来的一个重要概念,是表征一个图的非平面性的一个重要参数,是拓扑图论中的前沿难题.它起源于上世纪五十年代Turan在砖厂碰到的一个实际应用问题(Tu-rans Brickyard Problem)逐渐发展成为图论学科中非常活跃的一个分支,其理论在电路板设计,草图识别与重画以及生物工程DNA的图示等领域有广阔的应用,因而吸引着国内外许多学者的关注.它研究的主要是如何把一个图画在平面上或曲面上,使其产生的交叉数目最少,通常采用的是纯数学方法的证明.一般地,确定图的交叉数是十分困难的,事实上,Garey和Johnson已经证明了确定一般图的交叉数是一个NP-完全问题.目前,能确定交叉数的图类很少.确定图类的交叉数主要集中在一些特殊图类上,如完全图Kn,完全2-部图Km,n,完全3-部图K1,m,n,简单的图之间的笛卡尔积,循环图等.
本文尝试应用并创新某些新的方法,主要研究了如广义Petersen图.联图.笛卡尔积图等一些典型图类的交叉数.其主要结构如下:
一.交代了图的交叉数的起源、研究背景、研究工作的理论与实际意义,以及较为详细介绍了目前交叉数的研究在国内外的发展动态
二.给出了图的基本概念及本文常要用到的引理和性质.
三.研究了与联图有关的图的交叉数,主要研究了一个典型有两条悬挂边的六阶图与路和圈的联图的交叉数.
四.证明了一个特殊六阶图与路和圈的联图的交叉数..
五.探讨了与轮图有关的交叉数问题,在假定著名的Zarankiewicz猜想对m=7的情形成立的基础上,确定了6-轮W6与路Pn的联图的交叉数和6-轮W6与星图Sn的笛卡尔积图的交叉数.
六.讨论了一类Petensen图的交叉数,主要确定了当κ≥3时,广义Petensen图P[3κ-1,κ]交叉数的上界和下界.
七.给出了本文的总结和对未来工作的展望.