

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、山東大學(xué)博士學(xué)位論文圖的圓染色及(g,f)-染色理論的若干結(jié)果姓名:閆曉霞申請(qǐng)學(xué)位級(jí)別:博士專業(yè):運(yùn)籌學(xué)與控制論指導(dǎo)教師:劉桂真20030328山東大學(xué)博士學(xué)位論文圖的圓染色及( F ,,) 一染色理論的若干結(jié)果閏 曉 霞山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院摘要若S 是一個(gè)有限集,我們用㈦表示S 中元素的個(gè)數(shù).對(duì)于實(shí)數(shù)o ,用l z l 表示不大于實(shí)數(shù)z 的最大整數(shù),用『。] 表示不小于實(shí)數(shù)X 的最小整數(shù).給定正整數(shù)i ,J ,我們用g c d
2、( i ,J ) 表示i 與J 的最大公約數(shù).除非特別指出,本文所考慮的圖均是有限無(wú)向簡(jiǎn)單圖.我們用V ( G ) 和E ( C ) 分別表示圖G 的頂點(diǎn)集合和邊集合.用d G ( u ) 表示頂點(diǎn)Z t 在圖G 中的度,用A ( G ) 表示G 的最大度,用5 ( G ) 表示G 的最小度.C [ V 。] 表示G 的由頂點(diǎn)子集I /導(dǎo)出的子圖,G 【E ’] 表示G 的由邊子集E ’導(dǎo)出的子圖.%表示n 個(gè)頂點(diǎn)的完全圖.Q ( G
3、) 表示G 的獨(dú)立數(shù),x ( G ) 表示G 的色數(shù).文中所用術(shù)語(yǔ)與符號(hào)基本與文獻(xiàn)?1 中一致.定義1 .21 設(shè)C 是長(zhǎng)度為r 的圓周,圖G 的一個(gè)r 一圓染色是一個(gè)映射c :X ∈以G ) r _ c 上的一段單位長(zhǎng)度的開(kāi)弧c ( z ) ,使得當(dāng)( X ,Y ) ∈E ( C ) 時(shí),c ( x ) N c ( y ) = 0 .如果G 有r 一圓染色,我們就稱G 是r 一圓可染色的.圖G 的圓色數(shù)記作x 。( G ) ,定義為:
4、x 。( G ) = i n f { r :G 是r 一圓可染色的} .圖G 的圓包數(shù)x 。( G ) 最初是在1 9 8 8 年由V i n c e 提出的,當(dāng)時(shí)稱之為“星色數(shù)”,上面的定義不是V i n c e 的原始定義,是Z h uX u d i n g 在文獻(xiàn)[ 2 】中給出的一個(gè)等價(jià)定義. V i n c e 給出的定義是這樣的:定義1 .2 .2 對(duì)兩個(gè)正整數(shù)k ,d ,1Sd 曼k ,圖G 的一個(gè)( k ,d ) 一染色
5、是一個(gè)染色C .所用顏色集合為{ o ,1 ,?,k 一1 ) ,使得( z .Y ) ∈E ( G ) = } dSJ c 扣) 一c ( ∥) } ≤k —d圓色數(shù)定義為:x 。( G ) = i n f { ;:存在G 的( %,d ) 一染色} . U圖的圓染色的另一等價(jià)定義是由G o d d y n ,T a r s i 和Z h a n g 在文獻(xiàn)【3 】中提出的,這個(gè)定義將圖的染色與網(wǎng)絡(luò)的流聯(lián)系起來(lái).給定圖G 的一個(gè)( k
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 圖的f-染色的若干結(jié)果.pdf
- 圖的邊共染色的若干結(jié)果.pdf
- 關(guān)于圖的對(duì)策染色數(shù)的若干結(jié)果.pdf
- 圖的圈和路因子理論的若干結(jié)果及對(duì)平面圖中全染色猜想的研究.pdf
- 圖的圓色數(shù)的若干結(jié)果.pdf
- 邊染色圖中的匹配、圈及圖的圓染色.pdf
- 若干圖的染色.pdf
- F-調(diào)和映照的若干結(jié)果.pdf
- 圖的f-染色和均勻邊染色.pdf
- 有關(guān)平面圖的邊面染色的若干結(jié)論.pdf
- 18715.若干圖的邊染色和全染色
- 共色理論中的若干結(jié)果.pdf
- 關(guān)于反射對(duì)稱圖的若干結(jié)果.pdf
- 帶位勢(shì)F-調(diào)和映射的若干結(jié)果.pdf
- 幾類圖的若干染色問(wèn)題.pdf
- 圖的若干染色問(wèn)題研究.pdf
- 圖的若干染色問(wèn)題的研究.pdf
- 若干圖類的對(duì)策染色和鄰強(qiáng)邊染色.pdf
- 保險(xiǎn)風(fēng)險(xiǎn)模型破產(chǎn)理論的若干結(jié)果.pdf
- 關(guān)于分?jǐn)?shù)消去圖的若干結(jié)果.pdf
評(píng)論
0/150
提交評(píng)論