復(fù)合圖的L（2，1）-標(biāo)號(hào).pdf

1、圖G的L(2，1)一標(biāo)號(hào)是一個(gè)從點(diǎn)集V(G)到非負(fù)整數(shù)集上的函數(shù)f，滿足條件：(1)|f(u)-f(v)|≥2，若uv∈E(G)；(2)|f(u)-f(v)|≥1，若d(u，v)=2．圖G的L(2，1)-標(biāo)號(hào)數(shù)定義為：λ(G)=minfmax{f(v)：v∈V(G))。圖G的L(2，1)-標(biāo)號(hào)來(lái)自于頻道分配問(wèn)題：不同的電臺(tái)要使用無(wú)線電波發(fā)送信號(hào)，為了避免相互干擾，位置十分接近的電臺(tái)要使用相差足夠遠(yuǎn)的頻道，位置較近的電臺(tái)要使用有一定相差的

2、頻道。將頻道分配給電臺(tái)，目標(biāo)是在保證電臺(tái)互不干擾的前提下使用最少的頻道資源． 通常情況下每個(gè)電臺(tái)不止有一個(gè)頻道，本文討論了在每個(gè)電臺(tái)不止有一個(gè)頻道時(shí)的頻道分配問(wèn)題，建立的模型為復(fù)合圖G[H<,v<,1>>，H<,v<,2>>，…，HH<,v<,m>>]的L(2，1)-標(biāo)號(hào)。圖G中的點(diǎn)v<,i>代表電臺(tái)，圖凰v<,i>代表電臺(tái)v<,i>中的頻道。文章的第一章主要介紹了圖的L(2，1)一標(biāo)號(hào)的定義和一些基本的定理。 在第二章

3、中，先得到了復(fù)合圖的一些基本性質(zhì)，接著通過(guò)構(gòu)造一個(gè)算法對(duì)復(fù)合圖中的子圖凰進(jìn)行標(biāo)號(hào)，由此說(shuō)明了如果子圖凰的點(diǎn)數(shù)都等于n且沒(méi)有洞，即圖凰的補(bǔ)圖存在Hamilton路。 第三章中再對(duì)一些基本的圖類(lèi)進(jìn)行考慮，得到當(dāng)G為Pm(m≥2)時(shí)．Pm[K<'c><,n>]的L(2，1)-標(biāo)號(hào)數(shù)；證明了當(dāng)G為樹(shù)時(shí)T[K<'c><,n>]的L(2，1)-標(biāo)號(hào)數(shù)為(△+1)n或(△+1)n+1，并給出了當(dāng)H<,v<,i>>的點(diǎn)數(shù)不相同的情況時(shí)λ(T[K