图的t-松弛染色问题研究
发布时间:2017-12-13 07:23
本文关键词:图的t-松弛染色问题研究
更多相关文章: 染色 t-松弛染色 r-方路 r-方圈 k-树 完全多部图
【摘要】:图的松弛染色问题来自于卫星通信的频率分配问题。设G(V,E)是一个图,t是一个非负整数。令f是一个从顶点集V(G)到非负整数集的函数,如果对任意顶点v都有|{u:f(u)=f(v),u ∈ V(G),uv ∈ E(G)}|≤则称f是图G的一个t-松弛染色。图G的t-松弛色数记为χt(G),定义为minmax{f(v):v ∈ V(G)},其中f取遍图G的所有t-松弛染色。本文主要考虑几个特殊图类的松弛染色问题。在第二章中,对任意非负整数t,我们确定了n个顶点的r-方路的t-松弛色数,给出了n个顶点的r-方圈的t-松弛色数的上下界。当t=0时,χ0(G)即为图G的正常色数,即χ0(G)= χ(G)。显然,当t≥0时,χt(G)≤χ(G)。第三章证明了在顶点数足够多的情况下,kk-树和每个部的顶点数为2t的完全多部图的t-松弛色数等于它们的正常点色数。我们用K(n2,...,ns)表示一个完全s部图,其中s个部的顶点数分别为n1,n2,...,n.s。在第四章中,对t = 1,2,3,4的情形,本文分别给出了求解K(n1,...,.s)的最优t-松弛染色的多项式时间算法。按照相同的求解思路,可以得到t =5,6的最优t-松弛染色的多项式时间算法,由于证明过程太长,故本文省略了这两种情况的细节。当t ≥ 7时,因为顶点数的增多情况越来越复杂,是否存在多项式时间算法求解最优t-松弛染色的问题有待进一步研究。
【学位授予单位】:东南大学
【学位级别】:硕士
【学位授予年份】:2017
【分类号】:O157.5
【参考文献】
中国硕士学位论文全文数据库 前1条
1 齐秀媛;图的条件染色和非正常条件染色[D];山东师范大学;2014年
,本文编号:1284289
本文链接:https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/1284289.html