这一讲介绍图的着色问题。

首先我们看看问题的定义。

它的输入是一个无向的连通图。

有M种颜色。用这些颜色来给图的

顶点着色。每个顶点是一种颜色。要求每条边的两个端点一定是不同的颜色。这是它的

着色要求。它的输出是所有可能的着色方案。

如果不存在着色方案的话，就回答NO。这是问题的

描述。我们来看一个例子。这是一个七个顶点的图。

然后我们用三种颜色来对它进行着色。

右边这就是一个着色方案。

是它的一个解。我们看到这里边的每条边，都被着以不同的颜色。

它的端点颜色都是不一样的。这是一个实例。下面我们看一下它的

算法的设计。首先我们给出输入，是一个图。这是它的

顶点标号。颜色呢，标记成1、2到M。颜色的标号。

它的解是一个

向量。这个向量的每个分量的取值，就是1、2到M中的

某个整数。代表的是对比如说Xi等于2，那就是X2

X2被着以第二种颜色。所以这就是一个

着色方案。那么结点的部分向量就是已经对1、2、3、4、K前K个结点已经选择了

着色的颜色了，这就是一个部分向量。下面我们看看它的搜索树。

这是一个M叉的树。因为每一个结点它的初始都可以有M种可能的颜色来对它

进行着色。其中选择一中就是了。约束条件

在部分向量X1到XK这个

位置，下一次我们要对K加1号顶点进行着色。

如果K加1号顶点和这里面的某些顶点是邻接的，而这里边的顶点已经

用过的颜色，在K加1号顶点的选择中就不能再用了。这个是

约束条件。那么如果一个顶点，跟它邻接的那些顶点把

M种颜色都用到了，那这个顶点就没有办法着色了。这时候就必须回溯，回溯到它的

父结点。这个约束条件我们看到是满足多米诺性质的。

因为前面的比较少的分量如果都

颜色冲突的时候，你再对后面的结点来涂以颜色是没有用的。它找不到合理的

着色方案。搜索策略假定我们用深度优先的办法来进行搜索。它的时间复杂度会

比较高。因为这是一个M叉树。树的叶结点如果全部画全的话应该是M的N次方

这个量级。而在每个节点处我们还要判定这些节点之间的颜色是不是冲突，至少需要O

n的工作量。所以它应该是这样的时间复杂度。下面我们看一个例子，就是

刚才这个图。这是刚才给的着色方案。

初始先从这个根开始，就是说这个是出发点，然后我们考虑对

1号结点进行着色，它第一种可能的颜色是第一号颜色，

比如红色。它着完了以后，二号结点它就不能再着红色了，

因为这两个结点是在同一条边的两个端点。因此它可用

第二种颜色，比如蓝色。当它用了蓝色以后，三号结点还可以用红色，我们现在是深度优先的办法。

然后四号结点不能用红色了，因为这两个结点是同一条边的端点。那么它可以用蓝色，

到这个结点着完了以后，五号结点还可以

用红色，下面六号结点就

不能再着了。因为六号结点关联的是五号、四号、一号，这三个都着完了，

而这三个着好以后，六号结点已经没有颜色可以选择了。

它把其他的结点，把三种颜色都占掉了。

那么这个时候是六号结点它一和二两种颜色都不能要了，只能选择三种颜色。

那么下面到七号结点，七号结点我们发现跟它关联的

一、二、三、

六四个结点都关联了，而一、二、三、六已经占有了三种颜色。所以七号结点已经

不可再着色了。因此从这个结点回到父结点。

又回到这。那么这个地方不能着第二种颜色。

它可以考虑第三种颜色。

然而到这个结点，我们再看到，下一层六号结点

已经不能够再着色了，因此从它又回到它的副结点。

然后又回到这个结点。那么考虑第三个方向的颜色，三，三的颜色。

三的颜色选择完了，下个可以考虑用一的颜色。

然后再下一层这个一不能用了，因为这两结点是邻接的，那么它可以考虑二号的颜色，

那么它考虑了二号以后，下一层一号、

二号都不能用了。它可以考虑三号的颜色。到这个时候为止，我们已经找到了一个着色的方案。

这是一个可行解。那么

这可行解我们可以把它标记出来。红、蓝、红、灰、

红、蓝、灰，正好就是这图的这个解的表示。

后边我们再继续由它回去，回到这，这边还可以再继续向

这个方向搜索。然后后边每一个结点都可以向右边还可以有一个大范围的搜索空间。

