论文部分内容阅读
图的交叉数概念是由图论专家Pual Turán于1944年在《Journal ofGraph Theory》的创刊里引入的，它是衡量一个图离平面图有多远的一个参数，是图的一个重要拓扑不变量.其理论已应用到大规模电路VLSI中的圈布局，草图的重画与识别，生物工程DNA的图示上等.自20世纪以来，国内外许多图论方面的专家学者投身到这一领域.如C.Thomassen、B.Mohar、D.Archdeacon、R.B.Richer、 D.J.Kleitman、K.Asano、D.Bokal、P.T.Ho、 M.Kle(sc)等，及国内的刘彦佩、黄元秋、郝荣霞、任韩、杨元生、陈仪朝等人.然而M.R.Garey和D.S.Johnson已证明计算一般图的交叉数是一个NP-难问题.正因为如此，到目前为止关于图的交叉数的成果并不是很丰富，且能确定其精确值的图类大多结构特殊，研究方法也无法推广到一般的图上.本文尝试利用一些新的方法探讨若干图类的交叉数，已取得了以下几个方面的结果如下: 1.研究联图的交叉数.本文第二章，用不同于M.Kle(sc)的方法确定了一些五阶、六阶图分别与n个孤立点、路和圈的联图交叉数，尤其得到了两个不连通的五阶、六阶图分别与n个孤立点联图交叉数，目前关于这方面的结果基本很少. 2.研究Cartesian积图的交叉数.本章引入一个新的拉链积性质，得到了两个六阶图、一个七阶图和一个八阶图分别与路的Cartesian积图的交叉数.引入一些新的收缩技巧，部分解决了猜想cr（K2，m□Sn）=cr（K2，m，n）+([)m/2」([)m-1/2」(m≥5). 3.研究几个特殊图的交叉数.本文第四章考虑一些特殊图的交叉数.研究了两类特殊图Km-3e（完全图Km去掉三条匹配边得到的图）和Km，n-2e(完全二部图Km,n去掉两条边得到的图)的交叉数.关于图K2，m，n的交叉数我们也得到了一些相关结论.