图着色问题与算法

可视化演示

图着色要求相邻顶点颜色不同，是NP难问题的经典代表。本文详解顶点着色与边着色、色数与团数关系、贪心着色算法与回... 切换模式查看不同维度。

着色基本概念：为什么“相邻不能同色”

教务主任的桌上，30 张课程卡片摆成一张网。你给“不能同时上的课”之间画一根线：高数和线代连着，因为同一个班的学生要上这两门；线代和体育连着，因为同一个老师下午要连上三节……很快，卡片之间布满连线。这张由“卡片”和“连线”构成的网，就是图论里的图：卡片叫顶点（Vertex），连线叫边（Edge）。你要做的，是给每个顶点分配一个“时间段编号”，让所有被边相连的顶点拿到不同的编号。

用数学语言说：给定无向图 G=(V,E)，图着色就是找一个把顶点映射到颜色编号的函数 c，并且对任意一条边，两个端点的颜色必须不同。如果一个着色只用到了 k 种颜色，就说这个图是“k-可着色”的。比如二分图永远 2-可着色，三角形必须 3 色。判断一个图是否 k-可着色，是这个问题最核心的判定形式——它把一个排课表问题，压缩成了一个纯粹的组合约束问题。

$$\displaystyle \text{合法着色 } c : V \to \{1,2,\dots,k\},\quad c(u) \neq c(v), \quad \forall (u,v) \in E$$

1. 着色函数 c：把每个顶点映射到一个颜色编号。c(u) 表示顶点 u 被分配的颜色，正如你给每门课贴上一个时间段标签。

$$\displaystyle c : V \to \{1,2,\dots,k\}$$

2. 颜色域 {1,……,k}：一共只有 k 种颜色可用，对应现实中“最多 k 个时间段”。k 是预先给定的上限（比如 4 色问题就是 k=4）。

$$\displaystyle \{1,2,\dots,k\}$$

3. 核心约束 c(u)≠c(v)：对每条边，两端颜色必须不同。用生活的语言说：凡是画了线的两门课，绝不能落在同一个时间段。

$$\displaystyle c(u) \neq c(v)$$

4. 全称量词 ∀(u,v)∈E：约束要对图中每一条边生效，一条也不能漏。有一条边违反，整个方案就是非法着色。

$$\displaystyle \forall (u,v) \in E$$

你看，排课表的核心难点根本不在“课多”，而在“冲突密”。把现实关系抽象成顶点和边，图着色就有了第一个实用价值：它把“我看得见的麻烦”翻译成“机器能算的模型”。接下来我们会看到，仅仅是这个翻译动作，就已经解决了一半问题。

边着色与对偶：把比赛安排成时间表

换个场景。你是校运会裁判长，要把 6 场比赛排进一个下午。顶点是球队，边是比赛——同一支球队不能同时踢两场，所以“共享同一个顶点的两条边”必须被安排到不同时间。这一次，冲突的单位不是顶点，而是“边”本身。这就是图着色问题的第二副面孔：边着色（Edge Coloring）。给每条边染色，使得任意两条有公共端点的边颜色不同。

有趣的是，边着色完全可以改造成我们熟悉的顶点着色：把原图的每条边“升格”为一个新顶点；如果两条边在原图共享端点，就在新顶点之间连一条边。这样构造出来的新图叫原图的线图（Line Graph）L(G)。于是，“给 G 的边着色”等价于“给 L(G) 的顶点着色”。这个转换看似绕路，却把两类问题统一了起来。

$$\displaystyle L(G) = \left( E,\ \left\{ (e_i, e_j) \mid e_i \neq e_j,\ e_i \cap e_j \neq \emptyset \right\} \right)$$

1. 线图的顶点集合 E：原图 G 的每一条边，变成线图 L(G) 里的一个顶点。e 从“连接关系”升格为“实体的身份”。

$$\displaystyle V_{L(G)} = E(G)$$

2. 线图的连边规则：两条原边 e_i 与 e_j 共享一个端点时（交集非空），就在线图中对应的两个顶点之间连一条边。

$$\displaystyle (e_i, e_j) \in E_{L(G)} \iff e_i \cap e_j \neq \emptyset$$

3. 对偶关系：原图的边着色，正是线图的顶点着色。研究对象从边“翻转”为顶点，问题本质不变。

有了这个转换，很多边着色结论可以直接从顶点着色理论“平移”过来。最漂亮的成果之一是维津定理（Vizing's Theorem）：任意简单图的边色数 χ'(G)，要么是最大度数 Δ，要么是 Δ+1。Δ 大的顶点就像身兼多职的明星球队，它参与的边必须全部不同色——但神奇的是，边色数永远顶多比 Δ 大 1，不会更糟。这一定理给排比赛提供了硬性承诺：按最大参赛场数准备时间段，最多再加一个备用，一定够。

