條件染色的算法與復(fù)雜性.pdf

1、圖的染色理論在離散數(shù)學的研究領(lǐng)域中處于中心地位。它還經(jīng)常出現(xiàn)在看上去沒有或者僅有一點聯(lián)系的研究領(lǐng)域中。圖的染色理論非常有用。時間表的編制,排序問題,調(diào)度問題,以及由它們演化而來的其他問題等等,都可以用染色理論來處理。圖G=(V(G),E(G))。對一個正整數(shù)k,圖G的一個正常k染色是指一個滿射c:V(G)→{1,2…,k),滿足如下條件:如果點u和點v在G中相鄰的話,那么c(u)≠c(u),即u和v要染不同的顏色。按照上述方法染色,所需

2、要用到的最少顏色數(shù)被我們稱為圖的色數(shù),記為X(G)。對圖G的一個頂點子集S,我們用c(S)來表示在c這種染色方式下S中所用的不同顏色的集合。到目前為止,圖的染色有很多推廣,包括圖的邊染色,列表染色,地圖染色和全染色等等。我們這里研究的是圖的條件染色。對于給定的正整數(shù)k和r,圖G的一個正常的(k,r)-條件染色是指滿足如下兩個條件的滿射c:V(G)→{1,2,…,k}:(C1)如果u和v在圖中相鄰,那么它們必須染不同的顏色；(C2)圖的任

3、一頂點v的鄰域所染的不同顏色數(shù)必須大于等于min{d(v),r}。對于給定正整數(shù)r,使得圖G具有一個正常(k,r)-條件染色所需的最少的顏色數(shù)稱為圖G的第r階條件色數(shù),記為Xr(G)。由Xr(G)的定義可知X(G)=X1(G),因此條件染色是傳統(tǒng)染色的一個自然推廣。但是條件染色又跟傳統(tǒng)染色有很多的不同。在2006年的一篇文章中,賴虹建等人給出了許多條件染色的性質(zhì)和定理說明了它在圖論性質(zhì)方面的很多不同。在本文中,我們將主要討論條件染色問題

4、在算法方面的表現(xiàn)。
　　 本研究分為總價格部分：第一部分討論了一般圖的條件染色的算法表現(xiàn),第二部分集中考察了在無爪圖中的(3,2)-條件染色的性質(zhì)和算法。第三部分給出了一些其他的關(guān)于條件色數(shù)的結(jié)果。第一部分包括第二章和第三章。在第二章中,我們首先考察了一般圖的條件染色的算法復(fù)雜性問題。我們主要證明了判定對于給定任意大的圍長,最大度不超過3的平面二部圖是否可以(3,2)-條件染色這個問題是NP-完備的。這個結(jié)果跟傳統(tǒng)的染色有很大的

5、不同。在傳統(tǒng)的染色中,對于最大度不超過3的圖的染色問題有多項式時間算法來解決。我們也證明了在傳統(tǒng)染色中的一些著名ⅣP-完備問題在條件染色中也是同樣成立的。在第三章中,我們將會說明(3,2)-條件染色問題對于給定樹寬的圖是有多項式時間算法的。我們也會對最大度大于等于4的一般圖給出一個(△+1,2)-條件染色的多項式時間算法。第二部分是第四章。在這一章中,我們將集中討論無爪圖的第2階條件3染色問題。首先,我們證明了判斷一個最大度為3的無爪圖