仙人掌的连续边着色

来源 :新疆大学 | 被引量 : 2次 | 上传用户:benben1906
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G是简单图,用颜色1; 2, 3,…对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的.图的连续边着色对应于没有等待时间的日程安排问题.不是所有的图都有连续边着色.图G的亏度de f (G)是粘在G上使得它可连续着色的悬挂边的最小数目侧. 通常要确定一个图是否有连续边着色是比较困难的,而且己刻划的图只有很少的一部分.事实上,Sevastjanov在[s]中己经证明了即使是对一个给定的二部图,要确定它是否有连续边着色也是NP完全的. 仙人掌是一个每个块是圈或Kz的图.从定义可知一个仙人掌的任意两个不同的圈至多有一个公共点.用of必表示图‘中包含的奇圈个数,尺表示由n个只有一个公共顶点的三角形构成的图.如果一个图G有导出子图G1和Gz使得G二Gl、 Gz并且G1nGz=Ifi,则称G是G,和G:在顶点?的粘,记作G二Gi vv Gz,其中?E Y(Gl n Gz). 在本文中,我们研究仙人掌的连续边着色问题.我们确定了奇.数不超过2的仙人掌的亏度,给出了一个无割边且奇圈数是数的仙人掌可连续着色的充分条件,并且证明了无割边且奇圈数是奇数的仙人掌是不能连续着色的.此外我们还给出了两类亏度为1的仙人掌。
其他文献
期刊
期刊
传统的基于穷举搜索的暴力法在攻击密码散列时需要大量的计算,而且往往要经过很长的时间才能完成计算。 本文作者提出了一种称为索引链预计算法的密码散列攻击方法。传统
近年来,随着互联网等科学技术的飞速发展,在社会调研、基因生命科学等领域每天都会收集到海量的数据,如何从如此多的数据中提取出有用的信息已经成为人们面临的新挑战。在这
期刊
期刊
摘要:中庭为人们创造了舒适的近似室外空间的内部空间,但同时还具有空间大,耗能大,室内热环境不稳定等特点。因而在中庭的设计中,应结合其自身的特点,对于不同形式,不同地区的中庭,采用不同的设计手法,使其能够真正为人们提供一个舒适的室内活动空间。  关键词:寒冷地区中庭设计中庭节能  THE DESIGN OF ARTIUM AND ARCHITECTURAL DAYLIGHTING ROOF   Li
学位
两个同型部件并联组成的可修系统是可靠性理论中的最基本模型之一。本文在现有可靠性研究成果的基础上,对以下两个两同型部件并联可修系统的可靠性进行了分析: (1)考虑检测
期刊