用吴方法解决染色问题

Solve the Dyeing Problem by Wu’s Method

摘要: 染色问题是图论中的著名问题，目前已有人用Groebner基方法解决了染色问题，本文另辟蹊径用吴方法来解决染色问题。吴方法又称特征列方法，是吴文俊于20世纪70年代提出的处理多项式代数问题的一种方法。与Groebner基方法不同之处在于，它完全采用零点集的观点来处理问题，因此在染色问题求解方面较Groebner基方法更有效，本文仅解决染色问题中的三色问题。

Abstract: Dyeing problem is a famous problem in graph theory; the dyeing problem has been solved by Groebner bases method. This text applies the technique of Wu’s method to solve the dyeing problem. The Wu’s method is also called the feature list method; it is a method to deal with polynomial algebra problem proposed by Wu Wenjun in the 1970s. The difference between Wu’s method with Groebner bases method is that Wu’s method completely uses the viewpoint of zero set to deal with the problem, so it is more effective than Groebner bases method in solving dyeing problems; this paper only solves the 3-color problem in the dyeing problem.

1. 引言

这部分内容涉及到图论的知识：一个图有n个顶点，任何两个顶点之间最多有一个边。我们想用三种颜色去染这些顶点，使得同一个边的两个顶点被染的颜色不同，即三色问题 [1]。我们认为地图与三色问题的原理是相同的，这些顶点代表着被染色的区域，两个顶点是被连接的通过一个边如果这两个相应的区域是毗邻的。

首先，我们令 $\xi ={\text{e}}^{\frac{2\text{π}i}{3}}\in C$是单位1的立方根，我们用单位1的3个不同的立方根 $1,\xi ,{\zeta }^2$代表这三种

颜色，现在我们令 $x{}_1,\cdots ,x_n$这n个变量代表图G的n个不同的顶点。每一个顶点是 $1,\xi ,{\zeta }^2$这三种颜色中的一个。以上通过下面的n个方程来表示：

$x_i^3-1=0,i=1,2,\cdots ,n$(1.1)

如果顶点 $x_i,x_j$是被连接的通过一条边，它们需要有不同的颜色。因为 $x_i^3=x_j^3$，我们有 $\left(x_i-x_j\right)\left(x_i^2+x_i{x}_j+x_j^2\right)=0$。因此 $x_i,x_j$将会有不同的颜色当且仅当：

$x_i^2+x_i{x}_j+x_j^2=0$(1.2)

令I是 $C\left[x_1,\cdots ,x_n\right]$的理想， $C\left[x_1,\cdots ,x_n\right]$是由(1.1)和(1.2)这些多项式产生的。我们将考虑包含在 $C^n$中的 $V\left(I\right)$，将会有下面的定理。

定理1.2.1：一个图是三色问题当且仅当 $V\left(I\right)\ne \varphi$。

我们可以用Groebner基去决定是否 $V\left(I\right)=\varphi$，我们首先计算I的一个可约的Groebner基，如果 $1\in G$，则 $V\left(I\right)=\varphi$，否则 $V\left(I\right)\ne \varphi$。

2. 预备知识

我们首先回忆升列，矛盾列，基列和特征列的定义，可见文献 [2][3]。

2.1. 升列的定义

对于两个非零多项式F和G，如果下列两个条件之一成立：

1) $cl\left(F\right)<cl\left(G\right)$。

2) $cl\left(F\right)=cl\left(G\right)=p>0$，但 ${\mathrm{deg}}_{x_p}\left(F\right)<{\mathrm{deg}}_{x_p}\left(G\right)$。

我们称F的级别比G低(或者称G的级别比F高)，记作 $F\prec G$或者 $G\succ F$。

设F是一个多项式， $cl\left(F\right)=p>0$。对任何一个相对于 $x_p$比F级别低的多项式G都称为相对于F是约化的，记为G red/F。

下面考虑有限多个多线式组成的序列

$A:A_1,A_2,\cdots ,A_r$

如果下列两条件之一成立：

1) $r=1,A_1\ne 0$。

2) $r>1,0<cl\left(A_1\right)<cl\left(A_2\right)<\cdots <cl\left(A_r\right)$，且对任意 $j>i,A_{j}red/A_i$。

