问题描述

给定无向连通图和m种不同的颜色，用这些颜色为图G的各个顶点着色，每个顶点有一种颜色

是否有一种着色方法？使得图G中每条边的两个顶点有不同的颜色

这个问题就是图的m可着色判定问题

色数：如果有一个图最少需要m种颜色才能使得图中每条边连接的2个顶点有着不同的颜色，称m是这个图的色数。

著名的平面图的四色猜想就是图的m可着色判定问题的特殊情形，可平面图是什么？如果一个图的所有顶点和边都可以用某一种方式画在一个平面上，并且没有任何两条边相交，就成为可平面图。

四色猜想：

问题分析

变量声明

无向连通图G(V,E)用邻接矩阵a表示，a[ i ][ j ]=1表示i和j两个顶点之间存在一条边( i , j )，即( i , j )属于图G(V,E)的边集E。 否则，a[i][j]=0。

整数1,2,3，...，m表示m种不同的颜色

顶点i的颜色用x[ i ]表示。x[ i ]就是问题的解

解空间

解空间可以表示为一颗n+1高度的完全m叉树，第i层有m个儿子，每个儿子对应X[ i ]的一种可能性

第一层就是第一个顶点，第二层第二个顶点，...，第n+1层是最后一个顶点（叶子）。每个分支结点，都有m个儿子结点。最底层有个叶子结点。

回溯逻辑

剪枝--检查什么可行性？

可行的条件是yu当前点相邻的点不能与之同色

backtrack（int i）

完整代码

//最大团问题
#include 
#include 
#include 
#include 
using namespace std;const int maxnum = 101;
bool a[maxnum][maxnum]; //图的邻接矩阵
bool x[maxnum];         //当前解
int cn;                 //当前团的顶点数
int bestn;              //当前的最优解
int n;                  //图G的顶点数
int e;                  //图G的边数
void display(){for (int j = 1; j <= n; j++){if (x[j]) printf("%d ", j);}printf("\n");
}
void backtrack(int i){int j;if (i > n){bestn = cn;printf("%d\n", bestn);display();return;}bool ok = true;for (j = 1; j < i; j++){if (x[j] && !a[j][i]) // i与j不相连{ok = false;break;}}if (ok) //进入左子树{cn++;x[i] = true;backtrack(i + 1);cn--;}if (cn + n - i > bestn) //剪枝{x[i] = false;backtrack(i + 1);}
}int main(){int i, u, v;memset(a, false, sizeof(a));memset(x, false, sizeof(x));scanf("%d%d", &n, &e); // 定点数，边数for (i = 0; i < e; i++){scanf("%d%d", &u, &v);a[u][v] = true;a[v][u] = true;}cn = bestn = 0;backtrack(1);return 0;
}/*
5 7
1 2
1 4
1 5
2 5
2 3
3 5
4 5
*/

测试用例

输入

输入定点数，边数，着色种类数

5 8 4

1 2

1 3

1 4

2 3

2 4

2 5

3 4

4 5

输出

48

P2819 图的 m 着色问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

又是一个子集树的回溯法，分析结束。还是很像模板的。