图着色 | Trudbot's Blog

图着色问题(Graph Coloring Problem)是一个著名的 $N P C$ 问题，其内容是，对于给定的无向图，为每个顶点指定一颜色，且使得相邻的顶点颜色不相同。

将图G以如上规则着色所需要的最少颜色数表示为 $χ (G)$ , 被称为最小着色数。

寻找图着色问题可行解——Welsh-Powell算法

welsh-powell算法用于找出一个 $χ (G)$ 不超过图的最大度 + 1 的图着色问题的解。

算法流程

将所有未着色的顶点集按度降序排序
为度最大的顶点染一个未被使用过的颜色color
遍历未着色的所有顶点，若其不与任何被染成color的顶点相邻，则将其染成color
若仍有未着色的顶点，重复123步骤，否则结束

举例

以下无向图举例

graph0

根据度数降序排序后，如下表所示

顶点编号	5	4	9	2	0	12	10	6	3	1	8	7	11
度数	5	5	4	4	4	3	3	3	3	3	2	2	1

第一轮染色， 5、9、2、6、7被染成相同颜色

graph1

第二轮染色， 4、12、10、3、11被染成相同颜色

graph2

第三轮染色， 0、1、8被染成相同颜色

graph3

以上图示使用网站工具Graph Editor (csacademy.com)绘制

代码实现

cpp

vector<int> welsh_powell(vector<vector<int>> &g) {
  int n = g.size();
  vector<int> color(n, 0);
  vector<int> v;
  for (int i = 0; i < n; i ++) v.push_back(i);
  sort(v.begin(), v.end(), [&g] (const auto &a, const auto &b) {
    return g[a].size() > g[b].size();
  });
  for (int cnt = 1; v.size(); cnt ++) {
    vector<int> t;
    for (auto &u : v) {
      if (color[u] == -1) {
        t.push_back(u);
      } else {
        color[u] = cnt;
        for (auto &adj : g[u]) {
          if (color[adj] == 0) color[adj] = -1;
        }
      }
    }
    for (auto &x : t) color[x] = 0;
    v = t;
  }
  return color;
}

饱和度算法

饱和度算法(DSatur Algorithm)是对Welsh-Powell算法的改进，它除了考虑考虑顶点的度外，还考虑顶点的饱和度(已着色的邻接点数量)。

DSatur算法同样不能保证得到最小着色数，但表现上比Welsh-Powell算法更好。

详见DSatur Algorithm for Graph Coloring - GeeksforGeeks

四色定理

四色定理（英语：four color theorem）又称为四色地图定理（英语：four color map theorem），是一个著名的数学定理[1]：如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样[2][3]

四色定理是第一个主要由电脑验证成立的著名数学定理。这一证明刚开始并不被所有的数学家接受。1979年，逻辑哲学和数学哲学家托马斯·蒂莫兹佐在《四色定理及其哲学意义》一文中提出，四色定理与其证明能否称之为“定理”和“证明”，尚有疑问。“证明”的定义也需要进行再次审视。蒂莫兹佐的理由包括两点：一方面，计算机辅助下的证明无法由人力进行核查审阅，因为人无法重复计算机的所有运算步骤；另一方面，计算机辅助的证明无法形成逻辑上正则化的表述，因为其中的机器部分依赖于现实经验的反馈，无法转换为抽象的逻辑过程[22][23]。即便在数学界中，对四色定理证明的误解也存在着。有的数学家认为证明是杰出的进展，也有人认为依赖计算机给出的证明很难令人满意[3]:197。也有人认为，计算机辅助证明数学定理不过是对人的能力进行延伸的结果，因为电子计算机不过是依照人的逻辑来进行每一步的操作，实际上只是将人能够完成的工作用更短的时间来完成[3]:198。还有人将计算机辅助证明和传统证明的差别比喻为借助天文望远镜发现新星和用肉眼发现新星的区别[24]。

**平面图：**如果无向图 $G$ 能在平面上画出图解，且没有任何边存在交叉，则 $G$ 是一个平面图。

一张地图即可抽象为一个平面图，四色定理也就说明，对于平面图， $χ (G) \leq 4$ .