几类特殊图的区间边染色

来源 :江苏师范大学 | 被引量 : 0次 | 上传用户:jeff1986928
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
对一个图G进行正常边染色,如果图G中的每一个顶点v所关联的边的颜色数是连续的或者说所染的颜色数可以构成一个整数区间,那么这个图就是一个可区间边染色图.这个问题源于学校在召开家长会时,想提前安排好家长与老师的咨询时间,要求每组会议时间一定,所有参加会议的老师构成集合A,所有的家长构成集合B,集合A与B便是二部图的二部顶点集,如果某位老师与某位家长要见面则连边,此时对这个二部图边进行染色,颜色数是整数,每条边的色数就是双方约定的见面时间,安排完希望不管是家长还是老师结束一个见面会议以后可以直接进入下一个会议,两者都不用浪费时间等待,也即让这个二部图的每个点关联边的颜色数是连续的即可。如果给定一个图,判断这个图是否是一个可区间边染色图,这是非常困难的一项任务.事实上,现在已经证明了一个二部图是否有一个区间边染色,这是一个NP-完备的问题.在这个课题中,我们主要整理了一些现在已经知道的关于图有区间边染色的一些结果,并且针对(a,b)-双正则二部图,在论文第二章做了一些结果,我们给出了一个(3,4)-双正则二部图有区间染色的一个充分条件,以及关于(a,ka)-,(a,3a)-,(4,4k)-双正则二部图有区间边染色的条件。随着对二部图的区间边染色的研究,又有人开始对三部图的区间边染色情况做研究,在第三章中,我们主要得到了几类特殊的完全三部图Kl,m,n区间染色的结果,例如K2,m,m,Kl,m,k(l+m)等.论文在最后一章则介绍了以后工作的方向及下一步所需要解决的问题。
其他文献
新能源汽车的发展促进了人们对动力电池的需求,而典型负极材料的工作性能已近乎达到理论极限。为满足工作性能需求,新型负极材料的发展与应用未来可期,开展其生态环境影响的量化评估与生态设计分析,是实现负极材料可持续发展的关键。研究首先针对中间相炭微球(MCMB)、钛酸锂(LTO)和硅碳(Si/C)三类新型负极材料,采用生命周期分析方法(LCA)开展生命周期环境影响评价。通过公开数据库,文献检索,企业报告、
公平正义是法律追求的价值目标。2009年《侵权责任法》出台后,其第24条的规定被学界称为公平责任条款,公平责任是指:受害人和行为人对损害的发生都没有过错的,法官可以依据实际情况,判定由双方分担损失。该条款是公平正义这一理念在法律条文上的具体化,有利于实现社会公平,社会的和谐发展。但与此同时,学术界和实务界对公平责任的讨论一直没有停止,尤其是司法实践中关于公平责任适用出现的滥用错用问题,主要包括适用
针对当前木材加工企业中普遍用人工进行木材表面缺陷检测的现状,本文采用机器视觉技术对木板表面图像特征进行研究,设计了一套包含软、硬件结构的自动检测装置来代替人工检测,提高了检测效率。本文完成的主要工作内容如下:1)根据企业生产需求及木板样本特点,确定分类标准,将木板缺陷分为活节、死节、油线三类。确定自动检测系统的工艺流程,设计相应的机械、电气硬件结构,制订用于机器视觉检测的软件开发计划。2)对木板表
非细胞黏菌的原质团是黏菌生活周期中的营养生长阶段。本实验采用的材料包括有:绒泡菌目、绒泡菌科、绒泡菌属的多头绒泡菌(Physarum.polycephalum)、绒泡菌目、绒泡菌科、煤
近些年国内外发生多起恐袭事件,每次都造成大量的人员伤亡,案发地几乎是人员密集的地方,例如火车站广场、公园入口区域、机场入口区域、商店入口区域、学校入口区域等。X射线技术结合图像处理技术,更加针对性地应用到安防领域,为反恐检测提供依据,进一步使安全检测便捷。然而,现代地铁口、机场、港口等一些重要地方使用的X射线安检设备,对被检包裹物的检测只能从物理性质和化学性质方面进行图片描述,再进一步识别包裹里被
随着我国市场经济体制的发展和现代企业制度的完善,各企业纷纷扩大规模以面对日益激烈的市场竞争,企业重组也随之成为企业发展的重要方式。企业重组会受到多种因素的影响,而
Dorogovtsev在[1]中首次提出了高斯积分子,作为维纳过程的一种推广,并给出了高斯积分子一个等价刻画,即一个中心化高斯过程{Y(t),t∈[0,1]}为积分子的充要条件是存在L2([0,1])上
为了解决能源不断减少与人们日益增长的能源需求之间的矛盾,需要调整能源结构,发展新能源产业。波浪能作为新能源中的一种,其储量大且能流密度高。因此,对波浪能的开发和利用
中国黄土高原地貌破碎,地质环境脆弱,频发的滑坡、崩塌、地面沉陷等自然灾害造成的人员伤亡和财产损失惨重,严重制约了经济发展,然而其中90%以上的滑坡都因降雨诱发。黄土遇水后导致的胶结减弱、自重增加、裂缝扩展、强度降低等反应均可降低边坡的稳定性,开展降雨诱发滑坡的大型物理模型试验,研究雨水的入渗运移规律和边坡的失稳破坏过程,能够完善黄土灾害相关理论,填补该方向研究空白,并对黄土滑坡防灾减灾工作有重要的
随着煤炭、石油等不可再生资源的短缺,近几年世界各国对光伏发电愈发重视。为监测光伏电站中每个组件的实时运行状况,有必要研制一种实用化光伏组件监测系统,实现组件级的光伏运行信息监测。本文首先对国内外光伏组件监测系统进行了研究,通过调研光伏电站的逆变方式,设计了两种组件监测系统通信架构,并分析二者的优缺点,确定了汇流箱/逆变器与组件间载波通信的通信方式,并设计相应的通信协议以保证监测系统各监测设备间的正