基于Gr?bner基的圖動態(tài)染色求解方案

何文峰，張勇軍，符一平

( 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 海口 570228)

?

基于Gr?bner基的圖動態(tài)染色求解方案

何文峰，張勇軍，符一平

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

摘要：考察了一般有限連通圖的動態(tài)染色方案以及動態(tài)色數(shù)，首先利用多元多項(xiàng)式方程組對其進(jìn)行建模，然后利用方程組對應(yīng)的Gr?bner基來判定方程組解存在性，進(jìn)而達(dá)到判定圖的動態(tài)染色方案的存在性的目的，最后給出求動態(tài)色數(shù)及相應(yīng)動態(tài)染色方案的方法，并給予實(shí)例驗(yàn)證.

關(guān)鍵詞：動態(tài)染色； 動態(tài)色數(shù)； Gr?bner基

圖染色問題就是用最少種類的顏色對圖的點(diǎn)、邊、面以某種規(guī)則進(jìn)行染色，研究染色所用色數(shù)以及設(shè)計(jì)對應(yīng)的染色方案就成為圖染色的基本工作.近年來，隨著通信以及計(jì)算機(jī)技術(shù)方面的長足發(fā)展，對染色問題提出了更高的要求.在此背景之下，2001年Montgomery在文獻(xiàn)[1]中提出動態(tài)染色概念，同時證明了一般圖的動態(tài)色數(shù)上界為Δ+3.林越等在文獻(xiàn)[2]中得到平面圖的動態(tài)色數(shù)上界為5的結(jié)論，除此之外，還有一些學(xué)者對特殊圖的動態(tài)色數(shù)給予了研究，如文獻(xiàn)[1],[3-9]分別對多重完全圖、二部完全圖、完全圖、樹、k-正則圖、偽哈林圖、單圈圖及雙圈圖等特殊圖的動態(tài)色數(shù)進(jìn)行了研究.

從以上研究的過程中可以發(fā)現(xiàn)，幾類特殊圖和平面圖的動態(tài)染色的上界已經(jīng)研究的較清楚,但一般圖的動態(tài)色數(shù)還知之甚少.因此，筆者考察了一般有限連通圖的動態(tài)染色方案以及動態(tài)色數(shù)，首先對其進(jìn)行多元多項(xiàng)式方程組建模，然后利用方程組對應(yīng)的Gr?bner基來判定方程組解的存在性，進(jìn)而達(dá)到判定圖的動態(tài)染色方案的存在性的目的，最后給出求動態(tài)色數(shù)的可行方法.

1預(yù)備知識

本文提到的圖G(V，E)均指n階連通圖，V(G)表示G(V,E)的頂點(diǎn)集，E(G)表示G(V,E)的邊集，

N(v)表示G(V,E)中頂點(diǎn)v的鄰點(diǎn)集，dG(v)=d(v)=|N(v)|表示G(V,E)的頂點(diǎn)v的度.

定義1 圖G(V,E)的動態(tài)d-染色是一個這樣的映射C:V(G)→C(d)={1,2,…，d},且滿足：

定義2若圖G(V,E)存在動態(tài)d-染色，而不存在動態(tài)(d-1)-染色，那么就把d稱為圖G(E,V)的動態(tài)色數(shù)，記為χd(G).

定義3 設(shè)圖G(V,E)是一個有限的簡單連通圖，鄰接矩陣(AdjacencyMatrix)記為A=(aij)n×n，其中，

2描述動態(tài)k-染色的多元多項(xiàng)式方程組的建立

圖G(V,E)動態(tài)d-染色就是用顏色集{1,2,…,d}對G(V,E)進(jìn)行正常頂點(diǎn)染色(即相鄰頂點(diǎn)染不同色)，同時，若某頂點(diǎn)有2個以上鄰點(diǎn)，要使得至少有2個鄰點(diǎn)染不同色.如果要把圖G(V,E)動態(tài)d-染色用多元多項(xiàng)式方程組描述出來，即根據(jù)圖G(V,E)的動態(tài)d-染色的定義建立多元多項(xiàng)式方程組模型.現(xiàn)取頂點(diǎn)染色方案向量X=(x1,x2,…，xn)T，其中，

若頂點(diǎn)vi用顏色集{1,2,…，d}中的顏色染色，那么vi的顏色xi為多項(xiàng)式方程

(xi-1)(xi-2)…(xi-d)=0

的解.

(|xi-xj|-1)(|xi-xj|-2)…(|xi-xj|-(d-1))=0

的解，而方程

(|xi-xj|-1)(|xi-xj|-2)…(|xi-xj|-(d-1))=0

等價(jià)于

((xi-xj)2-1)((xi-xj)2-22)…((xi-xj)2-(d-1)2)=0.

