图交叉数问题的研究 (1)

《图交叉数问题的研究 (1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学博士学位论文摘要图的交叉数问题是在实际应用中提出来的，在电子线路板的设计，CAD领域有广阔的应用．目前已经确定交叉数的图类主要集中于顶点数较小或者交叉数较小的图．本文对一些项点数较大或交叉数较大的图的交叉数问题进行研究，将计算机构造性证明和数学证明相结合。取得了较好的结果．本课题组给出的交叉数算法CCN已被成功地用于计算顶点数较小的图的交叉数．但由于图的交叉数问题是NP困难问题，对顶点数较大或交叉数较大的图，所需要的计算时间仍然太多．针对这一问题，本文给出了计算图的交叉数上界的算法CCN．。把计算图的交叉数上界问题转化为计算往其子图的较少交

2、叉点画法中回添边时所产生的交叉数的问题，从而可以对较大规模的图的交叉数性质进行研究．利用该算法计算了顶点数Ps12的所有路径幂图砖和13≤P≤20且k≤9的所有曩的较好的交叉数上界．对与圈G交图的交叉数，目前研究的较多的是两个圈的交图以及顶点数较小的图与圈交图的交叉数．Ringeisen和Beineke对玉0口G，m≤4进行了研究．本文对^％口G进行研究，给出了相应的交叉数计数方法，确定了这类图的交叉数下界．对m=5，6，7或者n为不小于4的偶数，给出了交叉数上界及对应的画法；如果著名的完全图交叉数猜想对j岛+2成立，则本文给出的交叉数上界就是完全图如

3、与圈G交图的交叉数．对与路径B交图的交叉数，目前研究的较多的也是顶点数较小的图与路径交图的交叉数．1(1e强等人对％口一，m≤5进行了研究．Bokal对蜀J口一进行了研究．黄元秋与Kleg∈分别研究了Wm口只的n≤3与m=3，4的情形；l【le酪对％3口R进行了研究．本文针对‰口R，Km．，口R，w』。口R进行了研究，给出了这些图的交叉数上界．并对其中‰口只，砭．f口R，H0口R，睨。口只给出了相应的交叉数计数方法，进而导出了这些图的交叉数下界．并最终确定了磁口R，岛J口只，矸0口R，w2J’l口^的交叉数，扩展了与路径交图的交叉数的研究结果．本文所给

4、出的交叉数研究方法还可以用于研究其它图的交叉数问题．作为应用实例，本文确定了两类三正则图Kntidel图^。和FlowerSnark及其相关图只的交叉数．相信该方法在图的交叉数问题研究中还有更广泛的应用．关键词：交叉数；交图；正则图；路径幂图；圈；路径；完全图；完全二部图；轮图；双锥图；Kniidel图：FlowerSnark大连理工大学博士学位论文CrossingNumbersofCertainFamiliesofGraphsAbstractCrossingnumbersofgraphsareingeneralverydifficulttocompu

5、te．neexactcrossingnumbersofveryfewfamiliesofgraphsareknown．Usingcomputeralgorithmtocomputeupperbounds．andusingmathmaticaltechniquestogetlowerbounds，this也esisresearchesonthecrossingnumbersofsomegraphswithrelativelargeorderorwithrelativelargecrossingnumber．TheexistalgorithmCCNprop

6、osedin2002computesthecrossingnumbersofallthegraphswithsomeorder．Unfortunately,thecrossingnumberofagraphisNPcomplete，andnotmuchhopeisheldforefficienflyfindingalloptimaldrawings--orevenasingleoptimaldrawing-forallgraphs．AnalgorithmCCN*ispresentedinthethesistocomputeupperboundsofth

7、ecrossingnumberofpathpowergraphs礴．LetP2IV(G)I．mupperboundsofcrossingnumbersof畿whereP≤12Orl3≤Ps20withk≤9arecomputedbyCCN'．ThenweinvestigatethecrossingnumberofCartesianproductswithcyclesandpaths．FortheCartesianproductofcycleandcompletegraph，RingeisenandBeinekehaveprovedthatcr(C3口C

8、n)=nandcr(商口Cn)=3n．Thethesisobtainsalowerboundf