圖的k-全染色問題與Gr?bner基求解

(1.海南大學(xué)理學(xué)院數(shù)學(xué)系,?？?570228；2.廣東財經(jīng)大學(xué)統(tǒng)計與數(shù)學(xué)學(xué)院，廣州，510320；3.海南熊大教育咨詢有限公司，?？?，570220)

1 引言

在圖的全染色(Total coloring)問題研究中，熟知的TCC猜想是，最大度為Δ的每個有限圖都是(Δ+2)-全可染的([1],[2],[3]). 目前該猜想的研究已經(jīng)取得了一系列成果(參見[4]-[11] ). 對于任意給定的有限圖G和任一正整數(shù)k,本文證明G的k-全可染問題等價于一個多元多項式方程組在{1,2,…,k}范圍的求解問題. 注意到一個多元多項式方程組在{1,2,…,k}范圍的解(如果存在的話)只有有限多個, 根據(jù)熟知的Gr?bner基算法理論, 我們就可通過計算出一個特殊的Gr?bner基給出一個圖k-全可染的有效判別與求解途徑, 進而求得圖的全染色數(shù)χ″(G).由于多項式的Gr?bner基的計算技術(shù)如今已經(jīng)非常成熟，使用諸如Maple, Macaulay, CoCoA等其中任何一個計算代數(shù)程序都可計算出由給定多項式組確定的理想的Gr?bner基，況且目前更有像F4, F5這些最新發(fā)展的快速計算Gr?bner基的算法面世. 因此，本文得到的方法可直接有效地應(yīng)用于任何一個有限圖，從而為TCC猜想的研究提供有效的幫助.

本文中考慮的圖為任意有限圖.

2 圖的k-全染色與多元多項式方程組的解

本節(jié)中圖的全染色的基本概念參見[4]. 有關(guān)一般圖論的基本理論見[1],[2].

給定圖G=(V,E), 其中V={v1,…,vn}是G的頂點集,E={e1,…,em}是G的邊集.

定義1若能用k種顏色給集合V∪E中的元素進行染色，使得其中任意一對相鄰或相關(guān)聯(lián)的元素接受不同的顏色， 則稱這個圖是k-全可染的.

