MWIS问题模型中几类图形的分数色数高炜梁立*夏幼明(云南师范大学计算机科学与信息技术学院,云南昆明650092)摘要：图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用,例如MWIS问题.给出了齿顶边星图、、蛛网图以及它们的r-冠图的分数色数、分数关联色数和分数全色数.关键词：分数色数；分数团；分数关联色数;分数全色数;星极图中图分类号:TQ92文献标识码：A1基本概念和引理与图的分数着色有关的研究最早可以追溯到1970年对图的多重着色的研究.E.R.Scheinerman和D.H.Ullman在[1]中有关于此专题的较为详尽的论述.图的分数色数有着十分广泛的应用,例如MWIS问题.处理这个问题的模型是无向图G=(V,E).图中每个顶点表示一台处理器,顶点与顶点之间存在边当且仅当顶点所代表的处理器之间有共享的资源.MWIS问题等价于分数着色问题.研究特殊图形的分数色数有助于解决特殊多处理器结构下的MWIS问题,相关内容可参考[2,3].关于齿顶边星图(m1,m2,…,mn),,蛛网图W(m,n)的定义可参考[4,5,6].在G的r-冠图中,顶点v上粘接的r条悬挂边的端点集记作v*.(本文只考虑无向、简单、有限图.文中涉及的符号和标记若没有特别说明,则与[7]一致)2.主要定理以及证明本文给出了齿顶边星图、、蛛网图以及它们的r-冠图的几种分数色数如下：定理2.1f((m1,m2,…,mn))=2;incf((m1,m2,…,mn))=max{n+1,+3};((m1,m2,…,mn))=max{n+1,+3}.定理2.2f()=;incf()=;()=.定理2.3f(W(m,n))=;incf(W(m,n))=;(W(m,n))=.定理2.4f(Ir((m1,m2,…,mn)))=2;incf(Ir((m1,m2,…,mn)))=max{n+r+1,+r+3};(Ir((m1,m2,…,mn)))=max{n+r+1,+r+3}.定理2.5f(Ir())=;incf(Ir())=;(Ir())=2m+r+1.定理2.6f(Ir(W(m,n)))=;incf(Ir(W(m,n)))=;(Ir(W(m,n)))=.由于篇幅有限,这里只给出定理2.6的详细证明过程,用类似的方法可证明其他结论.定理2.6证明:(1)当n为偶数时,一方面Ir(W(m,n))中存在K3,由f(K3)=3知(Ir(W(m,n)))3.另一方面,在W(m,n)中记从内到外第j(1jm)个圈相对应的n个顶点为uj1,uj2,…,ujn;相对应的n个外部悬挂点为t1,t2,…,tn;中心顶点为x.对于uji(1jm,1in),若i+j=奇数,则着颜色1.若i+j=偶数,则着颜色2;t1,t2,…,tn和中心顶点x着颜色3.中顶点均着颜色3;,,…,和中顶点均着颜色1或2.从而Ir(W(m,n))存在正常3着色,即(Ir(W(m,n)))3.故有(Ir(W(m,n)))=3.当n为奇数时,构造Ir(W(m,n))的(3n-1):(n-1)着色.对于集合{1,2,…,3n-1},当j为奇数时,顶点uj1,uj2,…,ujn分别分配子集{1,2,…,n-1},{n,…,2n-2},{2n-1,2n,1,2,…,n-3},{n-2,n-1,…,2n-4},…,{n+4,…,2n,1,2},{3,…,n,n+1},{n+2,…,2n}.也就是说,用前2n个元素的集合{1,2,…,2n}循环分配给uj1,uj2,…,ujn.每个顶点分配n-1个元素;当j为偶数时,顶点uj1,uj2,…,ujn分别分配子集{n,…,2n-2},{2n-1,2n,1,2,…,n-3},{n-2,n-1,…,2n-4},…,{3,…,n,n+1},{n+2,…,2n},{1,2,…,n-1};t1,t2,…,tn和中心顶点x均分配{2n+1,2n+2,…,3n-1};中顶点分配{2n+1,2n+2,…,3n-1};,,…,和中顶点可分配{1,2,…,2n}中的任意n-1个元素.由定义,这就是Ir(W(m,n))的(3n-1):(n-1)着色.从而f(Ir(W(m,n))).另一方面,构造Ir(W(m,n))的分数团g,使得=:对任意y{u11,u12,…,u1n},有g(y)=;若y=x,有g(y)=1;若yV(Ir(W(m,n)))-{x,u11,u12,…,u1n},有g(y)=0.下面证明对任意Ir(W(m,n))中的极大独立集S,有1(所谓极大独立集S是指,对于任意yV(Ir(W(m,n)))且yS,有S{y}不是独立集).由g的定义可知,要使的值最大,独立集中要尽可能多地包含最内圈中顶点或包含顶点x.若S中包含x,则S不包含最内圈中任何顶点,从而有=1;若S中存在最内圈中顶点,则S包含该圈的最大独立集但不包含x.由于长为n的奇圈的最大独立集基数为,从而有=1.所以对任意Ir(W(m,n))中的极大独立集S,有1.从而对任意Ir(W(m,n))中的独立集S,有1.根据定义,g是Ir(W(m,n))的分数团.从而有f(Ir(W(m,n)))=.综合上述两方面,当n为奇数时,f(Ir(W(m,n)))=.(2)设中的顶点分别是x1,x2,…,xr,相对应的各条悬挂边分别记为e1,e2,…,er;边xu11,xu12,…,xu1n分别记为e1,e2,…,en.显然有(S(Ir(W(m,n))))=.从而incf(Ir(W(m,n))).下面证明inc(Ir(W(m,n)))=.定义:图G...