图的着色问题汇总

2020-12-05

5 minute

algorithm

二分图问题

能否只用 2 种颜色对一个图上色，并且使得共边顶点不同色？

代码解决：

 1vector<int> G[MAX_V];
 2int vertexes;
 3int edges;
 4int color[MAX_V];  //二分图，颜色为1或-1
 5bool dfs(int v, int c) {
 6  color[v] = c;
 7  for (int i = 0; i < G[v].size(); i++) {
 8    if (color[G[v][i]] == c) return false;
 9    if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
10  }
11  return true;
12}
13void solve() {
14  for (int i = 0; i < vertexes; i++) {
15    if (color[i] == 0) {
16      if (!dfs(i, 1)) {
17        printf("No\n");
18        return;
19      }
20    }
21  }
22  printf("Yes\n");
23}
24solve();

二分图是着色问题的特殊情况，即图的最小着色数为2，接下来的问题是：

图的最多着色方法数问题

对 V 个顶点，E 条边的图，用小于 num_color 种颜色进行涂色，要求共边的两点颜色不相同，一共有多少种涂法？

重要思想：回溯

代码解决：

 1int G[MAX][MAX]; // init: 0
 2int color[MAX]; // init: 0
 3int V, E, num_color, ccount = 0;
 4bool Judge_Color(int v, int col) { // 对v点用col继续涂色
 5  for (int i = 1; i <= V; i++)
 6    if (G[i][v] == 1 && color[i] == col) return false;
 7  return true;
 8}
 9void Solve(int v) {
10  if (v > V) { // 涂色完毕
11    ccount++;
12    for (int i = 1; i <= V; i++) cout << color[i] << " ";
13    cout << endl;
14    return;
15  }
16  for (int i = 1; i <= num_color; i++) {
17    if (Judge_Color(v, i)) { // 如果可以涂色则进行涂色
18      color[v] = i;
19      Solve(v + 1);
20      color[v] = 0; // 回溯
21    }
22  }
23}
24Solve(1); // 从第一个结点开始涂色

以上问题我们给定了最小的涂色数，求的是方法的个数，反过来呢？

现在我们想要用最少的颜色达到目标，就是要求一幅图的最小着色数了：

思路：从小到大增加着色数，判断以当前数量的颜色是否可以成功涂色，如果可以一一选取其中可以涂色的颜色进行涂色，如果不可以则新增颜色涂色

最小着色数问题

基本思想：剪枝与回溯

 1int G[MAX][MAX]; // init: 0
 2int color[MAX]; // init: 0
 3int V, E, c_min = MAX + 1;
 4bool Judge_Color(int v, int col) { // 判断v是否可以用col涂色
 5  for (int i = 1; i <= V; i++)
 6    if (G[i][v] == 1 && color[i] == col) return false;
 7  return true;
 8}
 9void Solve(int v, int num_color) {
10  if (num_color >= c_min) return;  //剪枝
11  if (v > V) { // 涂色完毕
12    c_min = min(c_min, num_color);
13    return;
14  }
15  for (int i = 1; i <= num_color; i++) {
16    if (Judge_Color(v, i)) { // 如果可以用这种颜色涂色
17      color[v] = i;
18      Solve(v + 1, num_color);
19      color[v] = 0;  //回溯
20    }
21  }
22  // num_color种颜色不够用了
23  color[v] = num_color + 1; // 新增一种颜色
24  Solve(v + 1, num_color + 1);
25  color[v] = 0; // 回溯
26}
27Solve(1, 1);

下面是有关最小着色问题相应实际问题的解决。

分考场问题

n 个人参加某项特殊考试。为了公平，要求任何两个认识的人不能分在同一个考场。求是少需要分几个考场才能满足条件。

 1int G[MAX][MAX]; // init 0
 2int room[MAX][MAX]; // 保存教室i中第j个学生的id, init: 0
 3int c_stu, c_relation, min_room = MAX + 1, count_room;
 4void solve(int x, int count_room) {
 5  if (count_room >= min_room) return; // 剪枝
 6  if (x > c_stu) { // 学生分配完毕
 7    min_room = min(min_room, count_room);
 8    return;
 9  }
10  for (int i = 1; i <= count_room; i++) {
11    int flag = true, j = 0;
12    while (room[i][j]) { //查找学生教室中是否有认识的人
13      if (G[x][room[i][j]]) {
14        flag = false;
15        break;
16      }
17      j++;
18    }
19    if (flag) { // 教室里没有认识的人
20      room[i][j] = x;
21      solve(x + 1, count_room); // 继续用现有教室分配下一个学生
22      room[i][j] = 0;
23    }
24  }
25  // 教室不够 新增一个教室并把学生放进教室
26  room[count_room + 1][0] = x;
27  solve(x + 1, count_room + 1);
28  room[count_room + 1][0] = 0;
29}
30
31solve(1, 1); // 最开始用一个教室分配学生