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

1、圖G的L(2，1)一標(biāo)號是一個從點集V(G)到非負整數(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)號數(shù)定義為：λ(G)=minfmax{f(v)：v∈V(G))。圖G的L(2，1)-標(biāo)號來自于頻道分配問題：不同的電臺要使用無線電波發(fā)送信號，為了避免相互干擾，位置十分接近的電臺要使用相差足夠遠的頻道，位置較近的電臺要使用有一定相差的

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

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