四着色新算法及其应用

来源 :燕山大学 | 被引量 : 0次 | 上传用户:JK0803fengwei
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
四色问题是图论研究领域中的核心问题,四色定理的证明就意味着所有与四色定理等价的命题如考夫曼叉积猜想、马季亚谢维奇建立的丢番图方程解的存在性猜想等都同时得到了证明。四色定理的证明不仅可以证明出现在图论以外其它领域的等价命题,而且可以解释这些领域中与图论同构的思想体系。因此论文的研究具有一定的理论价值。论文首先介绍了四色问题的性质,分析了四色问题证明的几种不同思路以及各种证明方法的优点和不足,指出了四色问题与四着色算法之间的内在联系。其次,研究了顶点着色理论以及基于顶点着色理论的四着色算法。介绍了肯普的四着色理论,分析了基于肯普理论的肯普-凯特尔算法的优点以及存在的不足,并给出了改进后的新的四着色算法,同时给出了一个实例分析,证明了新的四着色算法不仅对于不存在不可变肯普链缠结的情形有效,而且对某些存在不可变肯普链缠结的情形同样有效。再次,研究了边着色理论以及基于边着色理论的四着色算法。分析了泰特的边着色理论及其缺陷,探讨了将肯普理论与泰特理论结合起来证明边着色定理的思路,从不局限于平面性的二部图角度运用匹配思想对四色定理提供了一个新的证明,并且据此构建了一个边着色的新四着色算法。最后,讨论了四着色算法在实际应用中的价值并结合四着色理论发展的一些前沿问题对四着色理论未来的发展的空间作出了一个展望。
其他文献
贝壳基质蛋白(Shell Matrix Proteins,SMPs)是贝壳形成的主要参与者和功能执行者,在有机框架构建和矿物沉积过发挥重要作用。本课题组前期通过对马氏珠母贝(Pinctada fucata
目的:探讨异种脱细胞猪皮基质敷料(生物敷料Ⅱ型)作为肉芽创面小皮片移植后覆盖物的临床效果。方法:22例肉芽创面植皮患者,肉芽创面总面积为5%8%TBSA,随机分为观察组和对照组。肉芽创面在小皮片移植后应用异种脱细胞猪皮基质敷料覆盖为观察组,以凡士林纱布覆盖为对照组,两组各11例。以视觉模拟评分(Visual Analogue Scale,VAS)作为疼痛评分,比较两组术后第5天换药前后30 min
本文以认知语言学为方法,分别从认知相似性、范畴典型性和分布普遍性三个方面,综合而系统地探究了英语句法结构的语义自然度。 以帮助读者理解和掌握英语句法结构为初衷,文章
英语搭配能力是衡量英语学习者英语水平的一个重要方面。然而,对于中国学习者而言,英语搭配一直是个难点。尤其是动词-名词搭配更成为难以掌握的一个方面。鉴于此,本文对中国
本研究在汉语口语产出准确度和汉语学习自我效能感已有研究成果基础之上,俄罗斯中级汉语学习者为研究对象,对其汉语口语产出的准确度和汉语学习自我效能感情况进行了考察,并
在机器学习和模式识别领域中,研究人员常常用样本间距离来衡量样本的相似性。在实际复杂任务场景中,传统的距离度量方式,如欧氏距离、马氏距离、汉明距离等,难以真正表征数据
写作是英语外语教学的一项重要组成部分。但是写作不仅是一项练习手段也是英语外语学习的一项目标。习惯上英语教师认为掌握一定数量的单词词语和语法规则是写作的基础,因此学
目的:通过国外和我国国家与地方省市的医保药品价格谈判的实践过程和结果,总结我国医保药品价格谈判现状和影响医保药品价格谈判的因素,分析谈判对药品价格和销量的影响,在分析影响医保药品价格谈判的因素基础上,为完善我国医保药品价格提供相关建议。方法:使用文献研究法对国内外的药品价格谈判的实践和观点进行归纳和总结;使用SPSS 22.0分析谈判对医保谈判药品价格谈判前后的销量和价格的影响;利用专家评分法和A
在实际生活中,由于测量方法和测量工具的精度问题,当响应变量大于最大值或小于最小值时,我们便观测不到响应变量的真实值,此时,Tobit模型可以用来分析此类数据.本文研究了双
随着网络媒体的迅速发展,网络广告大有取代传统媒体广告的趋势,但是,其法律规制却相对滞后,各国对网络广告的法律定位及立法模式尚未形成统一的认识。由于某些网络广告的基本