1. 问题

图的m着色问题。给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色。如果要求G的每条边的两个顶点着不同颜色。给出所有可能的着色方案；如果不存在，则回答“NO”。

2. 解析

设图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叉树.在解空间树中做深度优先搜索(约束条件:if a[i][j]=1,x[i]!=x[j])
举例：

该图顶点数为4，设色数为3，即求m=4,n=3时的解空间树

着色方案:(1,2,3,3)

3. 设计

void InPut()
{
int pos1, pos2;
scanf(“%d %d”, &pointnum, &m);
scanf(“%d”, &edgenum);
memset(Graph, 0, sizeof(Graph));
for(int i = 1; i <= edgenum; ++i)
{
scanf(“%d %d”, &pos1, &pos2);
Graph[pos1][pos2] = Graph[pos2][pos1] = 1;
}
}
bool IsOk(int i)
{
for(int j = 1; j < i; ++j)
if(Graph[i][j] == 1 && x[j] == x[i])
return false;
return true;
}
void BackTrack(int i)
{
if(i > pointnum)
{
sum += 1;
printf(“方法 %d : “, sum);
for(int j = 1; j <= pointnum; ++j)
{
printf(“%d “, x[j]);
}
printf(“\n”);
return;
}
else
{
for(int j = 1; j <= m; ++j)
{
x[i] = j;
if(IsOk(i))
BackTrack(i + 1);
x[i] = 0;
}
}
}

4. 分析

5. 源码地址