MWIS问题模型中几类图形的分数色数

1、MWIS问题模型中几类图形的分数色数高炜 梁立* 夏幼明(云南师范大学计算机科学与信息技术学院,云南 昆明 650092)摘要：图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用,例如MWIS问题.给出了齿顶边星图、蛛网图以及它们的r-冠图的分数色数、分数关联色数和分数全色数.关键词：分数色数；分数团；分数关联色数; 分数全色数; 星极图中图分类号: TQ92 文献标识码： A1 基本概念和引理 与图的分数着色有关的研究最早可以追溯到1970年对图的多重着色的研究. E.R.Scheinerman和D.H.Ullman在1中有关于此专题的较为

2、详尽的论述. 图的分数色数有着十分广泛的应用, 例如MWIS问题. 处理这个问题的模型是无向图G = (V, E) . 图中每个顶点表示一台处理器,顶点与顶点之间存在边当且仅当顶点所代表的处理器之间有共享的资源. MWIS问题等价于分数着色问题.研究特殊图形的分数色数有助于解决特殊多处理器结构下的MWIS问题,相关内容可参考2,3. 关于齿顶边星图(m1,m2,mn),蛛网图W(m,n) 的定义可参考4,5,6. 在G的r-冠图中,顶点v上粘接的r条悬挂边的端点集记作v*. (本文只考虑无向、简单、有限图.文中涉及的符号和标记若没有特别说明,则与7一致)2.主要定理以及证明本文给出了齿顶边星图