我们称A为一个升列 [2]。

2.2. 矛盾列的定义

一个升列称为矛盾列，如果 $r=1,A_1\ne 0$，但 $cl\left(A_1\right)=0$。即一个非零常数构成的升列是矛盾列。当把升列看成多项式方程组时，矛盾列总是没有解的。

2.3. 基列的定义

设A为一升列，G为一多项式。如果G相对于升列A中每个多项式都是约化的，则称G相对于升列A是约化的。

设另有升列

$B:B_1,B_2,\cdots ,B_s$

如果下列两条件之一成立：

1) 存在 $j\le \min \left(r,s\right)$，使得 $A_1~B_1,\cdots ,A_{j-1}~B_{j-1}$，但 $A_j\succ B_j$。

2) $s>r$且 $A_1~B_1,\cdots ,A_r~B_r$。

我们称A比B的级别高，或者说B比A的级别低，记为 $A\succ B$或 $B\prec A$。如果A和B中每个都不比另一个级别低，则称二者有相同的级别，记作 $A~B$。此时必有 $r=s,A_1~B_1,\cdots ,A_r~B_r$。

定理2.3.1：(Ritt引理)设 $A_1,A_2,\cdots ,A_q,\cdots$为一不增的升列组成的序列，即对任何q，有 $A_{q+1}\prec A_q$或 $A_{q+1}~A_q$成立，则存在指标 $q^{\prime }$，使得对任意 $q>q^{\prime }$恒有 $A_q~A_{q^{\prime }}$，即 $A_{q^{\prime }}$为上述序列中级别最低的升列。

推论2.3.1：若由升列组成的序列严格下降，则该序列必定只由有限个升列构成。

现在我们来定义升列集合上的极小元。

设PS为有限多个非零多项式组成的多项式集合。一个升列A称为属于PS是指A的每个多项式都属于PS。因为单个多项式本身也构成一个升列，所以属于PS的升列集是非空的。于是属于PS的升列集上的级别是一个偏序。由定理2.3.1，按此偏序每个升列的不增序列都有一极小元，该极小元自然属于PS。我们称这种极小元为PS的一个基列 [2]。

2.4. 特征列的定义

定理2.4.1：设PS为非零多项式构成的有限集 $A:A_1,A_2,\cdots ,A_r$，是PS的基列， $cl\left(A_1\right)>0$。设B为一非零多项式，且 $Bred/A_i,i=1,\cdots ,r$，则 $P{S}^{\prime }=PS\cup \left\{B\right\}$有一比A级别低的基列。

下面假设PS为一非零多项式构成的集合，我们来讨论其所谓特征列的构造。

对给定的 $P{S}_1=PS$，由定理2.4.1，存在 $P{S}_1$的基列 $B{S}_1$。将所有 $P{S}_1\text{-}B{S}_1$中的多项式对基列 $B{S}_1$求余式，则得一余式的集合 $R{S}_1$。若 $R{S}_1\ne \varphi$，令 $P{S}_2=P{S}_1\cup R{S}_1$。再找出 $P{S}_2$的基列 $B{S}_2$。注意， $P{S}_2$是由 $P{S}_1$添加所有对 $B{S}_1$的余式而得的，所以 $B{S}_2$的级别比 $B{S}_1$低。再将 $P{S}_2\text{-}B{S}_2$中的多项式对 $B{S}_2$求余式，并记该余式集合为 $R{S}_2$。如果 $R{S}_2\ne \varphi$，令 $P{S}_3=P{S}_2\cup R{S}_2$，并求其基列 $B{S}_3$，此时有 $B{S}_1\succ B{S}_2\succ B{S}_3\succ \cdots$。由推论2.3.1，这个基列构成的序列是有限的，因而必在某一步，比如说m，使得 $R{S}_m=\varphi$。此时我们称相应的基列 $B{S}_m$为PS的特征列 [2][3]，并记之为CS。

以下是多项组的零点分解定理，可见文献 [2]。

2.5. 多项式组的零点分解

设PS为给定的多项式集合，特征列为 $CS:A_1,\cdots ,A_r$， $A_i$的初式为 $I_i$，并记 $J=I_1\cdots I_r$，则有

