图论的历史：从哥尼斯堡到神经网络

1. 诞生 (1736)：哥尼斯堡七桥问题

与许多从古希腊或印度传统中历经几个世纪缓慢发展起来的数学领域不同，图论的确切出生地和出生日期是无可争议的。它于 1736 年诞生于一位天才的大脑：莱昂哈德·欧拉（Leonhard Euler）。

当时，普鲁士城市哥尼斯堡（现俄罗斯加里宁格勒）横跨普列戈利亚河两岸，并包含两个大岛。这四块陆地由恰好七座桥梁相互连接。

哥尼斯堡的市民创造了一个当地的谜题，一段都市传说：是否有可能在城市里散步，恰好穿过七座桥中的每一座一次，然后回到起点？

尽管进行了无数次尝试，没有人能找到这样一条路径，也没有人能最终证明这是不可能的。1735 年，这个问题引起了在圣彼得堡科学院工作的欧拉的注意。

欧拉的抽象

欧拉的天才不仅在于解决问题，还在于意识到哪些信息是无关紧要的。他认识到确切的自然地理——岛屿的大小、桥梁的长度、它们之间的距离——根本无关紧要。唯一重要的是连接（Connections）。

他抽象了地图：四块陆地变成了点（我们现在称之为顶点（vertices）或节点（nodes）），而七座桥变成了连接它们的线（我们现在称之为边（edges））。

在 1736 年的开创性论文《Solutio Problematis ad Geometriam Situs Pertinentis》（与位置几何有关的问题的解）中，欧拉证明了这种散步是不可能的。他推论，当您通过一座桥进入一块陆地时，您必须通过另一座桥离开它。因此，每块陆地都必须有偶数座连接它的桥梁（除非它是起点或终点）。由于哥尼斯堡的所有四块陆地都有奇数座桥梁与它们相连，因此该路径不可能存在。

通过将重点从距离和测量转移到连接和相对位置，欧拉不仅在无意中创立了图论，而且还为拓扑学奠定了概念基础。

2. 19 世纪：哈密顿、基尔霍夫和树

在欧拉论文发表后的约一个世纪里，图论的发展极少。它主要被视为休闲拼图的集合，而不是数学的一个严肃分支。然而，在 19 世纪，图论开始在其他科学学科中找到应用。

树与化学

1857 年，英国数学家 亚瑟·凯莱（Arthur Cayley） 使用了一种特定类型的图——一种没有循环的连通图，他称之为树（tree）——来计算理论化学中烷烃的同分异构体数量。大约在这个时候，在 1878 年，数学家 詹姆斯·约瑟夫·西尔维斯特（James Joseph Sylvester） 首次在数学意义上正式使用了“图”（graph）一词，并在化学键和数学连接之间进行了类比。

电路

1847 年，德国物理学家 古斯塔夫·基尔霍夫（Gustav Kirchhoff） 将图论概念应用于电路。为了计算复杂电网每个分支中的电压和电流，基尔霍夫开发了定律，这些定律从根本上依赖于寻找电路图的生成树（spanning tree）。这是图论被应用于严肃工程问题的最早实例之一。

十二面体游戏与哈密顿路径

1857 年，爱尔兰数学家 威廉·卢云·哈密顿爵士（Sir William Rowan Hamilton） 发明了“十二面体游戏”（Icosian game），这是一个作为木制十二面体出售的谜题，每个顶点都有一个木钉。目标是找到一条正好访问每个顶点一次并返回起点的路径。虽然欧拉研究的是正好访问每条边一次的路径（现在称为欧拉路径），但正好访问每个顶点一次的路径现在永远被称为哈密顿路径（Hamiltonian paths）。确定哈密顿路径是否存在，直到今天仍然是一个极其困难的计算问题（NP-完全问题）。

3. 百年之战：四色定理

也许没有什么问题比著名的四色猜想（Four Color Conjecture）更能推动图论的发展了。该问题由 弗朗西斯·古思里（Francis Guthrie） 在 1852 年尝试为英国各郡地图着色时首次提出。

该猜想简单地指出：给定平面上任何分为连续区域的地图（如国家的政治地图），可以使用最多四种颜色对这些区域进行着色，使得没有两个相邻的区域具有相同的颜色。

这个问题完美地转化为图论：如果每个区域都是一个顶点，并且一条边连接共享边界的区域，你是否可以仅使用四种颜色对顶点进行着色，使得没有两个相连的顶点共享一种颜色？

错误的开端与挫折

这个问题看起来具有欺骗性的简单。1879 年，阿尔弗雷德·肯佩（Alfred Kempe）发表了一个被广泛接受的证明。十一年后，即 1890 年，珀西·希伍德（Percy Heawood）在肯佩的证明中发现了一个致命的缺陷（尽管希伍德能够挽救该证明以证明五色定理）。1880 年，彼得·泰特（Peter Tait）发表了另一个证明；十一年后，朱利叶斯·彼得森（Julius Petersen）也发现了那个证明中的缺陷。