从球队视角跳出来看，你会领悟到“对偶”的妙处：同一个问题，主语换一下，原本眼花缭乱的关系就清晰了。顶点着色与边着色，就像同一座山的两个登山口，风景不同，山顶相同。

色数与团数：最少颜色数的紧箍咒

排课排到深夜，你问自己一个终极问题：到底最少需要几个时间段？这个“最少颜色数”就是图的色数，记作 χ(G)。它像一把尺子，衡量一张冲突网的“紧绷程度”。但如何估算这把尺子的刻度？一个重要的抓手是“团”：一组顶点，如果两两之间都有边相连，就构成一个团。换句话说，这个小组里的每一对人都是“直接冲突”的——就像五个老师互相都认识且都要上同一批学生的课，这五门课必须各自独占一个时间段。

团给色数提供了一个硬性下限：如果一个团里有 ω 个顶点（ω 叫团数），那么至少需要 ω 种颜色，因为团内任意两个顶点都相邻，谁也不能和谁同色。这就是图论中最重要的不等式之一“色数不小于团数”。

$$\displaystyle \chi(G) \geq \omega(G)$$

1. 色数 χ(G)：图 G 完成合法着色所需的最少颜色数，即最少时间段数。

$$\displaystyle \chi(G) = \min \{k \mid G \text{ 是 } k\text{-可着色的}\}$$

2. 团数 ω(G)：图中最大团的大小，团 = 两两相邻的顶点集合。想象一群“两两互相看不顺眼”的课，谁也不愿意和别人同色。

$$\displaystyle \omega(G) = \max \{|S| \mid \forall u,v \in S, (u,v) \in E\}$$

3. 不等式成立的原因：一个大小为 ω 的团里，任意两个顶点颜色都不同，所以颜色总数至少要有 ω 个。这个道理朴素得就像“五个结过梁子的人开会，必须开五场”。

注意，这个下界不一定能取到等号。例如长度为 5 的环 C₅ 没有三角形（ω=2），却需要 3 色（χ=3）。凡是“χ=ω“恰好成立的图叫完美图（Perfect Graph），二分图、弦图、区间图都是完美图家族的重要成员。排课时，团数告诉你”最坏的小团体有多大“，色数告诉你”全局到底需要多少时间”，两者之间那道鸿沟，往往是算法用武之地。

直觉上，最大团像“地心引力”，把颜色数牢牢吸在一个下限上。可现实中，复杂的冲突网常常比最大团“更难缠”——这正是图着色 NP 难本质的一角。不过别慌，接下来的贪心和回溯算法，就是人类对付这种“难缠”的常规武器。

贪心着色算法：先到先得的教务主任

真到了排课现场，没人会去搜索天文数字般的方案。教务主任的惯用策略是“先到先得”：拿着一张课程清单，按顺序处理每门课，给它安排一个“当前不与任何已排课冲突的最小时间段编号”。这像自助餐厅给客人排座位——新来的客人只要避开所有已经落座的朋友，找一个最靠前的空桌坐下。

这个策略就是贪心着色（Greedy Coloring）。它不回头、不算总账，只看眼前：每一步都选择“局部最舒服”的颜色。它的优点是极快——O(V+E) 就能给整个图着完色。代价是：结果严重依赖顶点顺序。同一个图，若先排“与很多人冲突的关键课”，可能只用 3 色；若先排边缘小课，后面可能被迫用出 4 色甚至更多。它给你一个承诺：无论顺序多差，所用颜色数都不会超过“最大冲突数 + 1”。

$$\displaystyle \text{贪心着色颜色数} \le \Delta(G) + 1$$

1. 最大度数 Δ(G)：度数最大的顶点有多少个邻居，即“和同一门课冲突的课程最多有几门”。

$$\displaystyle \Delta(G) = \max_{v \in V} \deg(v)$$

2. 上界 Δ+1：处理任意顶点 v 时，它最多有 Δ 个冲突邻居，这些邻居最多占用 Δ 种颜色；哪怕这些颜色全被占满，编号从 0 开始计数时，Δ 个邻居最多堵住 0 到 Δ-1 这 Δ 个编号，编号 Δ 一定仍然可用。

$$\displaystyle \chi(G) \le \Delta(G) + 1$$

3. 顺带结论：更精细的 Brooks 定理指出，除了完全图和奇数环，χ(G) ≤ Δ(G)。但贪心算法的意义从来不是理论最优，而是“快速给出一个不坏的可落地方案”。

实践中有个立竿见影的改进——威尔士-鲍威尔方法（Welsh-Powell）：先把顶点按度数从大到小排序，再执行贪心。这相当于聪明的教务主任总是优先处理“人缘最广、冲突最多”的硬骨头课，把它们用大编号时间段占住，再让小学科见缝插针。段考挂科率最低的课表，往往就是这么排出来的。贪心是“快刀”，配上好的顺序，就能在舒适与效率之间找到平衡点。

