给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

例如：点个数n=7，颜色m=3的涂色方案

 一般连通图的可着色问题，不仅限于可平面图。

 给定图G=（V，E）和m种颜色，如果该图不是m可着色，给出否定回答；若m可着色，找出所有不同着色方法。

设图G=(V, E), |V|=n, 颜色数= m, 用邻接矩阵a表示G, 用整数1, 2…m来表示

m种不同的颜色。顶点i所着的颜色用x[i]表示。

问题的解向量可以表示为n元组x={ x[1],…,x[n] }. x[i]∈{1,2,…,m},

解空间树为排序树,是一棵n+1层的完全m叉树.

在解空间树中做深度优先搜索, 约束条件:如果a[j][i]=1 , x[i] ≠ x[j]

m=3,n=3时的解空间树

对于下图，写出图着色算法得出一种着色方案的过程。

顶点数量n=4, 色数：m=3

m=4,n=3时的解空间树 X[1]←1 , 返回 true X[2]←1, 返回false; X[2]←2, 返回 true X[3]←1 ,返回false; X[3]←2, 返回false;X[3]←3, 返回 true X[4]←1, 返回false; X[4]←2, 返回false;X[4]←3, 返回 true

着色方案：（1，2，3，3）

图m可着色问题的解空间树中，内结点个数是：                   对于每一个内结点，在最坏情况下，用ok检查当前扩展结点每一个儿子的颜色可用性需耗时O(mn)。

因此，回溯法总的时间耗费是