几十年来，最聪明的数学头脑都未能证明四色猜想，这极大地推动了平面图、顶点着色和色多项式研究的进步。

计算机辅助的突破

最终，在 1976 年，数学家 肯尼斯·阿佩尔（Kenneth Appel） 和 沃尔夫冈·哈肯（Wolfgang Haken） 提供了一个证明。然而，这引起了极大的争议。他们的证明将无限的可能地图减少到 1,936 个可约配置（后来被细化为 633 个）。为了验证每个配置都是可着色的，他们依赖了超过 1,000 小时的计算机计算。

这是第一个使用计算机证明的主要数学定理。它在数学界引发了一场大规模的哲学辩论。如果人类无法独立验证步骤，它真的是一个数学证明吗？今天，计算机辅助证明已被广泛接受，但四色定理仍然是数学史上的一个决定性时刻。

4. 概率革命：埃尔德什与雷尼

两百多年来，图论的重点是静态的、确定性的结构。如果你有一个特定的图，你会问关于它的具体问题。但是在 1950 年代后期，由于杰出的匈牙利数学家 保罗·埃尔德什（Paul Erdős） 和 阿尔弗雷德·雷尼（Alfréd Rényi），该领域经历了巨大的范式转变。

他们引入了随机图（Random Graphs）的概念，将图论从一门纯结构学科转变为一门概率和统计科学。

埃尔德什-雷尼模型

他们提出了一个简单的模型：取 n 个顶点。对于每对可能的顶点，抛一枚有偏见的硬币。以概率 p，在它们之间画一条边。以概率 1 - p，不画。

数学家们不再问“这个图是否有哈密顿路径？”，而是开始问：“一个随机图有哈密顿路径的概率是多少？”

相变与巨型组件

埃尔德什和雷尼发现了一些令人叹为观止的东西。当你慢慢增加边形成的概率 p 时，属性并不是逐渐出现的——它们是突然出现的。他们发现了突然的相变（phase transitions），就像水在零度时突然结成冰一样。

例如，如果 p 很小，图是一组分散的、小的、不连通的组件。但是当 p 越过一个特定的临界阈值的那一刻，一个“巨型组件”（Giant Component）突然出现，瞬间将大量顶点连接成一个单一的网络。这一数学发现被证明对于理解从传染病的传播到互联网的弹性等一切事物都是至关重要的。

5. 现代时代：算法、网络与机器学习

随着 20 世纪下半叶计算机时代的到来，图论爆发了。它从抽象数学转变为计算机科学的绝对核心。

算法繁荣 (1950年代 - 1980年代)

随着计算机能够处理大型数据集，研究人员开始集中精力开发有效的算法来遍历和操作图。 艾兹赫尔·韦伯·迪杰斯特拉（Edsger W. Dijkstra）于 1959 年发表了他著名的最短路径算法。 福特（Ford）和富尔克森（Fulkerson）于 1956 年发表了他们的最大流算法。 罗伯特·塔扬（Robert Tarjan）在 1970 年代开发了用于寻找强连通分量和割点的线性时间算法。

网络科学与万维网 (1990年代 - 2000年代)

随着互联网的发展，研究人员意识到埃尔德什-雷尼的随机图模型并不能准确描述现实世界的网络。真实的网络，如万维网或人类社交网络，并不是纯粹随机的。

1999 年，艾伯特-拉斯洛·巴拉巴西（Albert-László Barabási）和雷卡·艾伯特（Réka Albert）引入了无标度网络（Scale-Free Network）模型，其特点是存在高度连接的“枢纽”。与此同时，邓肯·沃茨（Duncan Watts）和史蒂文·斯特罗加茨（Steven Strogatz）形式化了“小世界”（Small-World）现象（六度分隔理论）。

图论最著名的现代应用可能是拉里·佩奇（Larry Page）和谢尔盖·布林（Sergey Brin）的 PageRank 算法，该算法从根本上将整个万维网视为一个巨大的有向图，使用特征向量中心性对网站的重要性进行排名，并催生了谷歌搜索引擎。

图神经网络 (2010年代 - 至今)

今天，图论已经与人工智能融合。标准神经网络在处理非结构化、不对称数据方面存在困难。开发了图神经网络（GNNs），使机器学习模型能够直接处理图结构。

GNNs 目前正在推动药物发现（通过将分子视为原子图）、交通预测（通过将道路网络视为图）和推荐系统（通过将用户-项目交互建模为二分图）方面的巨大突破。

6. 结论：连接一切的分支

图论的历史证明了数学抽象的力量。起初是为了解决普鲁士河流上桥梁的一个微不足道的谜题，现在已经发展成为描述复杂关系的最终数学语言。

从绘制人类大脑复杂的线路图（连接组）到优化全球供应链，从在谷歌地图上寻找最快的回家路线到发现新抗生素的化学结构，图论仍然是我们深度互联世界的无形架构。