對于圖G(V,E)任一頂點(diǎn)vi，其度(即鄰邊數(shù)目)dG(vi)=AiAiT， 通過鄰接矩陣A 就可以確定. 若dG(vi)=AiAiT=1，正常頂點(diǎn)染色方案一定符合|C(N(vi))|≥min{2,dG(vi)}；若dG(vi)=AiAiT≥2,由鄰接矩陣A一定可以找到vi的鄰點(diǎn)集N(vi)={vi1,vi2,…,vidG(vi)}，若要求N(vi)={vi1,vi2,…,vidG(vi)}至少染2種顏色(即要求|C(N(vi))|≥min{2,dG(vi)}),那么頂點(diǎn)vi1,vi2,…,vidG(vi)對應(yīng)的顏色xi1,xi2,…,xidG(vi)就是方程

的解.

由以上過程，可以看到G(V,E)的動態(tài)染d-色方案與方程組

的解有關(guān).用定理1給定關(guān)系.

定理1 方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案，且是一一對應(yīng).

證明充分性方程組Sd的解X會使第一組方程和第二組方程都成立，那么X就會使得每個頂點(diǎn)都在顏色集{1,2,…，d}中選一種顏色，且相鄰的點(diǎn)顏色不同；方程組Sd的解X會使第三組方程成立，那么X就會使得任何有2個鄰點(diǎn)以上的頂點(diǎn)有至少2個鄰點(diǎn)染色不同.因此，方程組得解X就是圖G(V,E)的一個動態(tài)d-染色方案.

必要性若X是圖G(V,E)的一個動態(tài)d-染色方案，X就是圖G(V,E)的一個頂點(diǎn)正常染色方案，必然符合第一組方程和第二組方程，即代入必使其成立.X要使得任何有2個鄰點(diǎn)以上的頂點(diǎn)有至少2個鄰點(diǎn)染色不同，那么代入第三組方程，第三組方程也成立.由此，X代入方程組Sd會使得其成立，即X是方程組Sd的一個解.

綜上所述，方程組Sd的每個解對應(yīng)圖G(V，E)的一個動態(tài)d-染色方案.且是一一對應(yīng).

3圖G(V,E)的動態(tài)d-染色方案存在性的Gr?bner基判別方法

對于圖G(V,E)，動態(tài)d-染色方案是否一定存在？存在的話，是否d種顏色構(gòu)成的任一方案都可以對圖G(V,E)進(jìn)行動態(tài)染色？這些問題的解決可以從定理1中找到線索，方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案，且是一一對應(yīng).因此，要判定圖G(V,E)是否動態(tài)d-染色，是否d種顏色構(gòu)成的任一方案都可以對圖G(V,E)進(jìn)行動態(tài)染色就可以轉(zhuǎn)化為多元多次方程組解的存在性問題及求解問題.對于多元多項(xiàng)式方程組根的存在性可以借助于Gr?bner基來判定.因此，定理2就可以解決所提問題.

定理2對于給定的d(其中0

1)圖G(V，E)是動態(tài)d-染色的?Sd有解；

2)倘若Sd有解，那么Sd的所有解就給出圖G(V,E)的所有的動態(tài)d-染色方案；

3) Sd有解?理想I的Gr?bner基不包括非零的常數(shù)，其中，理想I是Sd各方程左端多元多項(xiàng)式在環(huán)R=C[x1,x2,…,xn]中生成的.

證明 1)和2)由定理1(方程組Sd的每個解對應(yīng)圖G(V,E)的一個動態(tài)d-染色方案，且是一一對應(yīng))可以直接推得成立.

由于Sd解的存在性?I的Gr?bner基生成的多元多項(xiàng)式方程組解的存在性，如果Sd有解，那么V(I)≠?，即理想I的Gr?bner基不包括非零的常數(shù)；若理想I的Gr?bner基不包括非零的常數(shù)，那么I的Gr?bner基生成的多元多項(xiàng)式方程組解就存在，即方程組Sd有解.3)成立.

4動態(tài)色數(shù)χd(G)的確定

定理3Sd-1無解而Sd有解?χd(G)=d.

證明充分性根據(jù)定理2 1)的逆否命題可知，如果Sd-1無解，那么圖G(V，E)就不存在動態(tài)(d-1) -染色，根據(jù)定理2 1)可知，如果Sd有解，那么圖G(V,E)就存在動態(tài)d-染色，由動態(tài)色數(shù)的定義可知χd(G)=d.

必要性如果χd(G)=d，根據(jù)動態(tài)色數(shù)的定義就知若要對圖G(V,E)進(jìn)行動態(tài)染色，最少需要d種顏色，即動態(tài)d-染色存在，而動態(tài)(d-1) -染色不存在，結(jié)合定理2 1)和2)就可以得到Sd-1無解而Sd有解.

5實(shí)例驗(yàn)證