回溯搜索算法：迷宫中回头重走

贪心经常交出“不错”的答卷，但你要是较真：能不能保证用 3 个时间段排完？答案只能交给精确算法。想象你走进一座迷宫，前面有三条岔路，你选了第一条，走到底发现是死路——于是退回岔口，换第二条。如果三条都堵死，就再退回上一个更大的岔口。这种“走不通就回头”的策略，就是回溯（Backtracking）搜索。

在着色问题里，回溯的递归过程是：按某个顺序处理顶点，尝试给它分配颜色 1、颜色 2、……最多颜色 k。每分配一个颜色，都检查是否与已着色邻居冲突；若三种颜色都试遍仍无解，说明前面某一步选错了，撤销当前顶点的颜色，回到上一层换一种颜色。只要有一个分支顺利走到所有顶点都着色完毕，就说明图是 k-可着色的。

$$\displaystyle \text{available}(v) = \{1,2,\dots,k\} \setminus \{c(u) \mid u \in N(v),\, u \text{ 已着色}\}$$

1. available(v)：当前顶点 v 还“敢用”的颜色集合。只有这个集合里的颜色才能安全分配。

$$\displaystyle \text{available}(v)$$

2. 颜色池 {1,……,k}：在尝试 k-着色时，全色板只有 k 种，这是搜索的边界。

$$\displaystyle \{1,2,\dots,k\}$$

3. 减掉邻居已用色：所有已着色邻居 u 的颜色都必须排除。若某个邻居用了颜色 2，你就不能再用 2。

$$\displaystyle \{c(u) \mid u \in N(v),\, u \text{ 已着色}\}$$

4. 剪枝条件：如果 available(v) 是空集，说明当前方案已经无路可走——不必再向下搜索，直接回退。这就是剪枝（Pruning）：把整棵死子树一次性扔掉。

$$\displaystyle \text{available}(v) = \emptyset \Rightarrow \text{回溯}$$

回溯最坏是指数级——这就是 NP 难的代价，但配上三个绝招，现实中它快到惊人：第一是剪枝，无路可走立即回头；第二是 MRV 启发式（Minimum Remaining Values），每次优先给“可选颜色最少”的顶点着色，让冲突尽早暴露；第三是前向检查，每步即时更新邻居的可用色集合。数独求解器、考试排期这类问题，回溯在毫秒到秒级就能交出最优答案。贪心是“先到先得的急性子”，回溯是“不撞南墙不回头、撞了南墙就换墙的倔强老黄牛”——它慢，但它给你担保。

四色定理：地图染色的世纪难题

回到开篇的地图。如果你把地图上的每个国家看作一个顶点、相邻国之间连一条边，就得到一个非常特殊的图——平面图：所有边都可以画在纸上而互不相交。一个流传百年的直觉是：给地图染色，让相邻国家不同色，4 种颜色永远足够。这便是四色定理（Four Color Theorem）的朴素表述。它像排课世界里的一个魔咒：只要冲突图是“平铺”的，四个时间段包打天下。

但这条定理证明了整整 124 年。1852 年，数学家 De Morgan 收到学生 Guthrie 的提问后，这个猜想迅速风靡欧洲。1890 年 Heawood 证明“五色定理”——平面图 5 色必够。四色却始终差一步：所有人类能想到的证明方法都在 4 这个数字前碰壁。直到 1976 年，Appel 与 Haken 用计算机检查了约 1500 个“不可避免的可约构形”，宣布证明完成——这是数学史上第一个离不开计算机的著名证明。2005 年，Gonthier 用 Coq 交互式证明器给出了形式化验证，四色定理终于无可争议。

$$\displaystyle \chi(G) \le 4, \quad \forall\, G \text{ 为平面图}$$

1. 平面图限制：定理的适用范围是平面图——边能在平面上无交叉绘制的图。地图的邻接结构天然是平面图。

$$\displaystyle G \text{ 是平面图}$$

2. 上界 4：任何平面图的色数至多为 4。注意是“至多”，不是“恰好”。

$$\displaystyle \chi(G) \le 4$$

3. 反例警示：四色定理不适用于一般图。五个顶点两两相连的完全图 K₅ 需要 5 色，但它画在平面上必出现交叉边，所以不是平面图。

$$\displaystyle \chi(K_5) = 5$$

四色定理教会我们一个比“四色”本身更值钱的道理：结构限制能带来颜色数的硬上界。你的冲突图若是平面的，就可以放心承诺 4 个时间段；若杂乱无章（含 K₅ 之类的子结构），再聪明的算法也不敢许诺 4 色。做算法的人拿到问题第一件事，就是判断“我的图属于哪一类”——这决定了你能押多大的注。

