图的k-星着色的Gröbner基求解

尹杰杰

(海南大学信息科学技术学院，海南海口570228)

在应用数学领域中，多项式理想的Gröbner基方法不仅可以用来判别多项式方程组解的存在性，还可以在解存在的情况下判别解的个数的有限性，Gröbner基方法已经被广泛用于图论中各种问题的多项式方程组模型的求解，参考文献［1-4］.对于具有n个顶点的简单连通图G，笔者证明了求解G的k-星着色等价于求解一个多元多项式方程组的所有 {1，2，…，k}解，并使用Gröbner基给出求解方法，从而得到求G的极小星着色和星色数的一个可行途径，最后通过实例验证了此代数计算方法的有效性.

注意到k-星着色是有限的，由多项式方程组模型得到的Gröbner基构成的方程组是较容易求解的三角形方程组，G的极小星着色和星色数在求解有限个方程后即可得到.如今多项式理想的Gröbner基的计算技术已经非常成熟，如MAPLE，Macaulay，CoCoA等任意计算代数程序都可计算出给定多项式方程组，确定其理想的Gröbner基.因此，本文代数计算方法可直接应用于任何一个有限图，不涉及已有计算Gröbner基的算法的复杂性，也不讨论其与已有只求极小星着色的优化算法的比较.

1 预备知识

主要介绍本文所需的图论知识，参考文献［5-7］.

给定图 G=(V，E)，其中 G 的顶点集 V={v1，…，vn}，边集 E={eij=vivj|vi，vjV，i≠j}.

定义1 若相邻的2顶点所着的颜色不同，则称该着色是正常的顶点着色.若相邻的2条边所着的颜色不同，则称该着色是正常的边着色.

定义2 图G的星着色是指图G的正常的点着色并且使得G中任意长为3的路上的点不着相同的颜色.图G的星色数是G的星着色所用颜色个数的最小值，记作χs(G).

定义3 k≥4时k-星着色就是该星着色所用颜色种数为k.

定义4 T是图G的星着色，若不存在任何其它星着色T'，使得 |T'|＜|T|，则称T是图G的极小星着色.

定义5 设图G=(V，E)是简单连通图.则图G的邻接矩阵定义为A=［aij］n×n，其中

2 k-星着色的多元多项式刻画

将k-星着色的存在性和求解问题转化为多元多项式方程组解的存在性与求解问题，并使用Gröbner基给出图是否含有k-星着色的有效判别方法.

对于图 G，对其 k-星着色引入向量 X=(x1，x2，…，xn)，其中

显然xi取值在{1，2，…，k}中，即xi的取值是方程(xi-1)(xi-2)…(xi-k)=0的解.讨论点viV，任意与vi相邻的点vj(eijE)，因为星着色满足任何一条长为3的路上的点不着相同的颜色:

1)点vi与点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相邻的点 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相邻的点va，任意与 vj相邻的点 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得到多元多项式方程组

给出方程组(Sk)的解与图G的k-星着色方案的对应关系:

定理1 方程组(Sk)的解对应图G的一个k-星着色，反之亦然，且该对应是一一对应.

证明 充分条件 令(Sk)的任意一个解x0=(x1，x2，…，xn).故由k-星着色的定义可知该解对应一个k-星着色方案，即对xi，其中i{1，2，…，n}的取值进行分类，取值相同的归于一类，染同一种颜色.由于有k种不同的取值，也就能得到k类，染k种不同的颜色.按此分类着色就可得到一个k-星着色方案.

必要条件 取图G的一个k-星着色方案，记{1，2，…，k}为该k种着色对应的取值.按照k-星着色中相邻顶点不能染相同颜色，且G中任意长为3的路上的点不着相同的颜色.故该着色方案对应的着色向量x1=(x1，x2，…，xn)是满足方程组(Sk)的，所以可知着色向量x1是方程组(Sk)的一个解.

显然可知给出的对应是一一对应的.

用Gröbner基方法来给出k-星着色存在性的一个有效判别.

定理2 对于给定的k，其中1≤k≤n，考察复数域C上多项式确定的方程组

1)G是k-星着色⇔方程组(Sk)有解.

2)若方程组(Sk)有解，则(Sk)的所有解给出G的所有k-星着色的方案.

