图的交叉数问题研究

来源 :大连理工大学 | 被引量 : 12次 | 上传用户:q999666
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数问题是在实际应用中提出来的,在电子线路板的设计,CAD领域有广阔的应用。目前已经确定交叉数的图类主要集中于顶点数较小或者交叉数较小的图。本文对一些顶点数较大或交叉数较大的图的交叉数问题进行研究,将计算机构造性证明和数学证明相结合,取得了较好的结果。本课题组给出的交叉数算法CCN已被成功地用于计算顶点数较小的图的交叉数。但由于图的交叉数问题是NP困难问题,对顶点数较大或交叉数较大的图,所需要的计算时间仍然太多。针对这一问题,本文给出了计算图的交叉数上界的算法CCN*,把计算图的交叉数上界问题转化为计算往其子图的较少交叉点画法中回添边时所产生的交叉数的问题,从而可以对较大规模的图的交叉数性质进行研究。利用该算法计算了顶点数p≤12的所有路径幂图Pnk和13≤p≤20且k≤9的所有Pnk的较好的交叉数上界。对与圈Cn交图的交叉数,目前研究的较多的是两个圈的交图以及顶点数较小的图与圈交图的交叉数。Ringeisen和Beineke对Km□Cn,m≤4进行了研究。本文对Km□Cn进行研究,给出了相应的交叉数计数方法,确定了这类图的交叉数下界。对m=5,6,7或者n为不小于4的偶数,给出了交叉数上界及对应的画法;如果著名的完全图交叉数猜想对Km+2成立,则本文给出的交叉数上界就是完全图Km与圈Cn交图的交叉数。对与路径Pn交图的交叉数,目前研究的较多的也是顶点数较小的图与路径交图的交叉数。Kle(?)等人对Km□Pn,m≤5进行了研究。Bokal对K1,l□Pn进行了研究。黄元秋与Kle(?)分别研究了Wm□Pn的n≤3与m=3,4的情形;Kle(?)对W2,3□Pn进行了研究。本文针对Km□Pn,Km,l□Pn,Wl,m□Pn进行了研究,给出了这些图的交叉数上界。并对其中Km□Pn,K2,l□Pn,Wm□Pn,W2,m□Pn给出了相应的交叉数计数方法,进而导出了这些图的交叉数下界。并最终确定了K6□Pn,K2,l□Pn,Wm□Pn,W2,m□Pn的交叉数,扩展了与路径交图的交叉数的研究结果。本文所给出的交叉数研究方法还可以用于研究其它图的交叉数问题。作为应用实例,本文确定了两类三正则图Kn(?)del图J3,n和Flower Snark及其相关图Fn的交叉数。相信该方法在图的交叉数问题研究中还有更广泛的应用。
其他文献
IT系统管理复杂性问题是目前IT业面临的最大挑战之一。该问题最明显的症状就是IT系统故障频发,对运营维护管理人员的技术要求越来越高,相应的运营管理成本也持续增加。软件工程
合同管理是建筑工程项目管理的核心,合同管理是一个系统过程,只有熟悉掌握建筑领域法律法规,不断改进和深化合同管理方法,才能确保建筑市场持续健康的发展。本文介绍了建筑工程项
作为贸易大国,绿色贸易壁垒己影响到我国对外贸易的发展。本文通过分析我国应对绿色贸易壁垒的策略,探讨了应合理构筑我国的绿色贸易措施体系。
数据挖掘中的隐私保护问题近年来得到了广泛研究。本文首先分析了在数据挖掘中进行隐私保护的必要性,随后对隐私保护的主要技术进行了研究,最后指出了数据挖掘领域中隐私保护方
本文运用蛛网模型的有关理论,通过线性与非线性分析,研究供需曲线与模型的运行结果,结合解决微观经济领域与教育领域的供需波动问题,提出相应的对策与措施来实现模型的均衡。
科学计算可视化的出现与兴起,为许多传统问题的解决提供了新的思路与途径,拓宽了人类认识世界、理解世界的道路。将科学计算可视化研究与过渡状态研究相结合,能够进一步发挥各学
前言 VLSI(超大规模集成电路)器件在密度和性能方面的飞速发展,给器件的设计、制造和测试提出了新的挑战,导致器件的设计时阃和测试程序的开发时间成指数增长。 在建立器
俗话说“前车之鉴,后事之师”,档案便是将过去的实例加以记录呈现,并对人们现今社会生产生活起到指导作用的资料,档案管理工作记录了历史,又作用于未来,是社会生活中不可缺少的部分
目的:探讨恶性血液病患者化疗后院内感染的整体化护理。方法:对化疗后骨髓抑制期138例患者采用饮食、空气、皮肤黏膜、口腔、上呼吸道、泌尿道、肛周及外阴整体化护理。结果:患
装备制造业素有“工业母机”之称,是人类财富的支柱产业,在国民经济中占据支配地位。绿色制造是21世纪装备制造业重要发展方向,本文探讨将可靠性设计应用到装备制造业产品绿