几类特殊图的区间边染色

发布时间：2020-03-27 06:57

【摘要】：对一个图G进行正常边染色,如果图G中的每一个顶点v所关联的边的颜色数是连续的或者说所染的颜色数可以构成一个整数区间,那么这个图就是一个可区间边染色图.这个问题源于学校在召开家长会时,想提前安排好家长与老师的咨询时间,要求每组会议时间一定,所有参加会议的老师构成集合A,所有的家长构成集合B,集合A与B便是二部图的二部顶点集,如果某位老师与某位家长要见面则连边,此时对这个二部图边进行染色,颜色数是整数,每条边的色数就是双方约定的见面时间,安排完希望不管是家长还是老师结束一个见面会议以后可以直接进入下一个会议,两者都不用浪费时间等待,也即让这个二部图的每个点关联边的颜色数是连续的即可。如果给定一个图,判断这个图是否是一个可区间边染色图,这是非常困难的一项任务.事实上,现在已经证明了一个二部图是否有一个区间边染色,这是一个NP-完备的问题.在这个课题中,我们主要整理了一些现在已经知道的关于图有区间边染色的一些结果,并且针对(a,b)-双正则二部图,在论文第二章做了一些结果,我们给出了一个(3,4)-双正则二部图有区间染色的一个充分条件,以及关于(a,ka)-,(a,3a)-,(4,4k)-双正则二部图有区间边染色的条件。随着对二部图的区间边染色的研究,又有人开始对三部图的区间边染色情况做研究,在第三章中,我们主要得到了几类特殊的完全三部图K_(l,m,n)区间染色的结果,例如K_(2,m,m),K_(l,m,k(l+m))等.论文在最后一章则介绍了以后工作的方向及下一步所需要解决的问题。
【学位授予单位】：江苏师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 徐森;徐秀芳;花小朋;皋军;徐静;;一种基于二部图谱划分的聚类集成方法[J];控制与决策;年期

2 乔晓云;;二部图的Resolvent Estrada指标的界[J];山西大同大学学报(自然科学版);2017年02期

3 牟谷芳;;有向通弦二部图的最小秩问题研究[J];乐山师范学院学报;2017年08期

4 耿显亚;赵红锦;徐李立;;二部图的距离k次方和问题（英文）[J];数学杂志;2017年06期

5 葛志鹏;严广乐;张国亮;;基于蚁群聚类的二部图网络推荐算法[J];信息技术;2016年03期

6 李硕;颜谨;陈文雅;;均衡二部图中点不交的4-圈和6-圈（英文）[J];数学进展;2015年01期

7 孙静;胡智全;;平衡二部图哈密尔顿性的一个充分条件[J];应用数学学报;2015年05期

8 柳俊;周斌;黄九鸣;;基于二部图投影的微博事件关联分析方法研究[J];信息网络安全;2014年09期

9 李立峰;刘三阳;罗清君;;弦二部图的概念格表示[J];电子学报;2013年07期

10 陈宏宇;张丽;;给定控制数的连通二部图的最大边数[J];山东大学学报(理学版);2012年08期

相关会议论文 前7条

1 柳俊;周斌;黄九鸣;;基于二部图投影的微博事件关联分析方法研究[A];第29次全国计算机安全学术交流会论文集[C];2014年

2 常迎香;;一类无完美匹配的二部图[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

3 王国霞;刘贺平;李擎;;二部图影射及其在推荐系统中的应用[A];第25届中国控制与决策会议论文集[C];2013年

4 李小强;张宁;;基于邻接矩阵的二部图的判定方法[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

5 姚家保;古天龙;徐周波;;二部图无权最大匹配的符号OBDD算法[A];2005年全国理论计算机科学学术年会论文集[C];2005年

6 吴修国;韩作生;许崇敬;林腾;;分布式教务监考排定系统的研究与设计[A];山东省计算机学会2005年信息技术与信息化研讨会论文集（一）[C];2005年

7 李盛;;基于协同聚类的图像分割[A];第十四届全国图象图形学学术会议论文集[C];2008年

相关博士学位论文 前10条

1 王洪伟;二部图的匹配强迫数[D];兰州大学;2008年

2 孙静;二部图参数与圈型结构研究[D];华中师范大学;2014年

3 边红;图中的若干极值问题[D];厦门大学;2008年

4 刘敏;图中结构及相关参数研究[D];华中师范大学;2016年

5 邓凯;图的匹配强迫谱与匹配反强迫谱研究[D];兰州大学;2016年

6 郇潇;图中匹配的可扩性研究[D];南开大学;2010年

7 邹青松;图包含指定长度的圈和泛弧问题的研究[D];山东大学;2011年

8 李良辰;图中Z_3-连通和处处非零3-流问题的研究[D];华中师范大学;2012年

9 张光军;图的特下与度序列[D];上海交通大学;2012年

10 马丽;素数幂与2倍素数幂阶局部本原图[D];云南大学;2012年

相关硕士学位论文 前10条

1 井普宁;几类特殊图的区间边染色[D];江苏师范大学;2018年

2 朱高兹;基于协同过滤和加权二部图的推荐算法研究[D];吉林大学;2017年

3 许梅;基于二部图的事件建模及分析[D];北京邮电大学;2017年

4 丁立佳;二部图完美匹配计数与禁位排列[D];大连交通大学;2014年

5 胡琳;二部图的列表着色问题[D];新疆大学;2004年

6 孙晓萌;基于社团划分和加权二部图网络的个性化推荐算法研究[D];河北工业大学;2015年

7 张文琦;均衡二部图中的2-因子[D];山东理工大学;2010年

8 冯文丽;关于二部图的两个结果[D];山西大学;2005年

9 杨帆;（3，，4）-双向正则二部图的区间着色[D];华中师范大学;2008年

10 郭赵强;低密度校验码二部图构造算法研究[D];西安电子科技大学;2009年

本文编号：2602641