圖的頂點(diǎn)標(biāo)號(hào)及L（0，1）-邊跨距.pdf

1、山東大學(xué)碩士學(xué)位論文圖的頂點(diǎn)標(biāo)號(hào)及L（0，1）-邊跨距姓名：李雙成申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：劉家壯20040330山東大學(xué)碩士學(xué)位論文圖的頂點(diǎn)標(biāo)號(hào)及L ( 0 ，1 ) - 邊跨距李 雙 成( 山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，濟(jì)南2 5 0 1 0 0 )中文摘要圖l 的頂點(diǎn)標(biāo)號(hào)問題最早是從圖的L ( 2 ，1 ) - 標(biāo)號(hào)開始研究的，它們的應(yīng)用背景是H a l e [ 2 】在1 9 8 0 年提出的無(wú)線電頻率分配問

2、題：給定一些無(wú)線電發(fā)射臺(tái)，我們要求對(duì)每個(gè)無(wú)線電發(fā)射臺(tái)分配一個(gè)頻率，使得相互干擾的無(wú)線電發(fā)射臺(tái)所分配頻率的間隔在允許的范圍之內(nèi)．在隨后近十年里，頻率分配同題一直作為r 一染色問題被廣泛的研究( 文獻(xiàn)【3 ] 【4 ] ) ．1 9 8 8 年，在同J ，G r i g g s 的私人通信中。F ．R o b e r t s 建議用一些非負(fù)的正整數(shù)來(lái)表示頻率，使得相近的站點(diǎn)分配到不同的頻率，而相鄰的站點(diǎn)所分配的頻率至少相差2 ，從而使各個(gè)站

3、點(diǎn)不會(huì)相互干擾．在此建議下，G ．J ．C h a n g 和D ，K o u [ 1 2 】在1 9 9 3 年給出了L ( 2 ，1 ) 一標(biāo)號(hào)的精確定義：給定正整數(shù)k ．對(duì)任意的圖G ，它的k —L ( 2 ，1 ) 一標(biāo)號(hào)是一個(gè)函數(shù)，：v ( G ) ．+ { o ，1 ，?，％) ，使得對(duì)于G 中的任意兩個(gè)頂點(diǎn)“和u ，如果d ( u ，“ ) = 1 ，則有I f ( u ) 一／( v ) l ≥2 ；如果d ( “，“

4、) = 2 ，則有l(wèi) ，( u ) 一，( “ ) I ≥1 ．圖G 的￡{ 2 ，1 ) 一標(biāo)號(hào)數(shù)A 2 。t ( G ) 是一個(gè)使得圖G 有一個(gè)L ( 2 ，1 ) 一標(biāo)號(hào)的最小數(shù)k 。在2 0 0 0 年，G ．J ．C h a n g 等人【2 0 】又將圖的L ( 2 ，1 ) 一標(biāo)號(hào)問題推廣到圖的L ( d ，1 ) - 標(biāo)號(hào)。并證明了對(duì)于最大度為△的一般圖，它的L ( d ，1 ) 一標(biāo)號(hào)數(shù)A d ，I ( G ) SA

5、2 + ( d 一1 V , ．在證明的過程中，他們提供了一種求標(biāo)號(hào)數(shù)的方法：通過不斷的求圖G 的極大的穩(wěn)定子集，最終能夠在多項(xiàng)式時(shí)間內(nèi)把所有的頂點(diǎn)予以標(biāo)號(hào)．在這一方法的啟示下，邵振東博士【2 9 】把圖的L ( d ，1 ) 一標(biāo)號(hào)問題推廣到圖的L ( d L ，d 2 ) - 標(biāo)號(hào)，L ( n ，n 一1 ，·h 1 ) - - 標(biāo)號(hào)以及L ( d l ，d 2 ，?，如) 一標(biāo)號(hào)問題，給出了最大度為△的一般圖的各個(gè)標(biāo)號(hào)數(shù)