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

(1.海南大學理學院數學系,海口,570228；2.廣東財經大學統計與數學學院，廣州，510320；3.海南熊大教育咨詢有限公司，海口，570220)

1 引言

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

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

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

本節中圖的全染色的基本概念參見[4]. 有關一般圖論的基本理論見[1],[2].

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

定義1若能用k種顏色給集合V∪E中的元素進行染色，使得其中任意一對相鄰或相關聯的元素接受不同的顏色， 則稱這個圖是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)

對相關聯的元素不能染相同的顏色，故對任意一對相關聯的頂點vi與邊ej，對應的染色為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)，我們得到關于x1,x2,…,xn,y1,y2,…,ym的多元多項式方程組

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

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

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

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

容易看出以上給出的對應是既單且滿的.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 一個計算實例

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

圖1

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

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

2-全可染情形:

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

3-全可染情形:

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

4-全可染情形:

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

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

作者衷心感謝李會師教授的指導和幫助.