特殊图G与路与圈以及与孤立点的联图的交叉数

来源 :湖南师范大学 | 被引量 : 0次 | 上传用户:sunchaoemo
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数问题起源于二战时期Pual Turán在砖厂碰到的一个实际问题,后来逐渐发展成为图论学科中非常活跃的一个分支,吸引着大批国内外学者的关注和研究,其理论在电路板设计,草图识别与重画以及生物DNA的图示等领域有广泛的应用.但是,k确定一般图类的交叉数问题已经被证明是一个NP-完全问题.因此,至今为止有关图的交叉数问题的结果还非常少,且己被确定交叉数的图类大多数都是一些比较特殊的图类,故很多方法都不能推广到一般情况.甚至有的时候找出图的交叉数的一个比较好的上界或下界也很困难.本文运用归纳法的思想以及反正法确定了两个特殊图类的交叉数:一个六阶图H与路Pn的联图的交叉数以及一个四阶不连通图G与路,圈联图的交叉数本文一共由五个章节组成.第一章主要介绍了交叉数的起源,交叉数研究的理论与实际意义,目前关于交叉数的一些研究现状,同时本章节还简要的介绍了本文主要结构.第二章介绍了阅读本文时所必须的一些关于交叉数方面的基本概念以及一些重要结果.第三章,本章节主要得到关于图H与n个孤立点nK1的联图的交叉数,以及此图与路Pn的联图的交叉数及与圈的联图的交叉数的上下界.第四章,本章主要介绍一个四阶不连通图G与路,圈的联图的交叉数.第五章,给出本文的总结.
其他文献
"互联网+"时代,信息技术对各行各业的生态系统进行了全面升级,各级教育改革发展也迎来了新的拐点,开放大学校企合作办学也面临着全新的机遇和挑战,如何抓住时代要点,加快人才培
客滚船凭借其方便、快捷的特点,在海上客货运输过程中有着不可替代的地位。然而由于客滚船大通舱结构特点及其所载货物的特殊性,客滚船在发生火灾后倾覆现象时有发生,原因是在消防过程中船舶的稳性丧失。在消防过程中,客滚船受风浪影响,车辆移动或倾倒,消防水排水不畅,形成大面积的自由液面,结果导致船舶稳性减小或丧失,导致船舶倾覆。本文旨在通过对客滚船消防积水时的完整稳性进行研究,指导客滚船消防救援进行科学施救,
以PROFINET为代表的工业以太网,在国际上已渐有取代现场总线的趋势,但在国内,受限于中文资料和相关产品的稀缺,应用并不广泛。如果有一款本地化的PROFINET平台,一定能加速这
随着我国经济的快速发展和环境保护水平的不断提升,以及近年来土壤污染事件的发生,污染场地治理成为社会广泛关注的焦点。由于缺乏统一规范性立法,实践中污染场地特别是城市