图论的诞生：欧拉与柯尼斯堡的七桥问题 _古代数学

十八世纪，在今天俄罗斯加里宁格勒市还被称为柯尼斯堡的年代。像其他许多大城市一样，一条大河(普列戈利亚河)穿城而过。柯尼斯堡除了被一分为二以外，还包含河中的两个岛屿，人们建有七座桥梁连接着不同的陆地。
当时有一个著名的游戏谜题，就是在所有桥都只能走一遍的前提下，怎样才能把这片区域所有的桥都走遍？
这个谜题成为当地人一项热衷的消遣运动，许多人声称已经找到了这样一条路径，但当被要求按照规则再走一遍时，却发现还是没有人能够做到。

文章插图

直到 1736 年，瑞士数学家莱昂哈德·欧拉给出了答案，他在论文《柯尼斯堡的七桥》中解释了其中的原因，证明这样的步行方式并不存在，并在文中提出和解决了一笔画问题。
欧拉的解决方案出乎意料地简单--只要我们以正确的方式看待这个问题就容易得到答案。
诀窍是要剔去所有不必要的信息。比如，在不同的陆地上走哪条路并不重要。不要管陆地是什么形状，河流是什么形状，桥梁是什么形状，通通这些都不重要。
因此，不妨用一个点来表示一块陆地，用一条边来表示一座桥。根本不需要做到地理上的精确表示：只要不破坏点的连通性，两点间不要连接错误，就能以任何方式表示地理信息而不改变问题本身。

文章插图

▲ 对七桥问题的改造(图自维基)
一旦用这种方式看待问题，它的特征就更清晰了。对图形观察规律后，应该会注意到以下情况：当通过一条边到达一个点时（通过桥进入某块陆地），那么除非它是行走的最后一个点，否则要再次离开它时，就得通过不同的边，因为这是游戏的规则。也就是说，任何不是起点和终点的点都需要有偶数条边从它那里出来：每进入一条线，就必须有一条边能离开。
为了使每条边都能准确穿过一次，那么最多只能有两个点有奇数个边出来。事实上，要么有两个奇数的点，要么根本没有。在前一种情况下，这两个点对应于步行的起点和终点，而在后一种情况下，起点和终点是同一点。然而，在柯尼斯堡问题中， 4 个点都有奇数条边，所以穿过每座桥的步行是不可能的。
用现在图论的术语来说，柯尼斯堡七桥问题属于一笔画问题：如何判断这个图是否是一个能够遍历完所有的边而没有重复。如果存在这样的方法，该图则称为欧拉图。这时遍历的路径称作欧拉路径（一个环或者一条链），如果路径闭合（一个圈），则称为欧拉回路。
欧拉的这个结论标志着图论的诞生，即研究由线连接的点组成的网络。他还能够证明，如果一个图满足上述条件，图中奇数顶点（连接的边数量为奇数的顶点）的数目等于 0 或者 2 。
另外，这一结果也预示着拓扑学的思想，拓扑学只研究形状的连接性，而并不关注距离和角度。现在每张地铁地图是拓扑学应用的很好例子。通过改变距离和角度，它把本来是难以理解的乱七八糟的地理信息变成了一张每个游客都能毫不费力地阅读的路线图。

文章插图

▲ 加里宁格勒的现代地图。其余桥梁的位置以绿色突出显示，而那些被摧毁的则以红色突出显示(图自维基)
最后还有 2 点再补充一下。首先是一笔画问题与图论中哈密尔顿问题的区分，前者讨论的是能否不重复地遍历图的所有边，对点是否重复并无要求。而哈密尔顿问题讨论的是能否不重复地遍历一个图的所有顶点。
第二点是看看现在柯尼斯堡这些桥的现状。七座原始桥梁中的两座在二次大战中被炮火摧毁，目前只余五座桥梁。所以回头再看这个问题，现在两个节点的度数为 2 ，另外两个节点的度数为 3 ，因此，欧拉路径是存在的。如果有幸到那边旅游，不妨也慢慢步行一圈欧拉路径，一路异国风景尽在眼前，与大数学家欧拉一同感受下这个奇妙的问题。