3、、蛛网图以及它们的r-冠图的几种分数色数如下：定理2.1 f (m1,m2,mn)=2; incf (m1,m2,mn)=maxn+1, +3; (m1,m2,mn)= maxn+1, +3.定理2.2 f ()=; incf ()=; ()=.定理2.3 f (W(m,n)= ; incf (W(m,n)= ; ( W(m,n)=.定理2.4f (Ir(m1,m2,mn)=2; incf (Ir(m1,m2,mn)=maxn+r+1,+r+3; (Ir(m1,m2,mn)=maxn+r+1, +r+3.定理2.5f (Ir()=; incf (Ir()= ;(Ir()=2m+r+1.定理2.

4、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. 中顶点均着

5、颜色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分别分配

6、子集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,使得=:对任意yu11, u12,u1n,有g(y)=;若y=x,有g(y)=1;若yV(Ir(W(m,n)- x, u11, u12,u1n,有g(y)=0.下

7、面证明对任意Ir(W(m,n)中的极大独立集S,有1(所谓极大独立集S是指,对于任意yV(Ir(W(m,n)且yS,有Sy不是独立集).由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

8、(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的关联图S(G)的某个正常着色具有性质P,是指:yV(G),设NG(y)=y1,y2,yk,则(y1,y1 y),( y2, y2 y),( yk, yk y)着相同的颜色. 当n=3时,首先用6种(因为r1,因此当n=3时,r+56)颜色着S(W(m,3),并且在不考虑中心顶点x的情况下,使该着色具有性

9、质P: (x,e1),(x,e2),(x,e3)分别着1,2,3; (u11,e1),(u12,e2)着4;(u13,e3)着6;( u11, u11u12), ( u12, u11u12), ( u12, u12u13), ( u13, u12u13), ( u13, u13u11), ( u11, u13u11)分别着2,1,3,2,1,3; ( u11, u11u21), ( u12, u12u22), ( u13, u13u23)分别着5,6,4; ( u21, u11u21), ( u22, u12u22), ( u23, u13u23)分别着1,2,3.( u22, u21u22)

10、 , ( u23, u23u21), ( u31, u31u21)均着5; ( u21, u21u22) , ( u23, u23u22), ( u32, u32u22)均着6; ( u21, u21u23) , ( u22, u23u22), ( u33, u33u23)均着4; ( u21, u21u31)着2,( u32, u32u31), ( u33, u33u31)着2;( u22, u22u32)着3, ( u23, u23u33)着1; ( u31, u31u32), ( u33, u33u32)着3; ( u31, u31u33), ( u32, u33u32)着1;( u31

11、, u31u41)着 4, ( u51, u51u41), ( u42, u42u41), ( u43, u43u41)着4; ( u32, u32u42), ( u41, u41u42), ( u43, u43u42), ( u52, u52u42)着 5; ( u33, u33u43), ( u41, u41u43) ,( u42, u43u43) ,( u53, u53u43)着 6;(u41, u41u51)着 1, ( u61, u61u51), ( u52, u52u51), ( u53, u53u51)着1; ( u42, u42u52), ( u51, u51u52), ( u

12、53, u53u52), ( u62, u62u52)着 2; ( u43, u43u53), ( u51, u51u53) ,( u52, u52u53) ,( u63, u63u53)着 3; ( u51, u51u61)着 1, ( u71, u71u61), ( u62, u62u61), ( u63, u63u61)着5; ( u52, u52u62), ( u61, u61u62), ( u63, u63u62), ( u72, u72u62)着 6; ( u53, u53u63), ( u61, u61u63) ,( u62, u62u63) ,( u73, u73u63)着 4

13、.我们发现,第6圈的着色和第2圈是一样的,因此第7圈的着色可与第3圈一样, ,以此构成循环,可以一直着下去. 其次,将S(W(m,3)的6着色推广到S(Ir(W(m,3).对于W(m,3)的中心顶点x而言,(x, e1),(x,e2),(x, er)分别着5,7,8,r+5;而(x1, e1),( x2,e2), (xr, er)可着4或6;对于uji,设在S(W(m,3)中包含在W(m,3)中与uji关联的4条边的顶点的颜色集为Uji，则=5.设中元素分别为,则(uji, uji), (uji,uji),(uji, uji)分别各着集合1,2,r+5-Uji中的一种颜色,而(, uji),

14、(,uji),(, uji)均着与在S(W(m,3)中包含在W(m,3)与uji相关联的边和相邻的顶点所组成的顶点一样的颜色. 例如:对于点u11,顶点(x,e1), ( u12, u11u12), ( u13, u13u11), ( u21, u11u21)所着的颜色均为1，则(, u11), (,u11),(, u11)均着1.用同样的方法可处理与t1,t2,t3相关的顶点的着色.从而S(Ir(W(m,3)是r+5可着色的. 当n=4,m2时,S(W(m,4)可用5种颜色正常着色, 且使着色具有性质P: (x,ei)着i(1i4); (u1i,ei)着5 i(1i4);从而(u12, u1

15、2u11) ,(u14, u14u11) ,(u21, u11u21)着1; (u13, u12u13) ,(u11, u12u11) ,(u22, u12u22)着2;(u12, u12u13), (u14, u14u13) ,(u23, u13u23)着3;(u11, u14u11) ,(u13, u14u13), (u24, u14u24)着4;因此(u11, u21u11), (u22, u22u21) ,(u24, u24u21),(t1,t1u21)着3; (u12, u22u12), (u21, u22u21) ,(u23, u23u22),(t2,t2u22)着4;(u13,

16、u23u13), (u22, u22u23) ,(u24, u24u23),(t3,t3u23)着1; (u14, u24u14), (u21, u24u21) ,(u23, u24u23),(t4,t4u24)着2; (u21,t1u21), (u22,t2u22), (u23,t3u23), (u24,t4u24)着5. 类似n=3的讨论,可知该S(W(m,4)的5着色可推广到S(Ir(W(m,4)的r+5着色. 当n=4,r2 m3时, n+r+17,下面给出S(W(m,4)的满足性质P的正常7着色: (x,ei)着i(1i4); (u1i,ei)着5 (1i4);从而(u12, u12

17、u11) ,(u14, u14u11) ,(u21, u11u21)着1; (u13, u12u13) ,(u11, u12u11) ,(u22, u12u22)着2;(u12, u12u13), (u14, u14u13) ,(u23, u13u23)着3;(u11, u14u11) ,(u13, u14u13), (u24, u14u24)着4; (u11, u21u11), (u22, u22u21) ,(u24, u24u21),( u31, u31u21)着3; (u12, u22u12), (u21, u22u21) ,(u23, u23u22),( u32, u32u22)着6;

18、(u13, u23u13), (u22, u22u23) ,(u24, u24u23),(u33, u33u23)着1; (u14, u24u14), (u21, u24u21) ,(u23, u24u23),( u34, u34u24)着7; (u21, u21u31), (u32, u32u31) ,(u34, u34u31),( u41, u31u41)着5; (u22, u22u32), (u31, u32u31) ,(u33, u33u32),( u42, u42u32)着4; (u23, u23u33), (u32, u32u33) ,(u34, u34u33),(u43, u33

19、u43)着2; (u24, u24u34), (u31, u34u31) ,(u33, u34u33),( u44, u34u44)着6;(u31, u41u31), (u42, u42u41) ,(u44, u44u41),( u51, u51u41)着1; (u32, u42u32), (u41, u42u41) ,(u43, u43u42),( u52, u52u42)着7; (u33, u43u33), (u42, u42u43) ,(u44, u44u33),(u53, u53u43)着3; (u34, u34u44), (u41, u44u41) ,(u43, u44u43),(

20、u54, u54u44)着4;(u41, u41u51), (u52, u52u51) ,(u54, u54u51),( u61, u61u51)着3; (u42, u42u52), (u51, u52u51) ,(u53, u53u52),( u62, u62u52)着6; (u43, u43u53), (u52, u52u53) ,(u54, u54u53),(u63, u63u53)着1; (u44, u54u44), (u51, u54u51) ,(u53, u54u53),( u64, u54u64)着7;(u51, u61u51), (u62, u62u61) ,(u64, u64

21、u61),( u71, u61u71)着5; (u52, u62u52), (u61, u62u61) ,(u63, u63u62),( u72, u62u72)着4; (u53, u53u63), (u62, u62u63) ,(u64, u64u63),(u73, u63u73)着2; (u54, u54u64), (u61, u64u61) ,(u63, u64u63),( u74, u74u64)着6;(u61, u61u71),着1; (u62, u62u72)着7; (u63, u63u73)着3; (u64, u64u74)着4.由此,我们发现第6层相关顶点的着色和第3层完全一致

22、,从而得到一个循环,第7层的相关着色和第4层一致, 第8层的相关着色和第5层一致, .这就是S(W(m,4)的满足性质P的正常7着色类似n=3的讨论,可知该S(W(m,4)的7着色可推广到S(Ir(W(m,4)的r+5着色.当n5时,首先用n+1种颜色着S(W(m,n),并使得着色具有性质P.方法如下(设该着色为):(x,ei)=i(1in); (u11,e1)=( u12,e2)=(u1n,en)=n+1.从而(u12, u11u12)= (u1n, u11u1n)=(u21, u11u21)=1;(u11, u11u12)=(u13, u12u13)=(u22, u12u22)=2; ;

23、(u11, u11u1n)=(u1(n-1), u1(n-1)u1n)=(u2n, u1nu2n)=n; (u1i, u1i u2i)= (x,ei)+2(mod n); (uji, uji u(j+1)i)= ( u(j-1)i, u(j-1)i uji)+2 (mod n)(2jm); ( u(j+1)i, uji u(j+1)i)= ( uji, u(j-1)i uji)+2 (mod n)(2jm); (uji, uji uj(i+1)=(u(j-1)i, u(j-1)i u(j-1)(i+1)+2 (mod n); (uji, uji uj(i-1)=(u(j-1)i, u(j-1)

24、i u(j-1)(i-1)+2 (mod n); (umi, umi ti)=(u(m-1)i, u(m-1)i umi)+2 (mod n); ( ti, umi ti)=(umi, u(m-1)i umi)+2 (mod n).下面证明,这就是S(W(m,n)的n+1正常着色且具有性质P.观察即知,对W(m,n)中的顶点u1i来说,(x,xu1i),( u1(i+1), u1(i+1) u1i) ,( u1(i-1), u1(i-1) u1i) ,( u2i, u2iu1i)所着颜色相同.而对于uji(2jm)来说,由于每一层的相关元素的色数为上一层加2,因此和uji相邻的点和相关联的边构

25、成的S(W(m,n)中的顶点所着的颜色相同.所以只需说明是正常着色即可.直接观察可知,第一层着色是正常的.由于着色是每一层对应元素加2(mod n),因此只需验证第2层即可.对于W(m,n)中的顶点u2i,(u2i,u2(i+1)u2i)与10个顶点相邻,它们是(u1i,u1iu2i), ( u2i,u2iu1i), (u2(i-1), u2(i-1)u2i),(u2i,u2(i-1)u2i), (u3i,u3iu2i), (u2i,u3iu2i), (u2(i+1),u2(i+1)u2i) , (u2(i+1),u2(i+1) u2(i+2), (u2(i+1),u2(i+1) u1(i+1

26、) ,( u2(i+1),u2(i+1) u3(i+1).其中(u1i,u1iu2i), (u2(i-1), u2(i-1)u2i), (u3i,u3iu2i), (u2(i+1),u2(i+1)u2i)着相同的颜色i+2;( u2i,u2iu1i)着颜色i; (u2i,u3iu2i)与(u2(i+1),u2(i+1) u2(i+2),着相同的颜色i+4; (u2i,u2(i-1)u2i)和 (u2(i+1),u2(i+1) u1(i+1)着i+1; ( u2(i+1),u2(i+1) u3(i+1)着i+5.从而这10条边一共着5种颜色i,i+1, i+2, i+4, i+5 (mod n)

27、.而(u2i,u2(i+1)u2i)本身着i+3 (mod n)，因此(u2i,u2(i+1)u2i)不和它的邻边着相同的颜色.同理, (u2i,u2(i-1)u2i)也不和它的邻边着相同的颜色.另外与( u2i,u2iu1i)相邻的10条边着i+1, i+2, i+3, i+4, n+1(当j3时该值为i-2), i-1,6种颜色,而( u2i,u2iu1i)本身着颜色i,所以( u2i,u2iu1i)不和相邻的边着相同的颜色(着相同颜色的两条边的颜色差为0或n的整数倍,但n5). 与(u2i,u3iu2i)相邻的10条边着i,i+1, i+2,i+3,i+5,i+6,而(u2i,u3iu2

28、i)本身着i+4,所以(u2i,u3iu2i)不和相邻的边着相同的颜色.因此与W(m,n)中第二层顶点相关的S(W(m,n)中的顶点着色正常.从而是S(W(m,n)的正常n+1着色. 类似n=3的讨论,可知该S(W(m,n)的n+1着色可推广到S(Ir(W(m,n)的n+r+1着色. 从而incf (Ir(W(m,n) . 故incf (Ir(W(m,n)= .(3) 显然有(T(Ir(W(m,n)= .从而(Ir(W(m,n) . 下面证明(Ir(W(m,n)= .当n=3时,首先给出T(W(m,3)的5着色如下: (x)= ( u11u21)=1, (e1)=(u13)= ( u12u22

29、)= (u21)=2, (e2)=( u11)=( u13u23)= (u22)=3,(e3)= (u23)=4,(u12)=5, (uj1uj2)=4 (1jm), (uj2uj3)=1(1jm),(uj3uj1)=5(1jm), (uji)= ( u(j-1)i u(j-2)i) (1i3, 3jm),( uji u(j-1)i)= (u(j-2)i) (1i3, 3jm).最后, (ti)= (umiu(m-1)i); (tiumi)= (u(m-1)i). 从而由内到外,可得到T(W(m,n)的5着色.其次, T(W(m,3)的5着色可扩展到T(Ir(W(m,3)的r+5着色:对于W(

30、m,3)中任意一点的r条悬挂边可分别着与该点和该点关联边不同的颜色,对于该点的r个悬挂点可着与该点在W(m,3)中的某一条关联边相同的颜色.当n4时,首先给出T(W(m,n)的n+1着色如下: (x)=n+1;(ei)=i(1in); (u1i)=i+1(mod n)(1in); (ujiuj(i+1)=i-1 (mod n) (1jm,1in); (u1iu2i)=n+1(1in);(u2i) =i (1in);继续扩展: (ujiu(j+1)i)= (u(j-1)i) (2jm,1in); (uji)= (u(j-1)iu(j-2)i) (3jm,1in); (ti)= (umiu(m-1

31、)i); (tiumi)= (u(m-1)i).易证,可将T(W(m,n)的n+1着色扩展到T(Ir(W(m,n)的n+r+1着色.从而(Ir(W(m,n) . 故(Ir(W(m,n)= . (证毕)3.一些推论根据以上得到的结论再结合分数色数与圆色数的关系,我们得到如下推论:推论3.1 (m1,m2,mn)=(m1,m2,mn)=2;(S(m1,m2,mn)= (S(m1,m2,mn) = maxn+1, +3;(T(m1,m2,mn)= (T(m1,m2,mn) = maxn+1, +3.推论3.2 ()=()=2 (n为偶数); (S()=(S()=2m+1(m2或m=1, n=3k);

32、 (T()=(T()=2m+1(m2或m=1, n=3k).推论3.3 (W(m,n)=(W(m,n)= 3(n为偶数); (S(W(m,n)=(S(W(m,n)= ; (T(W(m,n) =(T( W(m,n) =.推论3.4(Ir(m1,m2,mn)=(Ir(m1,m2,mn)=2; (S(Ir(m1,m2,mn)= (S(Ir(m1,m2,mn)= maxn+r+1,+r+3;(T(Ir(m1,m2,mn)= (T(Ir(m1,m2,mn)= maxn+r+1,+r+3.推论3.5(Ir()=(Ir()=2 (n为偶数);(S(Ir()=(S(Ir()=2m+r+1 (m=1, n=5,

33、 r=1不同时成立);(T(Ir()=(T(Ir()=2m+r+1.推论3.6(Ir(W(m,n)=(Ir(W(m,n)=3(n为偶数); (S(Ir(W(m,n)=(S(Ir(W(m,n)= ; (T(Ir(W(m,n)=(T(Ir(W(m,n)= .注:推论中所述所有图形均为星极图.4.遗留问题本文主要研究了若干具有特殊结构图形的分数色数,从而为解决MWIS问题提供了理论依据.但根据以上得到的结论,对于蛛网图及其r-冠图,还有如下两个问题没有解决:（1）n=3,m2以及n=4, m3时W(m,n)的分数色数是多少？（2）n=4,r=1, m3时Ir(W(m,n)的分数色数是多少？这两个问题有待进一步研究.参考文献:1. Fractional Graph TheoryM. John Wiley and Sons, Inc.New York,1997.2高炜,梁立,张超. 超图的分数着色研究J. 云南师范大学学报(自然科学版). 2009, 29(1): 33-36.3高炜,梁立,夏幼明. 几种特殊图形的分数色数研究J. 山西师范大学学报(自然科学版). 2008,22(4):16-20.4刘玉记. 一类图的优美性J. 四川师范大学学报(自然科学版). 1995, 18(2):52-60.5卜长江,高振滨. 网图F (m , n1, n2, , nm )