圖的k-星著色的Gr?bner基求解

尹杰杰

(海南大學(xué)信息科學(xué)技術(shù)學(xué)院，海南?？?70228)

在應(yīng)用數(shù)學(xué)領(lǐng)域中，多項(xiàng)式理想的Gr?bner基方法不僅可以用來判別多項(xiàng)式方程組解的存在性，還可以在解存在的情況下判別解的個(gè)數(shù)的有限性，Gr?bner基方法已經(jīng)被廣泛用于圖論中各種問題的多項(xiàng)式方程組模型的求解，參考文獻(xiàn)［1-4］.對(duì)于具有n個(gè)頂點(diǎn)的簡(jiǎn)單連通圖G，筆者證明了求解G的k-星著色等價(jià)于求解一個(gè)多元多項(xiàng)式方程組的所有 {1，2，…，k}解，并使用Gr?bner基給出求解方法，從而得到求G的極小星著色和星色數(shù)的一個(gè)可行途徑，最后通過實(shí)例驗(yàn)證了此代數(shù)計(jì)算方法的有效性.

注意到k-星著色是有限的，由多項(xiàng)式方程組模型得到的Gr?bner基構(gòu)成的方程組是較容易求解的三角形方程組，G的極小星著色和星色數(shù)在求解有限個(gè)方程后即可得到.如今多項(xiàng)式理想的Gr?bner基的計(jì)算技術(shù)已經(jīng)非常成熟，如MAPLE，Macaulay，CoCoA等任意計(jì)算代數(shù)程序都可計(jì)算出給定多項(xiàng)式方程組，確定其理想的Gr?bner基.因此，本文代數(shù)計(jì)算方法可直接應(yīng)用于任何一個(gè)有限圖，不涉及已有計(jì)算Gr?bner基的算法的復(fù)雜性，也不討論其與已有只求極小星著色的優(yōu)化算法的比較.

1 預(yù)備知識(shí)

主要介紹本文所需的圖論知識(shí)，參考文獻(xiàn)［5-7］.

給定圖 G=(V，E)，其中 G 的頂點(diǎn)集 V={v1，…，vn}，邊集 E={eij=vivj|vi，vjV，i≠j}.

定義1 若相鄰的2頂點(diǎn)所著的顏色不同，則稱該著色是正常的頂點(diǎn)著色.若相鄰的2條邊所著的顏色不同，則稱該著色是正常的邊著色.

定義2 圖G的星著色是指圖G的正常的點(diǎn)著色并且使得G中任意長(zhǎng)為3的路上的點(diǎn)不著相同的顏色.圖G的星色數(shù)是G的星著色所用顏色個(gè)數(shù)的最小值，記作χs(G).

定義3 k≥4時(shí)k-星著色就是該星著色所用顏色種數(shù)為k.

定義4 T是圖G的星著色，若不存在任何其它星著色T'，使得 |T'|＜|T|，則稱T是圖G的極小星著色.

定義5 設(shè)圖G=(V，E)是簡(jiǎn)單連通圖.則圖G的鄰接矩陣定義為A=［aij］n×n，其中

2 k-星著色的多元多項(xiàng)式刻畫

將k-星著色的存在性和求解問題轉(zhuǎn)化為多元多項(xiàng)式方程組解的存在性與求解問題，并使用Gr?bner基給出圖是否含有k-星著色的有效判別方法.

對(duì)于圖 G，對(duì)其 k-星著色引入向量 X=(x1，x2，…，xn)，其中

顯然xi取值在{1，2，…，k}中，即xi的取值是方程(xi-1)(xi-2)…(xi-k)=0的解.討論點(diǎn)viV，任意與vi相鄰的點(diǎn)vj(eijE)，因?yàn)樾侵珴M足任何一條長(zhǎng)為3的路上的點(diǎn)不著相同的顏色:

1)點(diǎn)vi與點(diǎn)vj染不同的顏色，即1≤|xi-xj|≤k-1?(|xi-xj|-1)(|xi-xj|-2)…(|xi-xj|-(k-1))=0，所以有((xi-xj)2-1)((xi-xj)2-22)((xi-xj)2-(k-1)2)=0.

2)任意與 vi相鄰的點(diǎn) va(eiaE)，其中 a≠j，有1≤|xa-xj|≤k-1?(|xa-xj|-1)(|xa-xj|-2)…(|xa-xj|-(k-1))=0，即((xa-xj)2-1)((xa-xj)2-22)…((xa-xj)2-(k-1)2)=0.

