版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、本文考慮的圖若無特殊聲明均為簡單圖。一個簡單圖的k可邊染色是一個從含k種顏色的色集到圖G的邊集合的映射,并且使得相鄰兩邊染不同的顏色。對于一個k可邊染色的圖G來說,最小的k就是圖G的邊色數(shù)。Vince提出了圖的圓染色的概念,圖的圓邊染色就是圖的圓染色由點到邊的推廣。圖G是一個圖,正整數(shù)k,d滿足2d≤k,那么圖的(k,d)邊染色是指從顏色集{0,1,…,k-1}到圖G的邊的映射c,并且任意相鄰的兩邊e1,e2滿足d≤|c(e1)-c(e
2、2)|≤k-d。圖G的圓邊染色數(shù)x'c(G)就是圖G含有(k,d)邊染色中的k/d比值的下界。即:χ'c(G)=inf{k/d:G含有一個(k,d)邊染色}。 圖的圓邊染色的許多基本性質(zhì)被Hackmann證明: 定理0.1 [3]如果G是一個含有q條邊的圖,那么χ'c(G)=min{k/d:G含有一個(k,d)邊染色且k≤q)。 定理0.2 [3]如果G是第一類圖,那么χ'c(G)=△(G)。 如果G是第
3、二類圖,那么△(G)<χ'c(C)≤△(G)+1。 定理0.3 [3]如果圖G是第二類圖,那么要么χ'c(G)=△(G)+1要么△(G)+1/α'(G)≤χ'c(G)≤△(G)+α'(G)-1/α'(G)(其中α'(G)是圖G的邊獨立數(shù))第一類圖的圓邊染色問題已經(jīng)解決,而許多第二類圖的圓邊染色問題沒有得以解決。所以本文研究的主要是一些第二類圖的圓邊染色性質(zhì)。由于這個問題是一個NP問題,所以本文的思想就是確定某第二類圖的范圍。而確
4、定Χlc(G),就要從定義出發(fā),找尋(k,d)染色。找出上述范圍的k1,k2,k3,…,kn,dl,…,dn,uG=k1/d1/>k2/d2>…>kn/dn=lG,檢驗圖G是否含有(k2,d2)染色,如果沒有,Χlc(G)=k1/d1;如果含有(k2,d2)染色,繼續(xù)檢驗(k3,d3)染色,依次類推。本文根據(jù)以上算法來確定一些圖的圓邊染色。全文共分四章,第一章介紹圖論的一些基本概念,并給出圖的染色理論的已有定理證明及圓邊染色的理論。第二
5、章介紹解決圓邊染色的算法。 第三章我們給出了頂點數(shù)小于7的所有第二類圖的圓邊染色數(shù)。主要結(jié)論有: 定理0.4 在頂點小于7的所有第二類圖中,其圓邊染色數(shù): Χlc(G1)=3,Χlc(G2)=5/2,Χlc(G3)=4,Χlc(G4)=9/2,Χlc(G5)=5,Χlc(G6)=4,Χlc(G7)=5,Χlc(G8)=5。 定理0.5 如果G是一個C3×C3的笛卡爾積圖,那么其圓邊色數(shù)為: Χlc
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 一些圖的圓邊色數(shù).pdf
- 一些圖的均勻鄰強邊染色.pdf
- 13434.圖的邊染色及一些有限制條件的染色
- 圖的點可區(qū)別邊染色的一些結(jié)果.pdf
- 關(guān)于一些圖的定向染色.pdf
- 圖的鄰點可區(qū)別正常邊染色的一些結(jié)果.pdf
- 關(guān)于圖BBC染色的一些結(jié)果.pdf
- 一些圖類的連續(xù)邊著色.pdf
- 關(guān)于圖的邊分解的一些結(jié)果.pdf
- 一些圖的點鄰點可區(qū)別全染色.pdf
- 一些六點九邊圖的圖設(shè)計.pdf
- 一些圖的邊平均Wiener指標(biāo)的研究.pdf
- 一些乘積圖的L(2,1)-圓標(biāo)號.pdf
- 10352.不含相鄰短圈的平面圖的無圈邊染色的一些結(jié)果
- 關(guān)于圖的鄰點可區(qū)別全染色的一些結(jié)果.pdf
- 邊染色圖中的匹配、圈及圖的圓染色.pdf
- 32154.一些完全圖的邊傳遞循環(huán)正則覆蓋
- 11394.一些樹圖的度結(jié)合邊重構(gòu)數(shù)
- 關(guān)于圖的鄰點(強)可區(qū)別全染色的一些結(jié)果.pdf
- 多一些、少一些
評論
0/150
提交評論