图着色：冲突调解与四色悬念

图着色：冲突调解与四色悬念

「chromatic number」，色数——给图的每个顶点涂上颜色，让任何相邻的顶点颜色不同，所需的最少颜色数就是色数。这个定义简单得像幼儿园的涂色游戏，却挂着一桩悬置了一个多世纪的悬案，也催生了理论计算机科学里最重要的分水岭之一。收尾攻坚的第一仗由它打响：本节建立着色的形式框架，手算经典图类的色数，实现贪心与回溯两档求解器，最后重走四色定理的世纪之路——那里有数学史上第一份无法用纸笔复核的证明。

问题与经典图类的色数

形式化：图 G 的一个正常着色是映射，把颜色分配给顶点，使每条边的两端异色；色数记为所需最少的颜色数。实务翻译面极广——考试排期（同场考试不可同时进行，冲突学生共享顶点边）、寄存器分配（同时活跃的变量不可共寄存器）、频谱分配（相邻基站不可同频）、班级排课（教师与班级的冲突图）。

经典图类的色数可以手算到脱口而出：完全图的色数等于顶点数（人人相邻，个个异色）；二分图的色数恰为二（非空时两阵营各一色，第 1 章的奇环判定在此转世为"色数为二当且仅当无奇环"）；奇圈的色数为三、偶圈为二；树的色数为二（非平凡时）。有一条即时可用的下界：色数不小于最大团的规模（团内人人相邻），也不小于平均度加一的最大者——前者是结构的下界，后者是计数的下界，两把尺子常一起用。

着色与独立集的血缘一眼可见：每种颜色内部的所有顶点构成一个独立集（同色者必不可相邻），着色因此等价于"把顶点集切成数目最少的独立集"——下一节的主角在这里提前露脸。

两档求解器：贪心与回溯

贪心着色按某个次序逐个顶点涂色，每个顶点取"邻居未占用的最小色号"。它永远给出正常着色（正确性平凡），颜色数却随次序漂移：存在次序使贪心恰好达到色数（取一张最优着色，按颜色分层排列即是），也存在次序让它用掉"最大度加一"种颜色。于是得到经典的双侧界：色数夹在"最大团规模"与"最大度加一"之间。实务里没有免费的精确解时，贪心配一个好次序（如按度数降序、或动态取"未着色顶点中邻居最多者"）是标准打法。

import networkx as nx

def greedy_color(G, order):
    """贪心着色：返回 顶点->色号 与用色数"""
    color = {}
    for u in order:
        used = {color[v] for v in G[u] if v in color}
        c = 0
        while c in used:
            c += 1                       # 取最小的可用色
        color[u] = c
    return color, max(color.values()) + 1

C = nx.Graph([("甲","乙"),("乙","丙"),("丙","丁"),("丁","甲"),
              ("甲","丙"),("乙","丁")])       # 完全图：人人相邻
print("完全图贪心:", greedy_color(C, list(C.nodes)))

T = nx.Graph([("甲","乙"),("甲","丙"),("甲","丁"),("丙","戊"),("丁","己")])
print("树·好次序:", greedy_color(T, ["甲","乙","丙","丁","戊","己"]))
print("树·坏次序:", greedy_color(T, ["戊","己","丙","丁","乙","甲"]))
print("nx 官方贪心:", nx.greedy_color(T))
​

回溯精确求解在贪心之上加"最优性追求"：逐顶点试色，维持当前最优的颜色数上界，试色时只允许用到"上界减一"以内的色号（否则不可能更优），失败就回退。配上"出现同色冲突立即剪枝"的检查，中小规模实例（数十顶点）在可接受时间内能拿到精确色数：

def exact_coloring(G):
    """回溯求精确色数（中小规模适用）"""
    nodes = list(G.nodes)
    best = [len(nodes)]                  # 上界：一顶点一色必然可行
    def backtrack(i, color):
        if i == len(nodes):
            best[0] = min(best[0], max(color.values()) + 1)
            return
        u = nodes[i]
        for c in range(best[0]):         # 只试能超越当前上界的色号
            if all(color.get(v, -1) != c for v in G[u]):
                color[u] = c
                backtrack(i + 1, color)
                del color[u]
    backtrack(0, {})
    return best[0]

print("精确色数:", exact_coloring(C))
print("团下界:", nx.graph_clique_number(C))
​

输出的精确色数与团下界咬合（完全图上两者相等）——下界顶住、上界压下，两侧夹出答案，这是求解极值问题的通用姿势。

难度的分水岭

上一段回溯代码为何不能一路放大到万顶点？因为着色的判定版（"能否用不超过 k 种颜色着完"）在最一般的情况下属于难度层级最高的一族：多项式时间内既无人解出，也无人证明无解；绝大多数研究者相信它本质上需要指数时间，全部相关信念凝聚在一个悬赏的千年级难题之下。与前面各章对比顿觉泾渭分明：最短路、最大流、匹配、生成树全是"输入多项式倍时间可解"，着色与下一节的独立集却在"最少"二字上撞墙。这不是算法学家不够聪明，而是问题之间存在深刻的相互锁死——若任何一个被快速破解，一族同样形态的问题将同时崩解。工程上的应对分三路：贪心与局部搜索求"够用的着色"；回溯加剪枝吃中小实例；把问题转写成整数规划交给工业求解器。第 10 章工程检阅会看到第一条路线的真实生产线。

四色定理的世纪之路

地图着色的原题朴素至极：给平面地图的相邻区域涂不同色，最少要几色？四色猜想断言四色足矣，它的证明之路走了整整一个多世纪：早期几次"证明"相继被发现漏洞，其中一次的漏洞在被戳穿前已被当成定论近十年；转机来自对构形集合的穷举——把所有可能的"局部反例形状"归约为有限多个构形，再逐一验证每个构形都不可避免地出现在任何平面图里、且都能被四色消化。构形数以千计，人工验证不现实，两位数学家在计算机上跑出了完整验证，宣告定理成立。这在数学史上是第一份"机器不可替代"的证明：纸笔无法复核全部计算，数学共同体只能转而审查程序与构形生成逻辑。争议随之而来——"计算机辅助的证明算不算证明"至今仍是数学哲学的活跃辩题；后来的形式化验证项目把整条证明翻译进证明助手、逐行机器核对，为这场争论补上了现代注脚。顺带一提，"五色定理"（平面图五色必够）有一页纸的优雅证明，纸笔可完成——四与五之间的那一格，正是机器介入数学的门槛所在。

⚠️ 常见坑：拿"最大度加一"当色数的精确值。它只是上界——多数图的色数远小于此（星形图度数中心极高、色数却只是二）；也别拿贪心输出当最优，次序敏感性意味着换一次排序可能立刻更省。

💡 关键直觉：着色是"冲突的打包"——每种颜色是一个互不冲突的班次，色数是最少班次数。看到"不可同时发生"的约束，就应闻到着色问题的气味。

颜色的攻坚暂告段落。下一节把镜头从"分组"切到"选点"：独立集与顶点覆盖，哨所选址的权衡术。