3)任意與 vi相鄰的點(diǎn)va，任意與 vj相鄰的點(diǎn) vb(eibE)，其中 a≠j，b≠i，有1≤|xa-xb|≤k-1?(|xa-xb|-1)(|xa-xb|-2)…(|xa-xb|-(k-1))=0，即((xa-xb)2-1)((xa-xb)2-22)…((xa-xb)2-(k-1)2)=0.

綜上可知，?eijE得到多元多項(xiàng)式方程組

給出方程組(Sk)的解與圖G的k-星著色方案的對(duì)應(yīng)關(guān)系:

定理1 方程組(Sk)的解對(duì)應(yīng)圖G的一個(gè)k-星著色，反之亦然，且該對(duì)應(yīng)是一一對(duì)應(yīng).

證明 充分條件 令(Sk)的任意一個(gè)解x0=(x1，x2，…，xn).故由k-星著色的定義可知該解對(duì)應(yīng)一個(gè)k-星著色方案，即對(duì)xi，其中i{1，2，…，n}的取值進(jìn)行分類，取值相同的歸于一類，染同一種顏色.由于有k種不同的取值，也就能得到k類，染k種不同的顏色.按此分類著色就可得到一個(gè)k-星著色方案.

必要條件 取圖G的一個(gè)k-星著色方案，記{1，2，…，k}為該k種著色對(duì)應(yīng)的取值.按照k-星著色中相鄰頂點(diǎn)不能染相同顏色，且G中任意長(zhǎng)為3的路上的點(diǎn)不著相同的顏色.故該著色方案對(duì)應(yīng)的著色向量x1=(x1，x2，…，xn)是滿足方程組(Sk)的，所以可知著色向量x1是方程組(Sk)的一個(gè)解.

顯然可知給出的對(duì)應(yīng)是一一對(duì)應(yīng)的.

用Gr?bner基方法來給出k-星著色存在性的一個(gè)有效判別.

定理2 對(duì)于給定的k，其中1≤k≤n，考察復(fù)數(shù)域C上多項(xiàng)式確定的方程組

1)G是k-星著色?方程組(Sk)有解.

2)若方程組(Sk)有解，則(Sk)的所有解給出G的所有k-星著色的方案.

3)令I(lǐng)是方程組(Sk)中方程左端多項(xiàng)式生成的理想.則方程組(Sk)有解?理想I的Gr?bner基不含非零常數(shù).

證明 1)由定理1，可知1)成立.

2)若方程組(Sk)有解，則對(duì)于(Sk)的一個(gè)解，可知此解對(duì)應(yīng)一個(gè)星著色方案，所以(Sk)的所有解對(duì)應(yīng)k-星著色的所有方案.反之對(duì)于圖G的一個(gè)k-星著色，則其對(duì)應(yīng)的向量x=(x1，x2，…，xn)滿足(Sk)的解，故由定理1的結(jié)論可知方程組(Sk)成立.因此由該k-星著色對(duì)應(yīng)的向量就是方程組(Sk)的一個(gè)解，即方程組(Sk)的解和圖G的k-星著色是一一對(duì)應(yīng)的，方程組(Sk)的所有解給出G的所有k-星著色.

3)由于方程組(Sk)的解的存在性與理想I的Gr?bner基［1］給出的方程組的解的存在性是等價(jià)的.若方程組(Sk)有解，則V(I)≠?，即G≠{1}，理想I的Gr?bner基不含非零常數(shù);若理想I的Gr?bner基不含非零常數(shù)，就有V(I)≠?，方程組(Sk)有解，得證.

3 求圖的k-星著色的Gr?bner基方法

在方程組(Sk)有解的情況下，只要解方程組(Sk)即可得到圖G的所有k-星著色.求解多元多項(xiàng)式的方法雖然很多，但是注意到方程組(Sk)如果有解，則其解都在集合{1，…，k}內(nèi)，且解的個(gè)數(shù)是有限的.由文獻(xiàn)［1］可知在某個(gè)消元單項(xiàng)式序下，例如在單項(xiàng)式序xm＞xm-1＞…＞x1下理想I的一個(gè)約化Gr?bner基給出與方程組(Sk)等價(jià)的方程組形式為因此，在某個(gè)消元單項(xiàng)式序下計(jì)算出理想I的一個(gè)約化Gr?bner基后，就可采用回代的方法計(jì)算出圖G的所有k-星著色.在實(shí)際應(yīng)用定理2和此結(jié)論時(shí)，只需先調(diào)用MAPLE計(jì)算Gr?bner基的程序，便可判斷一個(gè)圖G是否有k-星著色，若有，再調(diào)用求解方程組的程序?qū)Ψ匠探M進(jìn)行求解即可得到G的所有k-星著色.