定理2.5.1： $zero\left(PS\right)=zero\left(CS/J\right)+zero\left(PS,I_1\right)+\cdots +zero\left(PS,I_r\right)$

其中， $zero\left(CS/J\right)=zero\left(CS\right)-zero\left(J\right)$，“+”表示求并集。

3. 主要结论

3.1. 吴方法解决染色问题的过程

定理3.1.1：一个图是三色问题当且仅当特征列为非矛盾升列。

证明：当特征列CS为矛盾列时，由矛盾列的定义可知特征列CS为一个非零常数构成的升列。因为当把升列看成多项式方程组时，矛盾列总是没有解的，所以可以得出 $zero\left(CS\right)=\varphi$，因为 $CS\subset P{S}_m$， $zero\left(CS\right)\supset zero\left(P{S}_m\right)=zero\left(PS\right)$，即 $zero\left(PS\right)=\varphi$。由定理1.2.1可知一个图是三色问题当且仅当 $V\left(I\right)\ne \phi$，所以一个图是三色问题当且仅当特征列为非矛盾升列。

例题3.1：考虑图1中的图形G。

图G相应的多项式是： $x_i^3-1=0,i=1,\cdots ,8$

$\begin{array}{c}{x}_i^2+x_i{x}_j+x_j^2,\left(i,j\right)\in \{\left(1,2\right),\left(1,5\right),\left(1,6\right),\left(2,3\right),\left(2,4\right),\left(2,8\right),\left(3,4\right),\\ \left(3,8\right),\left(4,5\right),\left(4,7\right),\left(5,6\right),\left(5,7\right),\left(6,7\right),\left(7,8\right)\}\end{array}$

我们求得该多项式组的特征列

$\begin{array}{l}CS=\{x_1-x_7,x_2+x_7+x_8,x_3-x_7,x_4-x_8,x_5+x_7+x_8,\\ x_6-x_8,x_7^2+x_7{x}_8+x_8^2,x_8^3-1\}\end{array}$

Figure 1. The 3-color figure

图1. 三色图

显然，各多项式的初式为 $I_i=1,i=1,\cdots ,8$. 由定理2.5.1有:

$zero\left(PS\right)=zero\left(CS/J\right)+zero\left(PS,I_1\right)+\cdots +zero\left(PS,I_8\right)$

容易看出，对 $i=1,\cdots ,8$， $\left\{PS,I_i\right\}$的特征列为矛盾列，故 $zero\left(PS,I_i\right)=\varphi ,i=1,\cdots ,8$。又因为 $J=I_1\cdots I_8=1$，即 $zero\left(J\right)=\varphi$。由定理2.5.1可知： $zero\left(CS/J\right)=zero\left(CS\right)-zero\left(J\right)$故 $zero\left(CS/J\right)=zero\left(CS\right)$，于是 $zero\left(PS\right)=zero\left(CS\right)$。因为特征列CS为非矛盾升列，所以图C是三色问题。我们假设三种颜色是蓝红绿，因为在CS中只有一个变量的多项式是 $x_8^3-1$，所以我们必须首先给 $x_8$选一个颜色，假设是红色。因为多项式 $x_7^2+x_7{x}_8+x_8^2\in CS$，所以我们为 $x_7$选一个与 $x_8$不同的颜色，比如是蓝色。因为多项式 $x_1-x_7,x_3-x_7\in CS$，所以 $x_1$和 $x_3$是蓝色。因为多项式 $x_4-x_8,x_6-x_8\in CS$，所以 $x_4$和 $x_6$是红色。因为 $x_2+x_7+x_8$和 $x_5+x_7+x_8$在CS中，所以 $x_2$和 $x_5$有相同的颜色且与 $x_7$和 $x_8$的颜色都不同，即 $x_2$和 $x_5$是绿色。

3.2. 吴方法和Groebner基方法在解决染色问题时的比较

Groebner基方法 [4][5][6]在计算过程中会使多项式对增加很快，选取多项式对的无序性也会造成结果不同，项序的选择和终止条件的复杂性与否都会影响计算的效率。吴方法 [7][8]在计算多项式方程组时效率较高，速度也很快，整体来说在解决染色问题上吴方法比Groebner基方法更快速和有效。