
丹麦与DTU学者找到四色问题的有效算法
来源标题:Danish researchers find efficient solution to the four colour problem
哥本哈根大学和丹麦技术大学的两位教授与多国合作者找到了四色问题的有效着色算法,结束了长达十年的研究。四色问题源自1852年,人们自1976年起已知任何地图最多四色即可着色,但如何实际找出着色方案此前并未解决。该成果带来了新的基础数学洞察。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
2026年11月17日 11:50:37 CET | 哥本哈根大学 | 新闻稿
任何地图都能只用四种颜色着色吗?这是数学中最著名的问题之一背后的疑问,可追溯至1852年。自1976年以来,我们已经知道答案是“肯定的”——但究竟如何找到这种着色方案呢?如今,哥本哈根大学和DTU的两位教授与国际同行一起,在经过长达十年的“痴迷”后,找到了最优算法。这一答案提供了新的基础性数学洞见。
174年来,世界各地的数学家一直在与四色问题较劲:任何地图真的总能只用不超过四种颜色着色,使得相邻区域不共享同一种颜色吗?
1852年,英国数学家Francis Guthrie在绘制英格兰各郡地图时注意到自己只需要四种颜色,于是猜测这是可行的。然而,挑战在于证明他的猜想无论地图是什么样子都始终成立。这就是此后一直困扰全世界数学家的著名的四色问题。
第一个证明于1879年提出,维持了11年才发现其中存在错误。完整的证明最终于1976年被找到,至此我们有了四色定理,但该证明颇具争议,因为它严重依赖计算机计算,其他数学家难以验证。1997年,一个更易理解的新证明被提出。它也能找到四色着色方案,但在应用于大地图时算法上很慢。
如今,一个包括两位丹麦教授在内的国际数学家团队取得了30年来的首个重大突破:他们找到了能高效地为任何地图进行四色着色的最优算法。
“此前的证明表明,用四种颜色为地图着色总是可能的。但它们在真正为地图上每个区域找到具体颜色方面并不擅长。新算法是高效的,提供了一种快得多的着色方式,”哥本哈根大学计算机科学系教授Mikkel Thorup说,他是这项研究背后的研究者之一。
关于这项研究的第一篇论文刚刚在理论计算机科学领域世界领先的会议FOCS'26上展示,并获得了最佳论文奖。
Mikkel Thorup和他的研究同事,包括Carsten Thomassen、Ken-ichi Kawarabayashi和Bojan Mohar,在四色问题上已经研究了大约十年。Thorup称之为“四色病”:
“这种病就是相信如此简单的陈述必定存在简单的证明。我猜至少有1000名数学家染上了四色病,花费数月试图让它成立,却从未真正成功。这是人们自1852年以来一直患有的病。”
但你可能会想,为什么会有人花数年时间研究这种东西呢?
“因为数学家有点疯狂。数学家研究的大部分内容都是非常书呆子气的问题。我们痴迷于这类问题,因为它挑战人类的智力。而如果我们找到了答案,我们很可能也会找到其他数学谜题的答案,”Mikkel Thorup说。
新算法比此前的算法高效得多的原因在于,它基于研究团队发现的一种全新的数学洞见。
用数学语言来说,地图这样的表面被称为平面图。研究人员发现,图中包含的可约构型远多于此前所认为的。这些是图的小片段,为数学家提供了着手计算着色方案的起点。
“把可约构型想象成你可以抓住的把手,用来开始四色着色。我们证明图中不止包含一个把手,而是数量惊人地多。此前没有人知道这一点,”来自DTU的教授、共同作者Carsten Thomassen说。
由于研究人员现在可以在图的许多地方找到“把手”,而此前他们往往只能找到一个,他们可以从许多不同的位置开始着色过程,因此能更快地为甚至非常大的地图着色。
“我们从数学家所称的二次时间变成了线性时间。这意味着,如果地图包含的区域数量增加十倍,计算只会变慢大约十倍。而用之前的算法,则会变慢大约100倍,”Carsten Thomassen解释道。
借助这一新突破,研究人员所做的不仅仅是找到了一种更快的着色方法。他们对图结构的新洞见超越了经典的四色问题,为研究远为复杂的图和表面类型开辟了新的可能性。
“引人注目的是,由于有如此多的把手,这一想法还可以应用于平坦地图之外的其他类型的表面。例如,带有孔洞的表面,比如游泳圈或一块埃门塔尔奶酪。这就是为什么我们相信这一结果的意义可能远远超出四色定理,”Mikkel Thorup说。
Mikkel Thorup 教授 计算机科学系 哥本哈根大学 mthorup@di.ku.dk +45 35 33 57 10/+45 21 17 91 23
Maria Hornbek 传播官 UCPH Communication 哥本哈根大学 maho@adm.ku.dk +45 22 95 42 83
哥本哈根大学成立于1479年,如今拥有37000名学生和10000名员工——其中超过5000名是研究人员——收入为113亿丹麦克朗。 该校研究人员已获得10项诺贝尔奖。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。