欧拉与柯尼斯堡七桥问题

Leonhard Euler

莱昂哈德•欧拉（Leonhard Euler）是十八世纪最伟大的科学家之一， 也是数学史上最多产的数学家。他生前一共出版了800多篇论文和著作，其中包含大量的力学、分析学、几何学、变分法等的课本，《无穷小分析引论》、《微分学原理》、《积分学原理》等都成为数学界中的经典著作。欧拉对数学的研究如此之广泛，因此在许多数学的分支中也可经常见到以他的名字命名的重要常数、公式和定理，例如欧拉常数、多面体欧拉定理、三角形的欧拉线、欧拉动力学方程、欧拉图、欧拉五边形数定理等等。

关于欧拉，有一个非常有趣的故事。

在18世纪，东普鲁士哥尼斯堡（今日俄罗斯加里宁格勒）有一条大河，河中间有两座岛屿，其中大一点岛屿与南北陆地各有一座桥相连，小一点的岛屿与南北陆地各有两座桥相连，而在两座岛之间，还有一座桥联系着两岛，因此一共有七座桥连接着两个岛屿和陆地。当时许多市民都在思索一个问题：一个散步者能否从某一陆地出发，不重复地经过每座桥一次，最后回到原来的出发地？这就是历史上有名的柯尼斯堡七桥问题。

这个看似不难解决的问题吸引了很多人来尝试，大家纷纷进行试验，但在相当长的时间里，始终未能解决。如果利用普通数学知识，每座桥均走一次，那经过这七座桥所有的走法一共有5040种，而这么多情况，要一一试验，在没有计算机帮助的年代，无疑意味着庞大的工作量。但怎么才能找到成功走过每座桥而不重复的路线呢？

1735年，有几名大学生写信给当时正在俄罗斯的彼得斯堡科学院任职的天才数学家欧拉，请他帮忙解决这一问题。欧拉亲自来到柯尼斯堡，观察了七桥后，认真思考走法，但始终没能成功，于是他怀疑七桥问题是不是原本就无解呢？

有时候，放弃这一问题是合理的。这就是 Leonhard Euler 的解决方法，他没有试图解决这一问题，而是证明其不可解决。让我们试着去理解欧拉的内在想法，做到像欧拉一样思考。首先从下图开始：

图中有四块彼此分隔的区域，两个岛屿和两块陆地，以及七座桥。接下来让我们一起探讨每一区域的桥数是否有一定模式：

每块区域的桥数

如图所示，每块区域的桥数皆为奇数。如果你只能穿过桥一次，区域有两座桥，那么你就可以进入并离开该区域。

有两座桥的区域的示例

通过图示很容易发现，如果你通过一座桥进入一个区域，那么你也要通过第二座桥离开它。但是当第三座桥出现，则无法只穿过桥一次而离开。所以对于一块区域，当桥数为偶时，则可以每座桥只穿过一次而离开；当桥数为奇时，则不能。

让我们再添加一座新桥，如下图所示，看看其是否能解决问题。

现在我们有两个偶数和两个奇数。让我们在添加新桥的图上画一条新路线。

我们已经看到了桥的奇偶数是重要的。这里有个问题：桥的数量解决问题了吗？难道这个数不应该一直是偶数吗？后来发现不是的。这就是欧拉做的，他发现了一个显示桥数量很重要的办法。更有意思的事，有奇数个连接点的「陆地」也很重要。这时候欧拉开始把陆地和桥转化成我们看得懂的图。下面是一幅表示了柯尼斯堡七桥的图：

抽象化七桥问题

在经过一年的研究之后，1736年莱昂哈德·欧拉提出并没有方法能圆满解决这个问题，他更在论文《柯尼斯堡的七桥》中，证明符合条件的走法并不存在，也顺带提出和解决了一笔画问题。这篇论文在圣彼得堡科学院发表，成为图论史上第一篇重要文献，也成为拓扑学的出发点。

欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数，这样的点称为偶顶点。相对的，连有奇数条线的点称为奇顶点。欧拉论述了，由于柯尼斯堡七桥问题中存在4个奇顶点，它无法实现符合题意的遍历。

欧拉把问题的实质归于一笔画问题，即判断一个图是否能够遍历完所有的边而没有重复，而柯尼斯堡七桥问题则是一笔画问题的一个具体情境。欧拉最后给出任意一种河──桥图能否全部走一次的判定法则，从而解决了“一笔画问题”。对于一个给定的连通图，如果存在超过两个（不包括两个）奇顶点，那么满足要求的路线便不存在了，且有n个奇顶点的图至少需要n/2笔画出。如果只有两个奇顶点，则可从其中任何一地出发完成一笔画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现，他还说明了怎样快速找到所要求的路线。

难倒许多人的七桥问题，经过欧拉这样转化，简单而圆满地解决了。

为了让大家更加生动地理解七桥问题，华院君找到了来自“遇见数学翻译小组”的视频——《柯尼斯堡七桥问题是如何改变数学的》：

本文综合自机器之心、遇见数学、潮科普科学平台等。

『往期精彩』

▼▼▼

点击“阅读原文”了解更多