版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、一個圖G=(V(G),E(G))的邊染色是指從其邊集合E(G)到自然數(shù)子集{1,2,…,r}上的一個滿射C。如果圖G有這樣的一個染色C,我們就稱圖G是一個邊染色圖,或r-邊染色圖,并用C(e)來表示邊e的顏色。給定圖G中的一個頂點ν,頂點ν的色鄰域CN(ν)是指集合{C(e):e與ν關(guān)聯(lián)}。頂點ν的色度記為dc(ν)=|CN(ν)|。一棵樹被稱為單色的是指這棵樹中的所有邊上所染顏色都相同。
1991年,Erdos,Gyar
2、fas和Pyber提出了邊染色圖的單色樹劃分數(shù)的概念。r-邊染色圖G的單色樹劃分數(shù),或簡稱為樹劃分數(shù),記作tr(G),是指最小的k滿足:對于G的任意r-邊染色,圖G的頂點集合可被至多k個頂點不交的單色樹覆蓋。Erdos,Gyarfas和Pyber猜想r-邊染色完全圖的單色樹劃分數(shù)是r-1,其中r≥2,并且他們證明了r=3時猜想的正確性。猜想對于r=2的情況等價于Erdos和Rado的斷言:對任意的圖G,圖G和圖G的補圖至少有一個連通。對
3、于無限完全圖,Hajnal等人證明了一個r-邊染色無限完全圖的單色樹劃分數(shù)至多是r。對于有限完全圖,Haxell和Kohayakawa證明了當n≥3r4r!(1-1/r)3(1-r)logr,任意r-邊染色完全圖Kn含有至多r個兩兩不同色的單色樹,并且他們的頂點集合劃分了Kn的頂點集合。Haxell和Kohayakawa還證明了當n充分大時,r-邊染色的完全二部圖Kn,n的單色樹劃分數(shù)至多是2r。一般地,確定tr(G)的精確的值是很困難
4、的。
與單色樹劃分數(shù)相關(guān)的一個問題是r-邊染色圖G的單色樹覆蓋數(shù),或簡稱為樹覆蓋數(shù),它是指最小的k滿足:對于G的任意r-邊染色,圖G的頂點集合可被至多k個單色樹(可以相交)覆蓋。對于完全圖,以某個點為中心的所有單色星構(gòu)成了一個覆蓋,所以r-邊染色完全圖的單色樹覆蓋數(shù)至多是r。Erdos,Gyarfas和pyber關(guān)于樹劃分數(shù)的猜想的一個弱形式是:r-邊染色完全圖的單色樹覆蓋數(shù)是r-1。
本文分為三部分,第一部
5、分主要研究了2-邊染色完全二部圖的單色樹劃分問題,第二部分主要研究了3-邊染色完全等部二部圖的單色樹劃分問題,第三部分主要研究了2-邊染色和3-邊染色完全二部圖的單色樹覆蓋問題。
第二章中我們研究了2-邊染色完全二部圖的單色樹劃分。對于2-邊染色的完全多部圖K(n1,n2,…,nk),Kaneko,Kano和Suzuki證明了:設(shè)n1,n2,…,nk(2≤k)是滿足1≤n1≤n2≤…≤nk的整數(shù),并且n=n1+n2+…+n
6、k-1,m=nk,則t2(K(n1,n2,…,nk))=[m-2/2n]+2。特別地,t2(Km,n)=[m-2/2n]+2,其中1≤n≤m。金澤民等人在2006年給出了2-邊染色的完全多部圖的單色樹劃分的多項式時間算法。第二章中我們給出了2-邊染色的完全二部圖的單色樹劃分更精細的刻畫,我們將2-邊染色完全二部圖分為幾種結(jié)構(gòu),并給出每種結(jié)構(gòu)的單色樹劃分數(shù)。我們得到如下結(jié)果。
1.如果K(A,B)是一個2-邊染色完全二部圖,
7、則它是下面四種結(jié)構(gòu)中的一種:(1)K(A,B)有單色支撐樹,(2)K(A,B})∈M,(3)K(A,B)∈S2,(4)K(A,B)∈S1。
2.如果K(A,B)∈M,則K(A,B)的頂點集可被兩個同色的單色樹覆蓋;如果K(A,B)∈S2,則K(A,B)的頂點集要么被一個孤立點和一個單色樹覆蓋,要么被兩個不同色的頂點不交的單色樹覆蓋;如果K(A,B)∈S1,并且m=|A|>|B|=n,則K(A,B)的頂點集可被至多[m-2/
8、2n]+2個頂點不交的單色樹覆蓋,并且存在邊染色使K(A,B)的頂點集恰被[m-2/2n]+2個頂點不交的單色樹覆蓋。
第三章中我們研究了3-邊染色等部完全二部圖的單色樹劃分。我們給出了幾種色度條件下的單色樹劃分數(shù)。設(shè)K(A,B)是一個3-邊染色等部完全二部圖,我們得到如下結(jié)果。
1.如果存在色度為1的頂點,則t3(K(A,B))=3。
2.如果每個頂點的色度都是2,則t3(K(A,B))=2。
溫馨提示
- 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)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 樹T在完全二部圖Bn+3中的4-填充.pdf
- 完全二部圖K4,4的弧傳遞Zp-正則覆蓋.pdf
- 完全二部圖K4,4的弧傳遞Zp-正則覆蓋的刻畫.pdf
- 完全二部圖的K-,1,k--因子分解.pdf
- 完全二部圖K-,n,n-的循環(huán)圈分解.pdf
- 完全二部圖K4,n所有符號圖的準虧格上界.pdf
- 若干完全二部圖的點可區(qū)別IE-全染色.pdf
- 用8長圈C-,8-最大填充和最小覆蓋完全二部圖K-,m,n-.pdf
- 完全二部圖K-,m,n-的k-good邊著色.pdf
- 圖的單色及雜色子圖劃分的復(fù)雜性.pdf
- 單色版畫
- 近似二部圖的邊覆蓋染色.pdf
- 引流單色版
- 單色配色方案
- 邊染色圖中的單色子圖研究.pdf
- 以完全正則二部圖為星補的圖.pdf
- 廣義完全多部圖的生成樹個數(shù)
- 廣義完全多部圖的生成樹個數(shù).pdf
- 邊著色圖中的異色和單色匹配.pdf
- 課程設(shè)計---完全二叉樹的判斷
評論
0/150
提交評論