一部图论发展史：从柯尼斯堡七桥到改变世界的现代数学语言

1736年的普鲁士柯尼斯堡城中，一个有趣的消遣游戏在当地居民中流行：在这座被普列戈利亚河分割的城市里，能否找到一条路线，一次性走遍连接两座小岛与两岸的七座桥，且每座桥只走一次？

图源：维基

很多人尝试过，但没有一人能走通，也没人知道为什么。当这个问题传到大数学家欧拉耳朵里后，他完成了一次漂亮的思想飞跃，彻底解决了这个问题。

欧拉抛弃了所有无用的物理表象——岛屿的面积、桥梁的长度，所有与连接关系无关的属性，通通不重要。他剥离了度量信息，直击问题的拓扑核心：连通关系，将陆地简化为点，桥梁简化为线。

凭借这一思维跨越，欧拉发表了论文《与位置几何有关的一个问题的解》(Solutio Problematis ad Geometriam Situs Pertinentis)。他不仅通过严格的逻辑证明了七桥路线的不存在，更由此奠定了数学中一个全新分支——图论(Graph Theory)的基础。

欧拉的这篇论文，连同范德蒙在1771年发表的关于骑士巡逻(Knight's tour)问题的研究，共同推进了由莱布尼茨开启的位置分析(Analysis situs)探索。

欧拉这种只看连通关系、不看几何形状的抽象思考方式，对后世数学产生了深远影响。

unset unset剥离表象的位置分析unset unset

几十年后，柯西与西蒙·安托万·让·吕利耶等数学家继续沿着这一方向探索。欧拉本人发现了凸多面体的一个基本性质，后来被称为欧拉示性数(Euler's characteristic)公式：对于任何凸多面体，顶点数 、边数 与面数 永远满足恒等式： 。柯西等人将其推广到了更一般的情况。

这种研究物体在连续变形下保持不变的性质的学问，最终演化成了今天大名鼎鼎的拓扑学(Topology)。图论与拓扑学的发展始终紧密交织，相互滋养。在1860年至1930年间，拓扑学的独立发展通过若尔当、库拉托夫斯基以及惠特尼的工作，反向滋养了图论。

19世纪中叶，推动两门学科共同演进的另一股力量来自现代代数工具的引入。物理学家基尔霍夫在研究电路时，独立发展了用图表示电路结构的方法，并由此提出了现代电子工程领域的基础法则——基尔霍夫电路定律(Kirchhoff's circuit laws)。

而在同一时期，当约翰·本尼迪克特·李斯廷刚刚将拓扑学这一概念引入学术界时，凯莱在研究微分算子的代数结构时，开始关注一类特殊的图——树(Trees)。凯莱敏锐地发现，这些没有回路的树，与化学分子中原子的内在连接网络存在着高度的结构同构性。他将关于树的成果与当时的化学成分研究结合起来，这种数学与化学的跨界结合，为枚举图论(Enumerative graph theory)的诞生奠定了重要基础。

这一领域随后在波利亚于1935至1937年间发表的奠基性成果中得到确立，并于1959年被德布鲁因推广，同时也为图论留下了许多源自化学的专有名词。

随着理论的不断成熟，图论的系统化构建也被提上日程。1936年，柯尼格出版了世界上第一本系统的图论教材。

1969年，哈拉里出版了该领域的权威教科书。特别是哈拉里的著作，打破了学科间的专业壁垒，使得数学家、化学家、电气工程师以及社会科学家得以在统一的理论框架下探讨网络结构问题。哈拉里更将该书的全部版税捐出，资助设立了波利亚奖(Pólya Prize)。

unset unset四色问题驱动的理论突破unset unset

如果说七桥问题是图论的起点，那么四色问题就是推动这门学科发生质变的催化剂。

不妨想象一张空白的世界地图。如果要给不同的国家上色，并且保证任何两个相邻（有共同边界而非仅一个公共点）的国家颜色都不一样，你最少需要几支彩笔？

德摩根写给哈密顿的信件，首次提到四色猜想。现存于都柏林三一学院。DeMorganFourColour

1852年，弗加斯·格思里在给英国地图上色时，经过观察发现，四种颜色就足够了，并提出了这个著名的猜想。这就是后来困扰数学界一个多世纪的四色问题(Four color problem)。同年，德·摩根在写给哈密顿的一封信中，留下了关于该问题的最早书面记录。

这个猜想看似简单，证明过程却异常艰难。一个多世纪以来，无数顶尖数学家都曾尝试证明这个猜想，却都未能成功，期间诞生了诸如凯莱、肯普等人的错误证明。肯普曾发表过一份仗着直觉而学术上看似优雅的证明，在被数学界普遍接受十余年后，才被希伍德指出存在致命的逻辑漏洞。

然而，这些艰难的尝试并非徒劳。为了解决四色问题，数学家们发展出了许多新方法。泰特将四色问题转化为图的因子分解问题(Factorization problems)，这一重新表述衍生出了一类新问题，并由彼得森与柯尼格进行了重点研究；希伍德、拉姆齐与雨果·哈德维格则将问题推广到了嵌入在任意亏格(Genus)曲面上的图着色问题。

与此同时，拉姆齐在着色理论上的工作，特别是图兰于1941年发表的关于图的边数与特定子图存在性关系的研究，共同开创了图论的另一重要分支——极值图论(Extremal graph theory)。

unset unset机器辅证与随机演化：走向复杂系统unset unset

四色问题的最终解决，引发了长久的数学争议。

1969年，海因里希·赫施首先发表了一种利用计算机求解该问题的方法。1976年，阿佩尔和哈肯正式宣布证明了四色定理。他们的核心策略深层依赖于海因里希·赫施提出的放电法(Discharging Method)，将无限复杂的地图归纳为 种基本构型，并借助当时的大型计算机进行了全面的穷举验证。

这是人类历史上第一个主要依靠计算机完成的重要数学定理证明。由于人类无法逐一检查所有构型，这个证明在当时引发了巨大争议，许多数学家拒绝接受这种无法被手动验证的证明方式。直到二十年后，罗伯逊、西摩、桑德斯和托马斯将构型数量优化至 种，提供了一个更为简洁的证明版本，相关争议才逐渐平息。

但这还不是故事的终点。

2005 年 1 月互联网拓扑局部图（数据：opte.org）

就在人们以为图论的研究对象仅限于静态的确定性图(Deterministic Graphs)时，埃尔德什与雷尼将概率论的思想引入进来了。他们改变了传统的研究视角，不再局限于单一图的静态拓扑，而是专注于研究图连通性的渐近概率。他们思考：当顶点数量趋向无穷时，在给定顶点之间以特定概率随机生成连线，图的连通性等整体性质将呈现何种渐近规律？就这样，随机图论(Random graph theory)作为一个全新分支破土而出。

今天图论已经渗透到现代科学的几乎每一个角落，计算机科学家用来设计算法与数据结构的基础，生物学家研究基因调控网络与蛋白质相互作用，社会学家分析人际关系与信息传播，也被工程师用于设计通信网络和交通系统。

就这样，图论从柯尼斯堡里的趣味问题出发，经过近三百年的发展，已经超越了传统几何学的经典范畴，成长为我们理解这个复杂互联世界的一种数学语言。

参考资料：维基百科(Graph theory)

来源：遇见数学

编辑：柠七

转载内容仅代表作者观点

不代表中科院物理所立场

如需转载请联系原公众号