论文部分内容阅读
图的松弛染色问题来自于卫星通信的频率分配问题。设G(V,E)是一个图，t是一个非负整数。令f是一个从顶点集V(G)到非负整数集的函数，如果对任意顶点v都有|{u:f(u)=f(v)，u∈V(G)，uv∈E(G)}|≤t，则称f是图G的一个t-松弛染色。图G的t-松弛色数记为xt(G)，定义为min max{f(v):v∈V(G)}，其中f取遍图G的所有t-松弛染色。 本文主要考虑几个特殊图类的松弛染色问题。在第二章中，对任意非负整数t，我们确定了n个顶点的r-方路的t-松弛色数，给出了n个顶点的r-方圈的t-松弛色数的上下界。当t=0时，x0(G)即为图G的正常色数，即x0(G)=x(G)。显然，当t≥0时，xt(G)≤x(G)。第三章证明了在顶点数足够多的情况下，k-树和每个部的顶点数为2t的完全多部图的t-松弛色数等于它们的正常点色数。 我们用K(n1，n2，…，ns)表示一个完全s部图，其中s个部的顶点数分别为n1，n2，…，ns。在第四章中，对t=1，2，3，4的情形，本文分别给出了求解K(n1，…，ns)的最优t-松弛染色的多项式时间算法。按照相同的求解思路，可以得到t=5，6的最优t-松弛染色的多项式时间算法，由于证明过程太长，故本文省略了这两种情况的细节。当t≥7时，因为顶点数的增多情况越来越复杂，是否存在多项式时间算法求解最优t-松弛染色的问题有待进一步研究。