几类联图交叉数地研究

《几类联图交叉数地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要fIIlllllllllllllllllJJlHIJlllllllllllllJllfY2147760近几年，越来越多的学者开始着手研究小阶图与路、圈的联图的交叉数．K2e誊e给出了所有缸阶图(含不连通图)与路、圈的联图的交叉数，此后，陆续有学者得到了一些五阶图与路、圈的联图的交叉数．2010年，K2e誊E确定了一个特殊6-阶图与路、圈的联图的交叉数【4引，丰富了联图交叉数的成果．本文在已有结果的基础上，得到了完全2一部图尥．4与路、圈的联图的交叉数，以及两个不连通图与n个孤立点的联图的交叉数，并得到四个推

2、论，另外确定了两个特殊的、结构较简单的不连通图与n个孤立点的联图的下界。本论文主要研究了几个特殊联图的交叉数，具体结果如下：(1)利用恐，4自身的结构特征，得到了鲍、4与路、圈的联图的交叉数：(2)确定了一个特殊5-阶不连通图quK，与几个孤立点的联图的交叉数，以及两个相关推论；(3)得到了一个特殊6-阶不连通图GuK，与n个孤立点的联图的交叉数，以及两个相关推论；(4)利用组合计数等方法得到了两个特殊不连通小阶图与几个孤立点联图交叉数的下界．关键词：图；好画法；交叉数；联图．ABSTRACTInrecenty

3、ears，moreandmorescholarsbegantodoresearchesonthecrossingnumbersofjoinofsomelowordergraphswithpathandcycle．KleS己hassolvedthecrossingnumbersofjoinofallthe4-vertexgraphswithpathandcycle，includingunconnectedgraphs．Othersgotthecrossingnilmbersofthejoinproductsofs

4、ome5-vertexgraphswithpathandcyclesuccessively．In2010，Kle童averifiedthecrossingnumbersofjoinofaspecialgraphonsixverticeswithpathandcyclel451,enrichedtheresultsofthejoinproductoftwographsonthecrossingnumber．Inthispaper，westudythejoinofgraphsbyfurtheronthebasiso

5、fconclusionswealreadyhave．WesolvethecrossingnumberofioiIlof垃，4withpathandcycle，verifythecrossingnumbersofjoinoftwospecialunconnectedgraphswithnKl，andgetfourinference．Whatismore，weobtainalowerboundforthecrossingnumbersofjoinofothertwospecialunconnectedgraphsw

6、ithnKl．Themainconclusionswehavegetinthispaperareasfollows．(1)UsingthestructuralcharacteristicsofK2'4’thecrossingnumbersofjoinof％，4withpathandcycleareobtained．(2)Verifiedthecrossingnumbersofjoinofaspecial5-vertexgraphwithnKl，andgottwoinferences．(3)Verifiedthe

7、crossingnumbersofjoinofaspecial6-vertexgraphwithnKl，andgottwoinferences．(4)Usingthecombinatorialcountingmethod，weobtmnedalowerboundforthecrossingnumbersofjoinofothertwospecialunconnectedgraphswith?zKl．Keywords：Graph；Gooddrawing；Crossingnumber；Jointgraph．II儿类

8、联图的交叉数研究1绪论图的交叉数(crossingnumber)是衡量一个画在在平面(或曲面)上使得边之间交叉尽可能少的一个重要参数，自上世纪五十年代被提出以来，已成为国际上一个非常活跃的图论研究领域．确定图的交叉数不仅对揭示图论的组合结构具有重要的理论意义，而且有着较强的现实应用背景，如电子电路板设计中的布线问题、CAD领域中的草图识别、软件开发工具中文档部分的ER图的自动生成等许多