最近翻旧笔记时看到几个热搜词叠在一起时光回溯网站、稳定工作4年-微信公众号爬虫-历史数据回溯-含项目报告.zip、拓扑排序、开关电源拓扑。前两个说的是数据爬虫里的历史取数后几个又跳到另一种拓扑。我在这些词里反复横跳时脑子里始终绕着一个老问题四色定理。这个问题的完整表述很短——任何一张平面地图最多用四种颜色就能让相邻区域颜色不同。它从被提出到真正被证明走了124年从第一个被广泛接受的证明到发现漏洞又隔了11年。而现代证明中最关键的思路恰好可以把拓扑和场这两个看似物理感极强的词结合到一块。这篇文章想顺着回溯这条线把四色定理的证明骨架、算法实现和踩坑点完整捋一遍顺便解释为什么说它是从一点撬动整个宇宙。1. 回溯起点四色问题为什么能钻进所有拓扑词条1.1 一句话定理与124年证明史四色定理的内容本身好懂到像儿童涂色题给一张平面地图染色让任意两个有公共边界的区域都不同色四种颜色永远足够。真正让人上瘾的是它的证明史。1852年Francis Guthrie 在给弟弟的信里提出这个问题1879年律师兼数学家 Kempe 发表了一个看起来天衣无缝的证明1890年Heawood 发现这个证明里藏着一个致命的逻辑漏洞。从被证明到被推翻中间隔了11年很多教材已经把它当成定理在写。后面的事更颠覆认知。1976年Appel 和 Haken 用计算机辅助完成了四色定理的证明这也是数学史上第一个无法靠人工逐行检查的主要定理。他们构造了一个包含近两千个可约构形的不可避免集合用程序逐个验证。后来 Robertson、Sanders、Seymour、Thomas 在1997年把构形数量压缩到633个2005年 Gonthier 又用 Coq 完成了形式化验证算是把逻辑链条彻底焊死了。时间事件意义1852Guthrie 提出猜想问题诞生流传于世1879Kempe 发表证明被学术界接受了近11年1890Heawood 指出漏洞证明失效但留下五色定理和环面七色结论1976Appel Haken 计算机辅助证明第一个靠程序证明的大定理争议巨大1997Robertson 等人简化证明构形数量降到633个结构更清晰2005Gonthier 用 Coq 形式化验证逻辑被机器逐步检查争议彻底进入新阶段1.2 为什么它和回溯绑得这么紧我理解回溯在四色定理里有两层意思。第一层是历史回溯从一个看似成立的证明开始往回找反例往回找漏洞。Heawood 做的事本质上就是回溯——你把 Kempe 的每一步拆开试图在某一步找到一个可以让理由失效的结构。这种回溯是数学里最常见也最折磨人的活动。第二层是算法回溯你写一个程序去给平面图染四种颜色最自然的做法就是深度优先搜索加回退。这个点染红下一个不行就换蓝实在不行退回上一个点重新试。四色定理的现代证明里计算机做的大量工作也是类似的穷举式回溯只不过它回溯的是构形是否可约而不是单个顶点的颜色。数据圈说的历史数据回溯是爬虫去捞旧网页算法圈说的回溯是搜索状态树数学圈的回溯则是从结论往回找反例。三个语境看似不搭边但底层逻辑一致先往前走发现走不通就回到某个记录过的岔路口换一条路。四色定理刚好把三种回溯都占全了。2. 拓扑视角把地图揉成图把图放回球面2.1 地图对偶国家变成点接壤变成边四色定理在数学里通常不讲地图讲图论。做法是对偶变换把每个国家看成一个顶点两个国家有公共边界就对应一条边。这样一张地图染色就变成了平面图的顶点染色相邻顶点不能同色。这个变换为什么重要因为它把区域形状千变万化的几何问题变成了连接关系固定的组合问题。一个国家是圆形还是锯齿形在拓扑上完全不重要重要的是它和谁相邻。就像你搜拓扑时看到的 Blender 硬表面建模全四边面拓扑建模关注的是网格节点如何被边连接而不是顶点在空间里的精确坐标。平面图的对偶图不一定是简单图可能出现多重边甚至自环。多重边不影响染色因为两个顶点之间有一条边就足以要求不同色自环在严格意义上是无法染色的但正常地图对偶不会产生自环。实际写程序时要先做数据清洗把这类边界情况处理掉。2.2 欧拉公式是真正撬动宇宙的那根杠杆整个四色定理证明史诗里我最想敲黑板的是这个式子V - E F 2对任意连通的平面图顶点数减边数加面数恒等于2。它太平静了看起来像废话但它是拓扑不变量这个概念最早的化身之一。你可以在平面上把一个图形揉来揉去只要不撕开不粘连这个数就永远不变。从欧拉公式能推出一个重要结论对没有多重边的连通平面图E ≤ 3V - 6。推导过程很简单每个面至少由3条边围成所以2E ≥ 3F再代入欧拉公式整理就得到这个不等式。然后平均度数 d_bar 2E / V ≤ 6 - 12 / V 6。也就是说任何一个足够大的平面图一定存在一个度数不超过5的顶点。这个薄弱点就是整个证明的支点。你想证明四色定理不需要同时处理所有顶点只需要反复利用图里一定有一个低度顶点这个事实。你可以把这个顶点单独拿出来先给剩下的图染色再想办法把它的颜色补上如果补不上就做局部调整。四色定理所有的归纳、放电、构形分析都是从这一根杠杆开始的。2.3 不只是平面环面为什么需要7种颜色拓扑视角最有意思的副产品是发现了色数取决于曲面形状。四色定理只在平面或球面上成立。如果你把地图画在轮胎面形状的环面上结论完全不同最多需要7种颜色而且真的存在必须用7种颜色的地图。Heawood 在1890年那篇指出 Kempe 漏洞的文章里顺便证明了更一般的曲面着色上界公式对环面算出来是7。这件事给了我们一个很重要的直觉四色定理根本不是颜色的规律而是平面的拓扑规律。平面上绕一圈必然回到原点且边界不缠在一起这个事实通过欧拉公式传导到了染色问题上。所以你看到的那些不同领域的热搜词拓扑排序、菊花链(fly-by)拓扑、开关电源拓扑、LLC/反激/全桥拓扑它们共享的其实是同一个思考方式连接关系比尺寸形状更本质。四色定理是这个思维方式在纯数学里最强硬的一次体现。3. 场论思路当四色定理被变成一场电荷回流3.1 拓扑-场论证明这个提法是怎么回事严格来说主流数学文献里不会把四色定理的现代证明叫做场论证明它更常被称为组合证明特别是 discharging method放电法。但在理解和传播时我觉得场这个框架非常顺给图上每个点分配一个初始量再让这个量按照局部规则在边上流动最后用总守恒量制造矛盾。这和物理里的场论只差一个形象解释电磁场里电荷是源场的散度等于电荷密度在四色证明里度数不足的顶点就是负电荷中心度数超标的顶点是正电荷中心放电规则就是让电荷沿边流动。你可以把它理解成离散曲率场正曲率顶点向负曲率顶点输送弯曲量最后所有顶点都达到一个不可能完全平衡的状态。这个类比不是要发明新的物理而是帮助建立直觉。真正严谨的链条由欧拉公式、放电规则、可约构形和计算机枚举组成全部是离散数学。3.2 三角剖分、欧拉亏欠与初始电荷为了用场论思路第一步是把平面图变成三角剖分在不改变染色性质的前提下加边直到每个面都是三角形。为什么可以加边因为你加边只是给图增加约束如果加边后的图还能用四色染出来原来的图当然也能。三角剖分之后欧拉公式会给出两个酷炫的数字F 2V - 4E 3V - 6。这来自于每个面三条边以及每条边被两个面共用。现在给每个顶点定义初始电荷charge(v) deg(v) - 6所有顶点的总电荷是sum(charge) 2E - 6V 2(3V - 6) - 6V -12总电荷是负数 -12这非常关键。它意味着一个三角剖分的平面图整体上处于亏欠状态不可能每个顶点都电荷非负。你顺着这个思路想如果存在一个真正需要五种颜色的极小反例图那么每个度数小于6的顶点都会变成麻烦制造者因为它们周围邻居太多、颜色不够用。放电法会设计一系列规则把正电荷从高degree顶点往低degree顶点送目标是经过多轮流动后让每个顶点都出现一个不可约的局部结构但与此同时总电荷是-12不可能让所有顶点都变成非负。这个矛盾逼出了结论极小反例不存在四色定理成立。3.3 可约构形Kempe链、放电规则和不可避免集合到这里必须解释两个术语否则后面没法聊。第一个是 Kempe 链。Kempe 当年的思路是假设一个极小反例里有度数不超过5的顶点v去掉v后剩余图可以用四色染好。如果v的邻居只用了三种颜色那就直接把第四种颜色给v。麻烦的是邻居恰好占满四种颜色。Kempe 的补救办法是选两种颜色只看它们在图中形成的连通分量把整个分量的颜色互换这样可能腾出一个空位。这个双色连通分量就是 Kempe 链。第二个是可约构形。一个局部子图如果能被证明不可能出现在任何极小反例里就说它可约。Kempe 链颜色交换是证明可约最基本的手段但问题在于当v有5个邻居时你可能需要做两次颜色交换第二次交换拿到的链会被第一次交换后的结构阻断于是颜色又变回去了。Heawood 找到的正是这种两条 Kempe 链互相拦路的坏情况。Kempe 链不够用后面的数学家就把思路拉远与其找一种通用局部调整不如列出一大堆局部结构逐个证明它们可约只要证明每个平面三角剖分必包含其中某一个结构也就是给出不可避免集合整个证明就完成。Appel 和 Haken 就是用程序枚举了近两千个构形再把它们塞进放电规则里最终拼出了那个不可避免集合。放电规则就是这场场的动力学正电荷从高degree顶点输向低degree顶点路径可以跨多个顶点每条规则都像粒子物理里的相互作用项。有的规则把2个单位电荷从7度顶点送到相邻的5度顶点有的规则要求在某个特定环状结构上做多步输送。规则不同最终能覆盖的构形也不同。可以说四色定理的现代证明就是一场精心设计、由计算机协助搜索出来的离散电荷回流。4. 回溯算法实践写一个四色染色器4.1 核心框架DFS加颜色回退如果你只是想要一个能用的四色染色程序不需要真的去复现放电法和633个构形。四色定理告诉你解一定存在接下来用回溯法可以稳定找到它。基本框架很简单按顺序处理顶点当前顶点尝试每一种颜色检查是否和已染色的邻居冲突如果没有冲突就染上去然后递归如果后续所有分支都失败就回退并把当前顶点重新置为未染色。def colorize(graph, k4): n len(graph) color [-1] * n def can_dye(v, c): for u in graph[v]: if color[u] c: return False return True def dfs(v): if v n: return color[:] for c in range(k): if can_dye(v, c): color[v] c res dfs(v 1) if res is not None: return res color[v] -1 return None return dfs(0)这段代码是按顶点下标0到n-1顺序处理的。平面图规模不大时足够用我也想强调一个心理预期四色定理保证能找到方案但它不保证朴素回溯跑得快。遇到几百个顶点的图顺序选得差回溯树可以膨胀到完全没法看。4.2 顺序和剪枝真正决定性能的是先染谁优化四色回溯最有效的不是写更复杂的剪枝而是改变顶点的处理顺序。我的经验是三条规则可以叠加使用第一优先染度数最高的顶点。度数高的顶点约束最强旁边坐着一堆邻居颜色选择天然最少。先处理它能尽早让后续搜索的冲突爆发出来避免在容易染的顶点上浪费层数。第二使用最少剩余值启发式MRV。每一步都挑当前可选颜色数量最少的未染色顶点去处理。这个思路和数独求解一样先攻最难的把硬骨头啃掉剩下的路径自然就少了。第三DSATUR 规则每次选与已染色顶点相邻数量最多、且当前可用颜色最少的顶点。DSATUR 是图着色问题里性价比极高的启发式很多标准测试图上跑出来的效果接近最优解。我自己在实测里踩过一个很明显的数据点同样一个80个顶点的平面图按下标顺序回溯跑了一分钟没出结果换成 DSATUR 顺序几十毫秒就出了四色方案。差距不是倍速级别是数量级级别。换句话说不要怀疑为什么大家都推荐启发式这个提升在实操里非常真实。4.3 别把回溯和拓扑排序混在一起这里想说清一个困扰很多人的点热搜里同时出现拓扑排序、菊花链fly-by拓扑、开关电源拓扑、Blender硬表面建模拓扑、scikit-learn拓扑优化它们都和四色定理里的拓扑不完全是一码事。名词领域实际在做什么拓扑排序图论/工程给有向无环图的任务排一个合法先后顺序菊花链fly-by拓扑硬件设计点对点串联的信号连接方式开关电源拓扑电力电子描述开关管、电感、电容组成的变换器结构Blender四边面拓扑三维建模把网格尽量建成四边面便于细分和形变四色定理的拓扑纯数学研究平面/曲面在连续变形下保持不变的性质它们共享的思想是忽略具体尺寸和形状只关注连接方式但应用模型完全独立。四色染色器里用的回溯和无向图的颜色约束和拓扑排序里有向无环图、入度为0优先是两个不同算法。如果你在写代码时把它们混在一起大概率会得到错误结果。我的建议是遇到拓扑两个字先分清楚语境再看是数学还是工程问题。5. 常见误区与实操排查5.1 Kempe证明的漏洞到底长什么样很多介绍四色定理历史的资料说 Kempe 证明有漏洞却没说明白漏洞在哪。我尝试用文字描述一次不需要画图也能理解。在度数为5的顶点v这里去掉v后保留四色染色五个邻居占了四种颜色于是有一对邻居必须同色。Kempe 想通过换色腾出一个空位。问题出在需要做两次独立的 Kempe 链交换第一次交换会改变图中若干顶点的颜色第二次交换要依赖的链可能在路径上被第一次交换后的颜色结构切断。最终结果是想保留的腾位操作被另一个腾位操作破坏v还是找不到一个可用颜色。为什么同样方法能证明五色定理因为在一个度数为5的顶点上Kempe 链的冲突恰好只在需要从四色里给第五个邻居找空位时出现五色证明只需要保证五个邻居被五色处理不需要做那步危险的二次交换。可见少一个邻居造成了完全不同的拓扑局面。5.2 计算机证明可信吗这也是新读者最容易问的问题。1976年的 Appel-Haken 证明用了约1200小时机时近两千个构形需要计算机逐个检查当时很多数学家不接受罪名是无法被人工完整验证。后来构形数降到633个2005年 Gonthier 用 Coq 把整个证明转化成机器可读、每步可验证的形式化证明这种凭计算机算出来的质疑才逐渐被消解。不过要提醒的是即便到了今天数学家们对它仍有一种审美上的遗憾四色定理缺少一个足够优美、短到能写进黑板证明的人工证明。它不是一个伪问题而是证明可以很短吗的开放审美问题。作为应用你完全可以把四色定理当成一个已经被严格验证的数学事实放心用来染色和做算法验证。5.3 我自己踩过的三个坑第一平面图判定不能省。四色定理只适用于平面图或球面图。K5五个顶点两两相连的完全图不是平面图色数就是5你用四色算法跑它当然无解。在程序里先检查欧拉公式 V - E F 2 和边的平面性条件可以避免很多误判。很多公开数据集里所谓平面图并不是规范的三角剖分直接套染色算法会多出大量无效分支。第二对偶图里的多重边不能当成多个独立邻居来计数。地图上两个国家可能有多个相邻路口对应到对偶图就是两个顶点之间有多条平行边。对染色而言平行边数量不影响逻辑只保留是否相邻这个布尔关系即可。我在处理飞地、边界复杂的真实地图时栽过一次错误地给两个顶点加了3条边程序认为它们是三个约束实际染色结果还碰巧能解但性能白白变差。第三回溯前先做顶点顺序优化。这不是可选项是必选项。我不会再强调一次它有多重要。如果你发现染色程序卡死第一件事不是加剪枝条件而是打印当前顶点顺序和每个顶点的可选颜色数看看是不是一直在纠结一个明显该先处理的点。这个习惯帮我省过很多小时。6. 一点个人体会我现在回看四色定理最震撼的依然是那个起点欧拉公式。它没有告诉你哪些构形可约也没有告诉你放电规则应该怎么设计但它给出了一个不可能绕开的总量。所谓回溯就是从这个总量出发一步一步往回推推到某个局部结构必须出现再证明那个局部结构无法存在。整个宇宙当然不会被一个定理撬动但这个式子的确撬动了一整座数学大厦。如果你也想复现这套思路我最推荐做的事不是去翻原版证明而是先写一个四色染色器再写一个放电规则的最小演示比如给一个小三角剖分定义 charge(v)deg(v)-6打印每个顶点在规则流动前后的电荷变化。这一步能让你直观看到总电荷为负如何在离散图上被消散掉。我每次做这种小实验都会对拓扑和离散场的理解深一层。最后再分享一个小技巧调试放电规则时一定要把每一步的电荷分布可视化出来。错误规则的第一症状往往不是最终矛盾失败而是某个中间步骤的顶点电荷出现异常高或异常低的值。看到那种数值基本可以断定规则里漏了某条邻接路径。先把数据画出来再回头改规则比对着几百行的枚举结果猜快得多。