这棵树就没有画。因此我们通过这个例子展示了这颗搜索树的一个

运行的实例。下面我们看一下这颗搜索树的情况。刚才我们只是画出了

这一部分。这一部分。

那么这边是一大片没有解的搜索空间，那这是就是说这

第一种颜色，第二种颜色，然后这边得到的是刚才那个可行解。在整个以它为根的这个子树里头，

只有这一个解。如果回到这个结点，向这走，那这个地方是

三，这个是一、二，这个是一、三，那么这边要搜索出来它的空间也

是这么大，可以找到另外一个可行解。那么这个解实际上我们可以不用真的

去遍历它，为什么？我们只要把这个解的所有的2的位置都

换成3，所有的3的位置都换成2，恰好就是这个解。

所以这两个解是一个对称的分布，只要做一个对换就可以了。

那么根据这样的分析方法，我们这是第一个结点上第一种颜色的时候可以找到

两个可行解，从这个地方第一种，第一个结点如果要上

第二种颜色的时候，相当于我这个取2，它可以按照刚才这个对应的生成方法，从这个方向上也有两个可行解，

只不过把这个1和这个2对换，

把这两个解中的1和2都对换过去以后，就可以得到对应第二个方向的两个解。

同样的，那么当第一个结点要上

第三种方向的时候，也可以通过这种对称的办法找到第三个方向的两个解。一共是六个解。

这时我们的搜索树的整个的结构。

通过刚才的分析我们看到，并不一定要真正的遍历整个这棵树的全部的空间，

我们只要遍历这六分之一的这个范围，

找到这个可行解以后，其他的五个解都是可以通过对称的方法把它

生成出来。那个工作量就很小了。它就省掉了

六分之五的时间。这个是利用对称性来裁剪

这个树的一个方法。另外一个方法我们观察到这个分支。这个分支

实际上也是没有解的，为什么？第一个结点是第一种颜色，

第二个结点是第二种颜色，第三个结点第三种颜色，就是说这三个结点分别取了，

不同的颜色。但是这三个结点都关联一个共同的点

7，7号点，那么如果这三个结点已经把

三种颜色取全了，7号点是没有办法涂色的。因此在这个位置，我们要进行一下

已经涂了颜色的结点有没有共同关联的顶点呢？如果要进行这个判断的话，我们就知道下边不可能有解的。

所以这个方向也可把它裁掉。

但是裁掉的代价是什么？就是我们在这个地方要做一下这三个结点会关联共同结点的这样判定工作。

所以在这个位置要增加一个工作量。从而把这个地方给裁掉。

到底是增加工作量裁掉一个空间合适呢？

还是我干脆不作这种增加工作量的判定，我就直接这个

遍历这个空间更合适呢？这是根据不同的问题有不同结果。

所以要做权衡，要做具体的分析。

把刚才这分析的方法小结一下，它的时间复杂度是NM平方量级，

根据对称性我们只需要搜索三分之一的解空间，

甚至搜索六分之一的解空间，就可以得到所有的解。所以对称性是在

回溯算法中，裁剪空间的一个有效的方法。

可以考虑使用。另外就是说我们在某些结点增加一些判定的工作量，

可以裁减更多的空间。这个要做权衡，是增加工作量合适还是减少

工作量合适。所以要在这个地方，通过权衡考虑需要不需要这种判定。

这是另外一种可行的方法。

下面介绍着色问题的应用。比如说一个会场分配的问题

有N项活动需要安排在一个会场上，如果两个活动I和J它的时间有冲突，

这个时候就说他们不相容。

怎么分配这些活动使得每个会场的活动都相容？而且占的会场个数最少。

这是一个会场分配问题。这问题我们可以建模成一个图的着色问题。

把这些活动都看做图的顶点，如果两个活动不相容，我们就连一条边，

那么下边就对会场，也就是说那些顶点进行着色。

找到一种颜色最少的着色方案，正好就是一种分配方案。

因为它同一条边的两个端点，都是不同颜色的。所以不相容的活动不会分配到一个会场里头。

这就是着色问题的一个实际应用。

把这一讲小结一下。

首先我们先给出着色问题的描述。

介绍了它的算法设计，最后介绍了的它的时间复杂度和

改进的途径。讲了一个它的应用的实例，这是这一讲的主要内容。

068图的着色

算法设计与分析 Design and Analysis of Algorithms

与讲师见面