图的交叉数的研究.pdf

《图的交叉数的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号QlZ墨：墨学校代码10542图的交叉数的研究密级学号2QQ墨!QQ2QQZZResearchesontheCrossingNumbersofGraphs研究生姓名：郑敦勇指导教师姓名、职称：黄元秋教授学科专业：运筹学与控制论研究方向：图论及其应用湖南师范大学学位评定委员会办公室二零一一年三月摘要111111IIIlIIll[1lltlllllllltlLIIL10Y1912266图的交叉数问题，起源于二战期间PualTurin在砖厂碰到的一个实际问题，后来逐渐发展成为了图论学科中非常活跃的一个分支，吸引着大批国内外学者的关注和研究．然而，确定一

2、般图类的交叉数是一个NP．完全问题．因此，到目前为止有关图的交叉数的结果比较少，仅限于一些特殊简单图的交叉数．甚至在许多情况下，试图找出图的交叉数的一个好的上界或者下界也是很困难的．本文运用归纳思想以及反证法，确定了两个特殊图：一个六点图G，与路R的联图，以及一个五点图G。与路R的联图的交叉数的精确值，并试图研究了关于完全二部图凰．。的一般性质．全文由5个章节组成．第一章介绍了交叉数的起源，交叉数研究的理论与实际意义，以及目前交叉数研究在国内外的发展情况．同时还简要介绍了本文的主要结构．第二章介绍了阅读本文所要用到的图的交叉数方面的基本概念和预备知识．

3、第三章得到了图G，(歹=1，2)与路R的联图的交叉数．第四章讨论了关于完全二部图蚝m的一些性质．第五章给出了本文的总结．关键词：图；画法；交叉数；完全二部图：联图．ABSTRACTThecrossingnumberofgraphscomesfromthePualTurdn’SbrickfactoryproblemduringtheWorldWarII，anditbecomesaveryactivebranchinGraphTheory,manyauthorshavestudiedthisarea．However，determiningthecross-

4、ingnumberofgraphsisNP-complete．Becauseofitsdifficuky,thereareonlvveryscarcespecialclassesofgraphswhosecrossingnumbersaredetermined．Evenmsomecases，itisverydifficuktofindtheupperorlowerboundsofthecrossingnumberofgraphs．Inthispaper，westudythecrossingnumberoftwospecialgraphs，suchast

5、heJoinGraphof6-vertexgraphG1andpathsR；theJoinGraphof6-vertexgraphG2andpathsR．Inaddition，westudytheprop-ertiesofcomplete-bipartitegraph／／5，t1．Thepaperisconsistof5chapters：Inchapterone，weintroducetheoriginsandbackgroundsofthecrossingnumber，itstheoreticalandpracticalmeanings，andits

6、developmentaroundtheWOrld．Chaptertwogivessomeconceptionsandpropertiesofthecrossingnumber，andintroducestherequiredknowledgeforreadingthispaper．ChapterthreedeterminesthatthecrossingnumberofthejoingraphGjO=1，2)andpathsR．Chapterfourstudiesthepropertiesofcomplet争bipartitegraph恐mInthe

7、lastchapter，wemakesomeconclusionsofourresearchwDrkandputforwardsomerelativeproblemswhichwewillgoahead．-Keywords：graph；drawing；crossingnumber；complete-bipartitegraph；joinGraph．IV目录中文摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．I英文摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．III1．绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．(1)1．1研究背景介绍⋯⋯⋯⋯⋯⋯

8、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯(1)1．2本文的结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．(6)2