定義2若圖G是k-全可染的，且不存在k′(k′

對于圖G, 我們對其頂點和邊k-染色的不同方案引入向量(X,Y)k=(x1,x2,…,xn,y1,y2,…,ym)T,其中

按照k-全染色的定義我們知道每個頂點、每條邊的染色方案有k種， 也即對于圖G中的任何一個頂點、任一條邊，按照向量分量的定義，xi，yj的取值為{1,2,…,k}中的一個， 也即xi，yj的取值是分別是方程

(xi-1)(xi-2)…(xi-k)=0,i=1,2,…,n，

(2.1)

(yj-1)(yj-2)…(yj-k)=0,j=1,2,…,m

(2.2)

的根.因為相鄰的頂點不能染相同的顏色， 故對任意一對相鄰頂點vi與vs，它們的染色分別為xi和xs，滿足|xi-xs|≥1. 這就表明|xi-xs|的取值為{1,2,…,k-1}中的一個, 也即xi，xs的取值是方程

(|xi-xs|-1)(|xi-xs|-2)…(|xi-xs|-(k-1))=0

的根. 直接驗證可知上面的方程等價于多項式方程

((xi-xs)2-12)((xi-xs)2-22)…((xi-xs)2-(k-1)2)=0.

(2.3)

又因為相鄰的邊也不能染相同的顏色， 故對任意一對相鄰邊ej與et, 它們的染色分別為yj和yt， 滿足|yj-yt|≥1. 這就表明|yj-yt|的取值為{1,2,…,k-1}中的一個, 也即yj，yt的取值是方程

(|yj-yt|-1)(|yj-yt|-2)…(|yj-yt|-(k-1))=0

的根. 直接驗證可知上面的方程等價于多項式方程

((yj-yt)2-12)((yj-yt)2-22)…((yj-yt)2-(k-1)2)=0.

(2.4)

對相關(guān)聯(lián)的元素不能染相同的顏色，故對任意一對相關(guān)聯(lián)的頂點vi與邊ej，對應(yīng)的染色為xi和yj， 滿足|xi-yj|≥1. 這就表明|xi-yj|的取值為{1,2,…,k-1}中的一個, 也即xi，yj的取值是方程

(|xi-yj|-1)(|xi-yj|-2)…(|xi-yj|-(k-1))=0

的根. 直接驗證可知上面的方程等價于多項式方程

((xi-yj)2-12)((xi-yj)2-22)…((xi-yj)2-(k-1)2)=0.

(2.5)

綜合式(2.1)-(2.5)，我們得到關(guān)于x1,x2,…,xn,y1,y2,…,ym的多元多項式方程組

下面的定理給出方程組(Sk)的解與圖G的k-全染色方案的對應(yīng)關(guān)系.

定理1方程組(Sk)每個解對應(yīng)圖G的一個k-全染色；反之亦然，且該對應(yīng)是一一對應(yīng).

證明“?” 取方程組(Sk)的任意一個解，記作(X,Y)0=(x1,x2,…,xn,y1,y2,…,ym)T. (X,Y)0是方程組的解， 也就是方程(2.1)-(2.5)的根， 故由k-全染色的定義知道該解對應(yīng)一個k-全染色方案，即對x1,x2,…,xn,y1,y2,…,ym的取值進行分類， 取值相同的歸于一類，染一種顏色. 因為有k種不同的取值， 也就能得到k類，染k種不同的顏色. 按此分類染色就可得到一個k-全染色方案.

“?” 取圖G的一個k-全染色方案， 記{1,2,…,k}為該k種染色對應(yīng)的取值. 因為k-全染色中相鄰元素和相關(guān)聯(lián)元素不能染相同的顏色， 故該染色方案對應(yīng)的染色向量(X,Y)1=(x1,x2,…,xn,y1,y2,…,ym)T是分別滿足方程(2.1)-(2.5)的， 也即滿足方程組(Sk)，從而染色向量(X,Y)1是方程組(Sk)的一個解.

容易看出以上給出的對應(yīng)是既單且滿的.

3 圖的k-全染色存在性的Gr?bner基判別

給定具有n個頂點、m條邊的圖G=(V,E),G顯然有極小全染色. 但是對于任意一個1≤k≤|V|+|E|=n+m,一個自然的問題是:G是否有含k種顏色的全染色方案?上節(jié)中我們證明了圖G的k-全染色方案的存在問題完全等價于一個多元多項式方程組在{0,1,2,…,k}范圍的求解問題, 且由定理 1 可知存在圖G的k-全染色方案的集合與多元多項式方程組(Sk)的解的集合之間的一個一一對應(yīng). 本節(jié)中我們用經(jīng)典的判別多項式方程組解的存在性的Gr?bner基方法(參見[3])來給出G是否為k-全可染的一個有效判別.

定理2對于給定的k, 其中1≤k≤|V|+|E|=n+m, 考察下面由復(fù)數(shù)域C上多項式確定的方程組:

(1)圖G是k-全可染得當(dāng)且僅當(dāng)方程組 (Sk) 有解.

(2)若方程組 (Sk) 有解, 則 (Sk) 的所有解給出G的所有k-全染色方案.

(3)令I(lǐng)是方程組 (Sk) 中方程左端多項式在多元多項式環(huán)R=C[x1,…,xn]中生成的理想. 則方程組(Sk)有解當(dāng)且僅當(dāng)理想I的Gr?bner基不含非零常數(shù).

證明(1)由定理 1 知圖G=(V,E)有k-全染色方案當(dāng)且僅當(dāng)方程組(Sk)有解.

(2)由定理1與上面(1), 該結(jié)論是顯然的.

(3)由于方程組(Sk)解的存在性與理想I的Gr?bner基給出的方程組的解的存在性是等價的，而C是代數(shù)閉域, 因此該結(jié)論由著名的Hilbert零點定理與熟知的Gr?bner基的性質(zhì)([3])即可得到.

4 求圖的k-全染色方案, 全可染色數(shù)及極小全可染方案的Gr?bner基方法

本節(jié)根據(jù)第三節(jié)定理 2 給出求圖的k-全染色、極小全可染方案及全可染色數(shù)χ″(G)的Gr?bner基方法.

4.1 求圖的k-全染色方案的計算方法

根據(jù)前面的討論, 在方程組(Sk)有解的情況下, 只要解方程組(Sk)即可得到圖G的所有k-全可染方案. 求解多元多項式的方法雖然很多, 但是注意到方程組(Sk)如果有解, 則它的坐標(biāo)的取值范圍是{1,2,…,k}且解的個數(shù)一定是有限的. 這樣, 由[3]可知, 在某個消元單項式序下, 例如在單項式序

x1?x2?…?xn-1?xn?y1?y2?…?ym-1?ym

下理想I的一個約化Gr?bner基給出與方程組(Sk)等價的方程組為:

4.2 求圖的全可染色數(shù)及極小全可染方案的計算方法

一個圖的k-全可染色方案(如果存在的話)不一定是唯一的. 但由于每個有限圖中頂點個數(shù)和邊數(shù)之和是有限的, 故k-全可染的染色數(shù)k有最小值, 而該最小值就是該圖的全可染色數(shù)χ″(G). 以下我們根據(jù)定理2給出求圖G的全可染色數(shù)χ″(G)的一種方法.

定理3k是圖G的全可染色數(shù)χ″(G)當(dāng)且僅當(dāng)方程組(Sk)有解而方程組(Sk-1)無解.

證明“?” 若k是圖G的全可染色數(shù)χ″(G), 則說明圖G全染色方案中包含k種顏色的染色方案, 由定理2(1)的結(jié)論我們得知方程組(Sk)有解; 而由全可染色數(shù)的定義, 圖G中全染色方案中包含的染色顏色數(shù)最少為k, 故圖G中不存在顏色數(shù)為k-1的全染色, 所以方程組(Sk-1)無解.

“?” 若方程組(Sk)有解而方程組(Sk-1)無解, 由定理 2(1)的結(jié)論知，圖G是k-全可染的，但不是(k-1)-全可染的, 也就說明圖G中全可染方案所包含的顏色數(shù)最小只能為k, 因此根據(jù)全可染色數(shù)的定義k是圖G的全可染色數(shù)χ″(G).

由定理3可以得到一個全可染色數(shù)χ″(G)的一個解決方案, 即我們可以通過采用由小到大的次序計算圖的全可染色數(shù)χ″(G), 進而得到圖G的極小全可染色方案.

5 一個計算實例

最后，我們給出一個實際例子來說明上節(jié)給出的方法的有效性. 考察有限圖G=(V,E), 其中頂點集V={v1,v2,v3,v4}, 邊集E={e1,e2,e3,e4,e5}.

圖1

以下我們應(yīng)用前面得到的計算方法來分別計算圖G的k-全可染、極小全可染色數(shù)以及極小全可染方案.

對k采用從大到小的次序來計算k-全可染(k>1):

2-全可染情形:

通過MAPLE計算Gr?bner基的程序計算得到理想IS2的一個約化Gr?bner基:G2={1},包含非零常數(shù), 所以由定理2(3)的結(jié)論知方程組(S2)是無解的, 故該圖不存在2-全染色.

3-全可染情形:

通過MAPLE計算Gr?bner基的程序計算得到理想IS3的一個約化Gr?bner基:G2={1}, 包含非零常數(shù), 所以由定理2(3)的結(jié)論知方程組(S3)是無解的, 故該圖也不存在3-全染色.

4-全可染情形:

通過MAPLE計算Gr?bner基的程序計算得到理想IS4的一個約化Gr?bner基:

方程組(S4)有解而方程組(S3)無解, 由定理3的結(jié)論知圖G的全染色數(shù)χ″(G)為4. 所有的4-全染色就是該圖的極小全染色方案.

作者衷心感謝李會師教授的指導(dǎo)和幫助.