实际应用：从课表到芯片再到数独

掌握了“冲突画边、颜色分配”这套思维，你会发现整个世界都在排课。CPU 寄存器要把临时变量装进有限的小格子，数独要把 1-9 填进 81 个格子……它们只是换了个名字的图着色。先看任务调度：期末考试有 200 门科目，同一个学生可能同时报考多门，同一考场不能同时安排两场科目——把科目作顶点、冲突作边，时间段的分配就是着色。再看更硬核的寄存器分配：编译器生成的中间代码里，两个变量若在同一时刻都处于活跃状态（干涉图里连边），就不能共享同一个寄存器；Chaitin 提出的图着色寄存器分配算法，用“染色”把变量塞进尽量少的寄存器，是现代编译器后端的基石技术。

最后看一个你几乎天天接触的例子：数独！数独有 81 个格子，同一行、同一列、同一个 3×3 宫内的任意两格不能填同一个数字——把每格看作顶点、冲突关系看作边，谜题里已给的数字就是预先染好的颜色，你要用 9 种颜色给整张图补完合法着色。暴力枚举 9 的 81 次方种方案是天文数字，但回溯配合 MRV（每次填可选数字最少的格子）能在 0.1 秒级别求解。这类约束满足问题（CSP）正是 AI 推理中的重要分支。

$$\displaystyle \chi(G_{\text{sudoku}}) \le 9$$

1. 数独冲突图 G_sudoku：81 个顶点代表 81 个格子，同一行、同一列、同一宫内的任意两个格子之间连边。

$$\displaystyle V = \{ \text{81 个格子} \}$$

2. 连边规则：同行、同列、同宫两两连边——这三类“不能相等”的约束，统一变成“必须异色”的边。

$$\displaystyle E = \{(i,j) \mid i,j \text{ 同行或同列或同宫}\}$$

3. 上界 9：9 种颜色（数字 1-9）可以覆盖全部 81 格的需求。给定数字就是强制预着色，求解过程就是 9-着色的回溯搜索。

$$\displaystyle \chi(G_{\text{sudoku}}) = 9$$

从教务课桌上的课程卡片，到编译器里的寄存器，再到手机里的数独游戏，这张“冲突网”织遍了计算机世界的每一个角落。图着色的魅力正在于此：它不针对任何具体业务，却把一切“两两不能共存”的关系，统一成了同一种算法语言。你学会的，不只是排课表，而是一种翻译现实约束的本领。

AI 应用场景

Python 演示

def greedy_coloring(vertices, neighbors):    # 贪心着色: 按给定顺序逐顶点选最小可用颜色    color = {}    for v in vertices:        used = {color[u] for u in neighbors[v] if u in color}        c = 0        while c in used:            c += 1        color[v] = c    return color def backtrack_coloring(vertices, neighbors, k):    # 回溯精确着色: 尝试用 k 种颜色完成合法着色    color = {}    order = sorted(vertices, key=lambda x: -len(neighbors[x]))    def dfs(i):        if i == len(order):            return True        v = order[i]        used = {color[u] for u in neighbors[v] if u in color}        for c in range(k):            if c not in used:                color[v] = c                if dfs(i + 1):                    return True                del color[v]        return False    if dfs(0):        return color    return None # 示例图: 两个三角形通过边 (1,4) 相连V = [0, 1, 2, 3, 4, 5]E = [(0, 1), (1, 2), (0, 2), (3, 4), (4, 5), (3, 5), (1, 4)]nb = {v: [] for v in V}for a, b in E:    nb[a].append(b)    nb[b].append(a) g = greedy_coloring(V, nb)print("贪心着色:", g, "颜色数 =", max(g.values()) + 1)for k in range(1, 5):    r = backtrack_coloring(V, nb, k)    if r is not None:        print("回溯能找到", k, "色方案:", r)        break

1. used = {color[u] for u in neighbors[v] if u in color}一行集合推导式算出“邻居已占用的颜色”，这是贪心和回溯共用的核心检查逻辑。
2. while c in used: c += 1从 0 号颜色开始递增，找到第一个没被邻居占用的颜色编号，即“最小可用颜色”。
3. order = sorted(vertices, key=lambda x: -len(neighbors[x]))按冲突边数从多到少排序，相当于威尔士-鲍威尔启发式，让“硬骨头”课先着色。
4. for c in range(k): if c not in used:回溯时依次尝试 k 种颜色，只试没有被邻居占用的颜色。
5. del color[v]当前顶点试遍 k 色仍失败时删除它的颜色，撤销这一层选择，退回上一层重试——这就是回溯的“回头”。
6. max(g.values()) + 1颜色从 0 开始编号，所以最大编号加 1 才是真实使用的颜色种数。

常见误区

面试题