离散数学中的柯尼斯堡桥问题

柯尼斯堡

• 柯尼斯堡是这座德国城市的名字，但这座城市现在属于俄罗斯。
• 在下面的图片中，我们可以看到柯尼斯堡的内城和普列戈利亚河。
• 河流普列戈利亚亚将城市分为四个区域，即 A、B、C 和 D。
• 总共有 7 座桥梁连接城市的各个部分。

柯尼斯堡桥问题

柯尼斯堡桥包含以下问题：

如果从 A、B、C 和 D 这四个陆地区域中的任何一个开始，是否有可能只在一次行程中经过所有七座桥，并且不游泳的情况下回到起点？

柯尼斯堡桥问题的解决方案

• 1735 年，瑞士数学家莱昂哈德·欧拉解决了这个问题。
• 根据该问题的解决方案，这类行走是不可能的。

欧拉通过以下图表展示了该解决方案。

在上述图表中，有以下内容：

• 图的顶点用来表示陆地。
• 边用来表示桥梁。

现在我们将看一张图片，并尝试理解柯尼斯堡桥的概念。

对于柯尼斯堡的市民来说，他们试图以一种只走过每座桥一次的方式绕城市行走，但这被证明是一个困难的问题。因此，欧拉最终证明了这种行走是不可能的。欧拉通过发明一种称为网络的图示来证明这一点。这个网络由弧和顶点组成。弧也称为线，顶点也称为线的交汇点。

在这张图中，他使用了两个岛屿和 4 个点（顶点）来表示两条河岸。这些点用 A、B、C 和 D 标记。7 条线（弧）用于表示七座桥。在上述图中，3 座桥（弧）连接河岸 A，3 条弧连接河岸 B。同样，5 座桥（弧）连接岛屿 C，3 条弧连接岛屿 D。这表明该网络的所有顶点都具有奇数条弧，因此这些顶点称为奇数顶点。（偶数顶点是指连接到它的桥梁数量是偶数的顶点）。

我们需要记住，柯尼斯堡问题的目标是绕城市行走，并且只走过每座桥一次。在欧拉的网络中，这意味着所有顶点都必须被访问，并且每条弧只能被描绘一次。他对此进行了研究，并说这是不可能的，因为要做到这一点，我们需要奇数顶点，而对于奇数顶点，行程必须从该顶点开始并在该顶点结束。因此，只有 2 个奇数顶点，并且只有 1 个起点和 1 个终点，前提是我们可以只描绘一次每条弧。由于该桥梁总共有 4 个奇数顶点，因此不可能做到。

因此，欧拉观察到，在描绘图时，如果他们试图访问一个顶点，则会发生以下情况：

• 图将包含一条进入顶点的边。
• 它将包含另一条离开该顶点的边。
• 因此，顶点的阶数必须是偶数。

基于上述观察，欧拉还发现了一件关于网络的事情：网络中存在的奇数顶点的数量决定了任何网络是否可遍历。

关于网络，欧拉发现，只有当网络包含以下内容时，该网络才是可遍历的：

• 网络不包含任何奇数顶点。在这种情况下，起点和终点必须相同。起点可以是任何顶点，但终点必须与起点相同。
• 或者网络包含两个奇数顶点。在这种情况下，起点必须是其中一个奇数顶点，终点必须是另一个奇数顶点。

现在，

• 由于柯尼斯堡网络总共有 4 个奇数顶点，因此欧拉得出结论，该网络是不可遍历的。
• 因此，欧拉最终得出结论，不可能完成柯尼斯堡所需的徒步旅行。

注意

如果柯尼斯堡市民想从一个陆地建造八座桥梁到另一个陆地，即从 A 到 C，那么它将具有以下特性：

• 他们将有可能进行一次行走，而无需重复穿越任何一座桥。
• 因此，它将恰好有两个奇数顶点。
• 但是，如果我们尝试添加第九座桥，那么由于这个原因，这次徒步旅行将再次变得不可能。

最后，我们有一个问题：如果网络根本不包含奇数顶点，会发生什么？在这种情况下网络可以被描绘出来吗？

偶数顶点的图示如下：

在网络发明之时，一种全新的几何学被发现，称为拓扑学。现在，我们在规划和绘制铁路网络等许多方面都使用了拓扑学。