若干图的连续边着色

来源 :山西大学 | 被引量 : 0次 | 上传用户:nooneknow7
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
具有重要的实际意义和理论意义的图的连续边着色问题是图论中的热点话题之一,它在组合分析和日程安排理论上有着非常广泛的应用.连续边着色问题首先是由Asratian和Kamalian在1987年提出的,其内容为:对于简单图G用颜色1,2.3…对其边正常着色,如果每一个顶点表现的颜色构成一个连续的整数集合,那么就称这个边着色是连续的.许多图是不可连续边着色的,为了测量与连续边着色的渐进程度,我们引入了图的一个新的不变量:图的亏度.图G的亏度def(G)是指加在G上使它可连续边着色的悬挂边的最小数目.本文分为三章,主要研究了若干图的连续边着色性.  第一章我们给出了本文将用到的图论的主要术语、记号和基本概念.在第二节我们介绍了连续边着色方面的基本结论.  第二章主要研究了一些圈图的连续边着色.在这章中,根据3-圈图的结构和性质,以及连续边着色的定义,得到了几类3-圈图的亏度,解决了它们的连续边着色问题.进而推广到k-圈图,我们通过运用归纳法和反证法的思想,讨论了一种k-圈图的连续边着色及其亏度问题.  主要结论叙述如下:  (1)若G是四条内部不相交的(u,v)路的并图,则def(G)={0,|E(G)|为偶;1,|E(G)|为奇.  (2)令C1,C2,C3是三个不相交的圈,Pi(i=1,2)是两条不相交的(V(Ci),V(Ci+1))路.若G是C1,C2,C3,P1和P2的并图,则def(G)=0.  (3)若G是仅有一个公共顶点的n(n≥1)个圈C1,C2,…,Cn的并图,则def(G)={0,|E(G)|为偶;1,|E(G)|为奇.  第三章主要是通过运用归纳法思想研究了两种笛卡尔积图Pn×Pm和Cm×Pn的连续边着色问题.  主要结论叙述如下:  (1)若G是两条不相交的路Pn和Pm的笛卡尔积图,则def(G)=0.  (2)令Cm是长为m(m≥3)的圈,Pn是与Cm不相交的一条长为n(n≥0)的路.若图G是Cm和Pn的笛卡尔积,则def(G)≤1.
其他文献
当前,如何让计算机理解人类的自然语言,并运用人类的自然语言模拟语言交际过程,实现“人机对话”,已经成为人工智能的一个重要研究领域——自然语言处理。问答系统是目前自然
学位
小波分析作为当前数学中一个迅速发展的领域,其理论的产生和应用都是十分重要的.小波理论是传统傅立叶变换的重大突破,已经引起了国际上众多学术团体和学科领域的兴趣与关注,
学位
学位
随着我国社会主义市场经济的发展,企业的用工已由学历本位逐步向能力本位转变,企业领导人对人才的需求原则和观念也在改变:过去只需要单一型的技术工人,如今需要的是复合型的
分岔和混沌是非线性系统最重要而又最基本的特性,几乎在所有涉及非线性科学的领域中,都存在着分岔现象和混沌运动。随着现代高新科技的发展,板、壳等结构元件处于电磁场环境
学位
学位
“大数据”时代,广告的策划、创意、制作和发布离不开大量受过高等专业教育的应用技术型人才.满足这一社会需求的最佳途径就是搭建普通本科教育与职业教育融合沟通的“立交桥