根據(jù)定理1、定理2和定理3，在實(shí)例中可以依照方程組S2,S3,S4…逐個利用數(shù)學(xué)軟件Maple計(jì)算所對應(yīng)的理想I的Gr?bner基,通過觀察理想I的Gr?bner基是否包含不為零的常數(shù)的方法來確定所對應(yīng)的染色方案是否存在，若存在，就利用理想I的Gr?bner基生成的多元多項(xiàng)式的方程組取得圖G(V,E)的所有的動態(tài)d-染色方案，同時根據(jù)定理3確定χd(G).

例有限圖G(V,E) (如圖1),其中V={v1,v2,v3,v4,v5,v6}，鄰接矩陣為

根據(jù)定理3，先驗(yàn)證G(V,E)的動態(tài)2-染色的存在性，再驗(yàn)證G(V,E)的動態(tài)3-染色的存在性，依次進(jìn)行下去，直到找到合適的d值,同時得到相應(yīng)的動態(tài)染色方案.

動態(tài)2-染色

利用Maple中計(jì)算Gr?bner基的程序可以計(jì)算出G2={1}是IS2的唯一約化Gr?bner基，由定理2可得S2無解，即圖G(V,E)的動態(tài)2-染色不存在.

動態(tài)染色

利用Maple中計(jì)算Gr?bner基的程序可以計(jì)算出

G3={x63-6x62+11x6-6,x62+x52+x5x6-6x5-6x6+11,x5+x6+x4-6,x5x6-x3x6-x3x5+x32,

x6+x5+x1-1,x3+x2-x6-x5,x5+x1-6}.

由定理2說明S3有解，且與G3對應(yīng)的方程組G3=0的解相同，在軟件Mapple中調(diào)用程序解G3=0，

得到結(jié)果(3,2,1,3,2,1)，(3,1,2,3,1,2)，(3,1,2,3,2,1)，(3,1,2,3,2,1)，(3,3,1,3,1,2)，(2,3,1,2,1,3)，(1,3,2,3,1,2)，(2,1,3,2,3,1)，(1,2,3,1,2,3)，(1,3,2,1,3,2)，(1,2,3,1,3,2)，(2,1,3,2,1,3).

由定理2也說明這些解恰好是動態(tài)3-染色的所有方案，同時，由定理3也可以知道χd(x)=3.

參考文獻(xiàn)：

[1] Montgomery B.Dynamic coloring[D].West Virginia:West Virginia University, 2001.

[2] 林越,趙克文.平面圖的動態(tài)著色[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2010,42(3):34-35.

[3] Alishahi M.On the dynamic coloring of graphs[J].Discrete Applied Mathematics,2011,159(3):152-156.

[4] Esperet L.Dynamic list coloring of bipartite graphs [J].Discrete Applied Mathematics,2010,158(17):1 963-1 965.

[5] 秦健,張巖.單圈圖和雙圈圖的動態(tài)色數(shù)[J].山東大學(xué)學(xué)報(bào)(理學(xué)版),2007,42(10):37-40.

[6] Akbari S,Ghanbari M,Jahanbekam S.On the list dynamic coloring of graphs[J].Discrete Applied Mathematics, 2009,157(14):3 005-3 007.

[7] Meng X Y,Miao L Y,Su B T.The dynamic coloring numbers of Pseudo-Halin graphs [J].Ars Combinatoria, 2006, 79:3-9.

[8] Kim S J,Park W J.List Dynamic coloring of sparse graphs[J].Combinatorial Optimization and Applications,2011,6 831:156-162.

[9] Kim S J,Lee S J,Park W J.Dynamic coloring and list dynamic coloring of planar graphs[J].Discrete Applied Mathematics,2013,161:2 207-2 212.

[10] 王桂平,王衍,任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京：北京大學(xué)出版社,2011.

Dynamic Coloring Solving Scheme Based on Gr?bner Basis

He Wenfeng, Zhang Yongjun, Fu Yiping

(College of Information Science and Technology, Hainan University, Haikou 570228，China)

Abstract：In the report, the dynamic coloring solution of the Limited connected graph and the dynamic coloring number were investigated. Firstly, the multivariate polynomial equation group was used to construct a model of the dynamic coloring problem; Secondly, the corresponding Gr?bner basis of the multivariate polynomial equations was used to determine the existence of solutions, which can judge the existence of the dynamic coloring protocol; Lastly, the dynamic coloring number and the solution method of the corresponding dynamic coloring were proposed, and which was validated by specific examples.

Keywords：dynamic coloring; dynamic coloring number; Gr?bner basis

中圖分類號：O 157.5

文獻(xiàn)標(biāo)志碼：ADOl：10.15886/j.cnki.hdxbzkb.2015.0023

文章編號：1004-1729(2015)02-0125-05

收稿日期：------------------------ 2014-10-10

作者簡介：何文峰(1978-)男，陜西蒲城人，講師.通信作者： 張勇軍(1977-)男，陜西渭南人，講師.