3)令I是方程组(Sk)中方程左端多项式生成的理想.则方程组(Sk)有解⇔理想I的Gröbner基不含非零常数.

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

2)若方程组(Sk)有解，则对于(Sk)的一个解，可知此解对应一个星着色方案，所以(Sk)的所有解对应k-星着色的所有方案.反之对于图G的一个k-星着色，则其对应的向量x=(x1，x2，…，xn)满足(Sk)的解，故由定理1的结论可知方程组(Sk)成立.因此由该k-星着色对应的向量就是方程组(Sk)的一个解，即方程组(Sk)的解和图G的k-星着色是一一对应的，方程组(Sk)的所有解给出G的所有k-星着色.

3)由于方程组(Sk)的解的存在性与理想I的Gröbner基［1］给出的方程组的解的存在性是等价的.若方程组(Sk)有解，则V(I)≠Ø，即G≠{1}，理想I的Gröbner基不含非零常数;若理想I的Gröbner基不含非零常数，就有V(I)≠Ø，方程组(Sk)有解，得证.

3 求图的k-星着色的Gröbner基方法

在方程组(Sk)有解的情况下，只要解方程组(Sk)即可得到图G的所有k-星着色.求解多元多项式的方法虽然很多，但是注意到方程组(Sk)如果有解，则其解都在集合{1，…，k}内，且解的个数是有限的.由文献［1］可知在某个消元单项式序下，例如在单项式序xm＞xm-1＞…＞x1下理想I的一个约化Gröbner基给出与方程组(Sk)等价的方程组形式为因此，在某个消元单项式序下计算出理想I的一个约化Gröbner基后，就可采用回代的方法计算出图G的所有k-星着色.在实际应用定理2和此结论时，只需先调用MAPLE计算Gröbner基的程序，便可判断一个图G是否有k-星着色，若有，再调用求解方程组的程序对方程组进行求解即可得到G的所有k-星着色.

4 求图的星色数的计算方法

一个图的k-星着色(若存在)不一定是唯一的，但由于每个有限图中星着色的顶点数是有限的，着色的颜色种数也是有限的，故k-星着色中着色数k有最小值，而该最小值就是该图G的星色数.根据定理2给出求图G的星色数的一种方法.

定理3 k是图G的星色数⇔方程组(Sk)有解而方程组(Sk-1)无解.

证明 充分条件 若k是图G的星色数，则说明图G的极小星着色所用的颜色为k，由定理2知方程组(Sk)有解.由星色数的定义，图G中星着色所用的颜色最少为k，故图G中不存在边着色数为k-1的星着色，所以方程组(Sk-1)无解.

必要条件 若方程组(Sk)有解而方程组(Sk-1)无解，由定理2的结论知图G存在k-星着色但不存在(k-1)-星着色，说明图G中星着色所用的颜色最少只能为k，所以根据星着色的定义k是图G的星色数.

图1 有限图G

5 举例

考察有限图 G=(V，E)，其中顶点集 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的星色数.

现在讨论顶点 v6，v6e56，可以得到方程组 (S'6)

同理，由其他点都可以得到此类型的方程组，总共有8个方程组.然后把此8个方程组合并成一个方程组即为(Sk).

由定义可知 k=1，2，3时，显然不成立，现在从 k=4开始讨论.

当k=4时通过MAPLE计算(S4)的一个约化Gröbner基G4={1}，则可知包含非零常数，得到方程组(S4)是无解的，所以不存在4-星着色.

当k=5时通过MAPLE计算(S5)的一个约化Gröbner基G5={1}，则可知包含非零常数，得到方程组(S5)是无解的，所以不存在5-星着色.

当k=6时通过MAPLE计算(S6)的一个约化Gröbner基G6={1}，则可知包含非零常数，得到方程组(S6)是无解的，所以不存在6-星着色.

当k=7时通过MAPLE计算(S7)的一个约化Gröbner基，然后用MAPLE计算(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)成立，所以该图的星色数为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-独立集与Gröbner基求解［J］.工程数学学报.2012，29(5):696-702.

［4］熊雪玮.几个图论问题的多项式建模与Gröbner基求解［D］.海口:海南大学，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.