- 1、本文档共4页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
两类广义图r-冠图的分数色数.pdf
第27卷第2期 重庆工商大学学报(自然科学版) 2010年4月
Sci
J TechnolBusinessUniv.(NatEd)
V01.27NO.2 Chongqing Apr.2010
文章编号:1672-058X(2010)02-0105—03
两类广义图r一冠图的分数色数事
高炜,梁立
(云南师范大学计算机科学与信息技术学院,昆明650092)
摘要:图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许
多领域中有着重要的应用.此处给出了广义圈、广义轮图的r.冠图的分数色数的计算公式.
关键词:分数色数;分数团;广义圈;广义轮图
中图分类号:TQ92 文献标志码:A
1基本概念和引理
关于此专题较为详尽的论述.图的分数色数有着十分广泛的应用,例如MWIS问题可用分数着色模型来解
决,研究特殊图形的分数色数有助于解决特殊多处理器结构下的MWIS问题,相关内容可参考文献[2,3].
关于图的分数着色有很多不同的定义方式,下面给出几种最常见也是最重要的定义,即分数着色、分数团和
口:b着色(此处只考虑无向、简单、有限图.文中涉及的符号和标记若没有特别说明,则与文献[4]一致).
M
l
t
是图G的分数着色}.
z,(G)=lllaX{善.、g(秽)Ig是图G的一个分数团}.
可参考文献[5].
E6】
定义3 图G的口:b着色,就是指给G中各顶点分配一个集合{1,2,…,a}的b元子集,使得相邻顶点
G存在口:b着色}.
的集合不交,则所(G)=inf{a/bI
以上3个定义是等价的,并且图G的分数色数是一个有理数,相关内容可参考文献[6].
定义4【71设C。是一个长度为n的圈,将c。的每一个顶点替换成k个点的独立集,并使相邻的两个独
立集中点两两相邻,这样得到的图叫做广义圈,记作c。(k).
定义5【81对自然数儿≥3,_|}≥1.广义轮图喊是指k个轮形图睨=K。VC。,将其k个c。重合构成的图.
V
也可将嘭表示成nKl
顶点;tl,t2,…,tt分别是后个E的中心,这里畈=E.
收稿日期:2009一11—20;修回日期:2009—12-23.
·项目基金:国家自然科学基金项目;云南省教育厅科研基金项目.
作者简介:高炜(1981一),男,浙江绍兴人,硕士,从事图论及其应用研究.
万方数据
106 重庆工商大学学报(自然科学版) 第27卷
也称为王冠在G的一个顶点秽上粘接的,条悬挂边的端点集记作t,掌.
引理l【l
o对阶数为n的完全图K,有疋,(K)=n.
引理2…如果日是G的子图,则骱(日)≤膏r(G).
u、u,
数,即最大团的顶点数.
2主要定理以及证明
此处给出厂义圈、广义轮图的r一冠图的分数色数如F:
2, n为偶数
f
定理1肘(,,(cn(尼)))2{三等,厅为奇数’
证明
的独立集.若i为奇数,则K中的顶点着颜色为1,若i为偶数,则K中的顶点着颜色为2;而对于C。(后)中
肘(‘(c。(后)))≤2:故当n为偶数时次,(,r(C。(_|})))=2.
(i—1)(几一1)+2
您可能关注的文档
- 东莞市地块包装规划内容、方法与应用.pdf
- 东莞近现代人才通论.pdf
- 东营凹陷流体压力系统研究.pdf
- 东邦特耐克丝推出高耐热树脂.pdf
- 东风汽车有限公司发布4年事业计划--计划至2007年底将销售与营业利润翻1番.pdf
- 东风汽车有限公司发布中期事业计划23计划将使公司的销售和营业利润至2007年底翻一倍.pdf
- 丝光沸石TiO2复合体的特征及对甲苯光催化降解研究.pdf
- 丝绵等絮用材料基于模糊排序法的舒适性研究.pdf
- 丝裂霉素C联合自体游离结膜瓣移植治疗翼状胬肉的临床观察.pdf
- 两个介电函数模型的用法.pdf
- 2025年广西中考地理二轮复习:专题四+人地协调观+课件.pptx
- 2025年广西中考地理二轮复习:专题三+综合思维+课件.pptx
- 2025年中考地理一轮教材梳理:第4讲+天气与气候.pptx
- 第5讲+世界的居民课件+2025年中考地理一轮教材梳理(商务星球版).pptx
- 冀教版一年级上册数学精品教学课件 第1单元 熟悉的数与加减法 1.1.6 认识1-9 第6课时 合与分.ppt
- 2025年中考一轮道德与法治复习课件:坚持宪法至上.pptx
- 2025年河北省中考一轮道德与法治复习课件:崇尚法治精神.pptx
- 八年级下册第二单元+理解权利义务+课件-2025年吉林省中考道德与法治一轮复习.pptx
- 精品解析:湖南省娄底市2019-2020学年八年级(上)期中考试物理试题(原卷版).doc
- 2025年中考地理一轮教材梳理:第10讲+中国的疆域与人口.pptx
文档评论(0)