【作者】 欧阳娟；

【导师】 黄元秋；

【作者基本信息】 湖南师范大学 ， 运筹学与控制论， 2012， 硕士

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

【Abstract】 The research on crossing numbers of graphs is originated in World War Ⅱ, when Pual Turan encountered a practical problem in a brick factory. It gradually developed into a very active branch of the disciplines of graph theory, attracting a large number of scholars’attention domestic and overseas. Besides, its theory has a wide range of applications in circuit board design, sketch recog-nition and redraw, and the graphic representations of the biological DNA, etc. However, to determine the crossing numbers of general classes of graphs have proven to be a NP-complete problem. Therefore, achievements on the crossing numbers of graphs are very few so far, and most of the graphs which crossing numbers are identified are special classes of graphs, therefore a lot of methods cannot be applied to the general classes of graphs, and what’s more, sometimes it is very difficult to find a proper upper or lower boundary of the crossing num-bers of graphs. By using inductive method and reduction-to-absurdity method, this paper determines the crossing numbers of two special classes of graphs:The crossing number of join the special of H with six vertices path and cycle,and not connected graph of G with four vertices path and cycle.This paper consists of five parts:The first chapter mainly introduces the origin of the crossing numbers, theoretical and practical significance of researches on the crossing numbers of graphs, and current status of researches on it. Moreover, the main structure of this paper is briefly described.The second chapter discusses some basic concepts and important achieve-ments of the crossing numbers, which are required in reading this thesis.The third chapter illustrates the crossing number of join the special of H with six vertices path and upper or lower boundary of cycle.The fourth chapter introduces the crossing numbers of not connected graph of G with four vertices path and cycle.The last chapter is the conclusion part.更多还原