论文部分内容阅读
图的T-染色的概念起源于通信领域中的频率分配问题.由于电磁波的自然特性,无线通信设备发射的电磁波可能对位于附近且满足一定功率和频率条件的其它设备形成干扰.频率分配问题的图论模型可以这样得到:令收发信机为图中的点,两点之间有边当且仅当这两个收发信机干扰.重图的T-染色是图的T-染色的一个较为实用的部分,这是因为在研究频率分配时,干扰可能会在不同的水平上发生.由于一个重图G能够被剖分成K个不同部分,我们可以用G(V,G<,0>,G<,1>,….,G<,K-1>)来表示G.重图G(V, G<,0>,G<,1>,…,G<,K-1>)的一个T-染色是指一个函数f,f满足同时是G<,i>的T(i)染色,即:对工Ai=0,1,….,K-1,{x,y}∈E(G<,i>) |f(x)-f(y)|T(i).G的f染色的色数是指值不同的f(x)的个数,记作:X<,T>(f),其中x∈V(G).G的f染色的匝等于max|f(x)-f(y)|,记作:sp<,T>(f),其中{x,y}∈E(G).G的T-染色的色数和匝分别记作X<,T>(G)和sp<,T>(G),当f取遍所有G的T-染色时,X<,T>(G)=minX<,T>(f),dp<,T>(G)=min sp<,T>(f).本文将给出一些关于简单图和重图的已知结论,同时还将给出一种计算重图的spT的新算法,并将讨论取特殊T集时重图的T-匝算法以及完全图Kn的T-匝算法.