柯尼斯堡七桥

题目

18 世纪的柯尼斯堡（今加里宁格勒）被一条河分成几块陆地，河上架着 7 座桥。市民们争论：能不能从某处出发，每座桥恰好走一次，最后回到（或走到）某处，不重复也不漏掉任何一座？

试过的人都没成功，但又说不清为什么不可能。

答案与解析

不可能。 1736 年，欧拉把问题抽象成图：把四块陆地看成顶点，七座桥看成连接顶点的边。问题变成：这张图能不能“一笔画”出来（每条边恰好经过一次）？

欧拉发现一个简单判据：

• 画的时候，除了起点和终点，每经过一个顶点，都是“进一次、出一次”，所以这些顶点的连边数必须是偶数；
• 因此，一个能一笔画的连通图，其“奇度顶点”（连边数为奇数的点）个数只能是 0 或 2。

而柯尼斯堡的四块陆地，连桥数分别是 5、3、3、3——四个顶点全是奇数度。奇度顶点有 4 个，超过了 2，所以必然无法一笔画。问题就此解决，连具体怎么走都不必试。

背后的数学

欧拉这篇论文通常被认为是图论的诞生。他第一次把“地理位置”剥离掉，只保留“点”和“连接关系”，这种抽象正是现代离散数学的精髓。

如今，“一笔画”判据是图论最经典的入门定理之一；而当要求“回到起点”时，所有顶点都必须是偶度（对应“欧拉回路”）。从七座桥到社交网络、电路板布线、快递路径优化，用的都是同一套语言。