关于图的笛卡尔积交叉数的研究

《关于图的笛卡尔积交叉数的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湖南师范大学硕士学位论文关于图的笛卡尔积交叉数的研究姓名：苏振华申请学位级别：硕士专业：运筹学与控制论指导教师：黄元秋20090301摘要图的交叉数是在近代图论中发展起来的一个重要概念，主要研究如何把图画在一个平面上，使其交叉的数目最少．通常这项研究都采用纯数学方法证明．然而，确定一般图的交叉数是一个NP一完全问题，因此，到目前为止有关交叉数的结果比较少，仅限于一些特殊图和简单图的交叉数．甚至于在许多情况下，试图找出图的交叉数的一个好的上界或下界也很困难．近年来，笛卡尔积交叉数越来越受到国内外有关学者的重视和关注．本文运

2、用组合方法和归纳思想以及反证法，主要研究了六阶图G(i_1，2，3，4)与路￡的笛卡尔积交叉数，五阶图Gl，与星图最的笛卡尔积交叉数，轮岷与星图最的笛卡尔积交叉数．全文由五个章节构成．第一章：较为详细地交代了交叉数的起源，理论和实际意义，国内外发展的动态，本文的写作背景，将要解决的问题和文章的创新之处．同时对与交叉数有关的一些基本概念和性质进行了解释．第二章：主要确定四个六阶图q(i=1，2，3，4)与路只的笛卡尔积交叉数．第三章：主要研究了五阶图G1，与星图最的笛卡尔积交叉数．第四章：主要得到了轮联与星图鼠的笛卡尔积交

3、叉数．第五章：提出了研究工作在发展中的一些问题以及作者在以后将致力于前进的方向．关键词：交叉数：轮：路：星图：笛卡尔积：好画法．ABSTRACTTheCrossingnumberofgr印hsisaVitalconc印tinmordengr印htheoⅨIts印plicationisimponantnotonlyinmeoⅨbutalsoinpractice．Thenithasattracttedmany伊印hmeo哆expertstosmdyWehavealreadylmo、mthattodetenllinethecr

4、ossmgnunlbersofgraphsisNP-complete．Becauseofitsdi伍cul咄atpresenttheclassesofgraphswhosecrossingnunlbershaVebeendetellninedareVeryscarce，andthereonlysomespecial伊印hswhosecrossingn啪bersarekn筛m．Eveninsomecases，itisVe拶di衢culttofindtheupperor10w钉boundsofthecrossingnumbe

5、rsof伊aphs．I沁cenUy；mecrossingnunlbersoftheCa九esianproductsbeconlemoreinterested．h1thispaper，westudythecrossingnumbersoftheC叭esianproductsofG(i=1，2，3，4)and￡，detenninethecrossingnumbersoftheCanesianproductsofa$5$一Venicesgr印hsG13With鼠，and呢with最．Ch印terone，intl．CIducin

6、gthebackgroundsofthecrossingnum_bersof鲫hs，itsdeVelopmentaroundmeworld，themeaningsoftheresearch，theproblemswewillsolVe，andgiVingsonleconc印tionsandproperties．Chaptertwo，detelll血ningmecrossingnuITIbersofmeCartesianIIIproductsofGf(i=l，2，3，4)with只．Ch印terthree，detemini

7、ngthecrossingnuH1_bersoftheCanesianofa5-Venices鲫hsG13with最．Chapterfour，detemliningthecrossmgnumbersoftheCartesianof呢with最．Ch印terfiVe，descmingsomequestionSwrhenresearchingintothisproblem，andthedirection1willgoahead．Keywords：Crossingnumbers；W11eel；Pam；Star(计印h；Cart

8、esianproduct；GoodDrawing．IV湖南师范大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的研究成果．除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品．对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标