4 求圖的星色數(shù)的計(jì)算方法

一個(gè)圖的k-星著色(若存在)不一定是唯一的，但由于每個(gè)有限圖中星著色的頂點(diǎn)數(shù)是有限的，著色的顏色種數(shù)也是有限的，故k-星著色中著色數(shù)k有最小值，而該最小值就是該圖G的星色數(shù).根據(jù)定理2給出求圖G的星色數(shù)的一種方法.

定理3 k是圖G的星色數(shù)?方程組(Sk)有解而方程組(Sk-1)無解.

證明 充分條件 若k是圖G的星色數(shù)，則說明圖G的極小星著色所用的顏色為k，由定理2知方程組(Sk)有解.由星色數(shù)的定義，圖G中星著色所用的顏色最少為k，故圖G中不存在邊著色數(shù)為k-1的星著色，所以方程組(Sk-1)無解.

必要條件 若方程組(Sk)有解而方程組(Sk-1)無解，由定理2的結(jié)論知圖G存在k-星著色但不存在(k-1)-星著色，說明圖G中星著色所用的顏色最少只能為k，所以根據(jù)星著色的定義k是圖G的星色數(shù).

圖1 有限圖G

5 舉例

考察有限圖 G=(V，E)，其中頂點(diǎn)集 V={v1，v2，v3，v4，v5，v6，v7，v8}，邊集 E={e1=v1v2，e2=v2v3，e3=v3v4，e4=v4v5，e5=v5v6，e6=v6v7，e7=v7v8，e8=v8v1，e9=v1v3}，求圖G的星色數(shù).

現(xiàn)在討論頂點(diǎn) v6，v6e56，可以得到方程組 (S'6)

同理，由其他點(diǎn)都可以得到此類型的方程組，總共有8個(gè)方程組.然后把此8個(gè)方程組合并成一個(gè)方程組即為(Sk).

由定義可知 k=1，2，3時(shí)，顯然不成立，現(xiàn)在從 k=4開始討論.

當(dāng)k=4時(shí)通過MAPLE計(jì)算(S4)的一個(gè)約化Gr?bner基G4={1}，則可知包含非零常數(shù)，得到方程組(S4)是無解的，所以不存在4-星著色.

當(dāng)k=5時(shí)通過MAPLE計(jì)算(S5)的一個(gè)約化Gr?bner基G5={1}，則可知包含非零常數(shù)，得到方程組(S5)是無解的，所以不存在5-星著色.

當(dāng)k=6時(shí)通過MAPLE計(jì)算(S6)的一個(gè)約化Gr?bner基G6={1}，則可知包含非零常數(shù)，得到方程組(S6)是無解的，所以不存在6-星著色.

當(dāng)k=7時(shí)通過MAPLE計(jì)算(S7)的一個(gè)約化Gr?bner基，然后用MAPLE計(jì)算(S7)所得的方程組得到以下解(列出部分解)(1，2，3，4，5，2，6，7)，(1，2，3，4，7，2，6，5)，(2，1，3，4，7，1，6，5)，(3，1，2，4，7，1，6，5)，(4，1，3，2，7，1，6，5)，(5，1，3，4，7，1，6，2)，(2，3，4，1，7，3，6，5)，(2，3，4，1，5，3，6，7)，(5，2，3，4，7，2，6，1)，(2，3，4，1，7，3，6，5)，(2，3，7，1，4，3，6，5)，(2，3，4，6，7，3，1，5).

綜上可知，方程組(S6)不成立，方程組(S7)成立，所以該圖的星色數(shù)為7，故所有的7-星著色都是極小星著色.

［1］ADAMS W ，LOUSTAUNAUS P.An introduction to Gr?bner bases［M］.Washington，D C:American Mathematical Society，1994.

［2］MOLLOY M ，REED B.A bound on the strong chromatic index of a graph［J］.J.Combinatorial Theory Ser.B，1997，69:103-109.

［3］熊雪瑋，趙志琴.圖的k-獨(dú)立集與Gr?bner基求解［J］.工程數(shù)學(xué)學(xué)報(bào).2012，29(5):696-702.

［4］熊雪瑋.幾個(gè)圖論問題的多項(xiàng)式建模與Gr?bner基求解［D］.海口:海南大學(xué)，2012.

［5］BONDY J A，MURTY U S R.Graph Theory［M］.Berlin:Springer，2008.

［6］TIMMONS C.Star coloring high girth planar graphs［J］.Electron J Combin，2008，15:124.

［7］KIERSTEAD H A KüNDGEN A，TIMMONS C.Star coloring bipartite planar graphs［J］.J Graph Theory，2009，60:1-10.