重图的T-染色

An algorithm to compute the span of the T-Colorings of multigraphs

重图的T-染色是图的T-染色的一个较为实用的部分,这是因为在研究频率分配时,干扰可能会在不同的水平上发生。由于一个重图G能够被剖分成K个不同部分,用G(V,G0,G1,……,GK-1)来表示G。重图G(V,G0,G1,…,GK-1)的一个T-染色是指一个函数f,f满足同时是Gi的T(i)染色,即:对i=0,1,……,K-1,{x,y}∈E(Gi)|f(x)-f(y)|T(i)。G的f染色的色数是指值不同的f(x)的个数,记作:XT(f)。其中x∈V(G)。G的f染色的跨度等于m ax|f(x)-f(y)|,记作:spT(f),其中{x,y}∈E(G)。G的T-染色的色数和跨度分别记作XT(G)和spT(G),当f取遍所有G的T-染色时,XT(G)=m inXT(f),spT(G)=m inspT(f)。本文将给出一些关于重图的T-染色的已知结论,同时还将给出一种计算重图的spT的新算法。

The T-colorings of muhigraphs is a more practical case of T-colorings of graphs where interference may occur on different level. A multigraph G can be partitioned into K distinct sets, so G is represented as G （ V, G0 ,G1 ,G2 ,… ,GK-1 ）. A T-coloring of G（ V, G0,G1 ,G2 ,… ,GK-1 ） is a function f satisfying that it is simultaneously a T（i） -coloring of Gi for all i, i. e. , so that for i = 0, 1,…, K-1, { x,y } E E （ Gi ） → If（x） - f（y） I ∈ T（i）. The order of a T-coloringfof G is the number of distinct values off（x） ,x ∈ V（G）. The span of a T-coloring f of G equals max If（x） -f（y） I, where the maximum is taken over all vertex in V（G）. The minimum order, and minimum span,where the minimum is taken over all T-colorings of G,are denoted by XT（ G）, and spr（G） ,respectively. Several previous results of the span of simple graphs and muhigraphs are showed, and a new algorithm to compute spr of multigraphs is presented ,furthermore the bound of the span of a special multigraph and the algorithm of spr（Kn） are discussed.