圖的頂點標號及L（0，1）-邊跨距.pdf

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

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

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

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

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