几类特殊图的荫度问题

来源 :青岛大学 | 被引量 : 0次 | 上传用户:bb253
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的染色理论最初来源于“四色猜想”问题,之后染色理论经过人们的不断发展,就延伸出点染色,边染色,全染色等染色理论。在本文中,我们主要研究的是边染色和点染色,具体来说,即平面图的线性荫度,可嵌入到欧拉示性数非负曲面图的线性荫度和平面图的点荫度。本文所讨论的图皆为有限的、简单的无向图。图的线性荫度最初是由Harary在1970年定义的,即图G可以分割成线性森林的最小数量,其中线性森林就是不相交的路的并集,并且用符号la(G)来表示图G的线性荫度。之后,经过人们的不断探究,Akiyama,Exoo和Harary提出了线性荫度猜想,即对于任意的图G,有[△(G)/2]≤la(G)≤[△(G)+1/2],这里△(G)表示图G的顶点的最大度。图的点荫度最初是由Chartrand等人在1968年定义的,即图G可以分割成森林的最小数量,其中森林就是不含圈的树的并集,并且用符号va(G)来表示图G的点荫度。之后,他们还证明了任意图的点荫度满足v(aG)≤[1+△(G)/2],平面图的点荫度满足va(G)≤3。在第一章,我们主要介绍图论的发展史,以及本文所涉及到的定义、符号还有专业术语。在第二章,我们研究最大度△(G)≥7的平面图,讨论了不含相邻含弦i,j∈{5,6,7}-圈的平面图G的线性荫度,证明了其线性荫度是[△(G)/2]。在第三章,我们研究最大度△(G)≥7且可嵌入到欧拉示性数非负的曲面图,讨论了不含相邻的含弦6-圈的图G的线性荫度,证明了其线性荫度是[△(G)/2]。在第四章,我们研究平面图的点荫度,讨论了不含相交的5,6-圈的平面图G的点荫度,证明了其点荫度满足va(G)≤2。最后,我们对本文做了总结,并对图的点荫度问题做出了展望。
其他文献
超网络是一种基于规则的分类模型,能够有效地处理各种分类问题,已被广泛地应用于模式分类、机器学习、生物信息学等领域。在实际应用中,传统超网络模型主要存在以下两个问题:
背景慢性失眠(chronic insomnia,CI)和阻塞性睡眠呼吸暂停(obstructive sleep apnea,OSA)是两种最常见的睡眠障碍,且两者常常共病(comorbid obstructive sleep apnea with ch
第一部分前循环大血管狭窄患者的认知功能与脑灌注变化目的:观察前循环大血管狭窄患者的认知功能与脑灌注改变方法:收集无症状的前循环大血管狭窄患者19例为病例组,行脑CT增
当前对于高清晰、高质量、可控状态、固定场景下的传统人脸表情识别与单因素的人脸表情识别研究,已经取得了比较满意的识别效果,但对于非约束状态下不可控人脸表情图像,效果不理想。原因在于非约束状态下人脸表情图像是多种因素共同作用的结果,这些因素给人脸表情识别带来了很大的挑战。本文提出一种鲁棒性高的非约束状态下多因素人脸表情识别算法,主要工作内容如下:(1)非约束状态下人脸表情图像往往包含多种影响因素,导致
以ReBCO为超导载流层的第二代高温超导带材,也被称为涂层导体,因为其较低的制造成本、出色的外磁场下电流承载能力,在实际使用中拥有非常广阔的前景。但是由于其对生产工艺的
互联网和社交网络的高速发展,为网民互动和发表意见提供了一个广阔的平台,网站评论、博客文章、新闻等大量的文本数据随之而产生。但是,互联网中的言论大多都含有个人情感的
中药在世界范围内的疾病治疗和人类健康护理中发挥着重要作用,中药的安全性是世界各国普遍关注的问题。因此,中药中有害物质的检测方法至关重要。然而,当前的测定方法耗时长
混沌理论是非线性科学的重要组成部分,在电路工程、图像加密以及保密通信等领域有重要的应用价值。随着人们对混沌研究的不断深入,发现整数阶系统具有分数维的性质。由于分数阶系统的阶数可以灵活调整,使得它拥有比整数阶系统更复杂的动力学行为。因此,采用分数阶微积分可以较为客观地描述非线性系统的行为,更加符合工程实际。针对现有分数阶系统吸引子动力学行为单一以及同步控制器设计复杂的问题,本文以分数阶系统为研究对象
改革开放以来,中国社会发生巨大变化,经济文化繁荣,公共艺术的形式也随之丰富并产生了各种形态。公共艺术是宋庄艺术中的重要组成部分,宋庄的当代性公共艺术开辟了一种新的公
目的:观察加味四妙散治疗抽动障碍湿热内蕴证临床疗效。方法:将符合纳入标准的60例门诊患儿分为观察组和对照组,每组30例,观察组采用中药加味四妙散口服,对照组采用盐酸硫必