How Euler Did It ？ 哥尼斯堡七桥问题

luyuanhong

How Euler Did It ？ 哥尼斯堡七桥问题

来源：智趣空间

作者：Graham Shawcross

背景

伟大的瑞士数学家莱昂哈德·欧拉（Leonhard Euler）应但泽市市长的要求提供哥尼斯堡大桥问题的解决方案，他给市长发来了这样一段风淡云轻的答复：

“ …… 因此，您看到，尊敬的先生，这种类型的解决方案与数学没有什么关系，我不明白为什么您期望数学家而不是其他任何人来提出它，因为该解决方案仅基于理性及其发现不依赖于任何数学原理。正因为如此，我不知道为什么即使是与数学关系不大的问题，数学家也能比其他人更快地解决。”

然而，就在同一年，他在给意大利数学家和工程师乔瓦尼·马里诺尼的一封信中写下了这一点。

“这个问题是如此平凡，但在我看来值得关注，因为几何、代数、甚至组合学都不足以解决它。”

1735 年 8 月 26 日，欧拉提出了一篇包含哥尼斯堡桥梁问题解决方案的论文，其中他解决了具体问题，并给出了任意数量的陆地和任意数量的桥梁的通用解决方案。于 1741 年晚些时候发表的这篇论文的标题是  “Solutio Problematis ad geometriam sites pertinentis”。

下面是 James R.Newman 翻译的这篇论文的编辑版本的逐字版本,我刚刚恢复了原始论文的段落编号。

欧拉的论文

1. 几何学中涉及量值的分支在过去一直被热心研究，但还有另一个分支至今几乎不为人所知；莱布尼茨首先谈到了这一点，称之为“geometry of position”（geometry situs）。几何学的这个分支处理仅依赖于位置的关系，并研究位置的属性；它不考虑大小，也不涉及数量计算。但迄今为止，对于属于这种位置几何的问题或解决这些问题所使用的方法，还没有给出令人满意的定义。最近有人公布了一个问题，虽然看起来确实属于几何学，但它的设计却不需要确定大小，也不能通过定量计算来解决，因此我毫不犹豫地把它归类为 geometry of position 问题，特别是因为解决方案只需要考虑位置关系，计算是没有用的。在本文中，我将介绍我发现的解决此类问题的方法，这可以作为 geometry of position 的一个例子。

2. 据我所知，这个问题是众所周知的，其表述如下：在普鲁士的哥尼斯堡镇，有一座名为克奈福夫的 A 岛，普雷格尔河的两条支流环绕着它。有七座桥 a、b、c、d、e、f 和 g 跨越河流的两条支流。问题是，一个人是否可以计划一次步行，让他只穿过这些桥一次，且最多只能穿过一次。有人告诉我，虽然有些人否认这样做的可能性，另一些人则表示怀疑，但没有人坚持认为这实际上是可能的。

基于上述，我为自己提出了以下非常普遍的问题：给定河流及其支流可以分隔的的任何区域，以及任意数量的桥梁，确定是否可以穿过每座桥梁正好一次。

3. 哥尼斯堡七座桥梁的特殊问题可以通过仔细列出所有可能的路径来解决，从而通过检查确定其中哪一座（如果有的话）满足要求。然而，由于可能的组合数量众多，这种解决方法过于繁琐和困难，并且在涉及许多桥梁的其他问题中根本无法使用。因此我放弃了它并寻找另一个范围更有限的东西；即，仅显示是否可以首先发现满足规定条件的行程的方法；我相信，这种方法会更简单。



4. 我的整个方法依赖于我表示过桥的适当且方便的方式，因为我使用大写字母 A、B、C、D 来指定彼此被河流隔开的各个土地区域。因此，当一个人使用两个可能的桥梁 a 或 b 中的任何一个从区域 A 到达区域 B 时，我用字母 AB 表示， 第一个表示他来自的区域，第二个表示他过桥后到达的区域。如果旅行者随后从 B 过桥 f 进入 D ，该交叉点用字母 BD 表示； 连续执行的两个交叉 AB 和 BD 仅用三个字母 ABD 表示，因为中间的字母B是既指定了过第一座桥通向的区域，又是过第二座桥前所在的区域。

5. 同样，如果旅行者从 D 穿过桥 g 进入 C ，我用四个字母 ABDC 指定这三次连续的过桥路线。穿行四座桥梁将由五个字母表示，如果旅行者穿行任意数量的桥梁，他的旅程将由比桥梁数量大一的字母数量来描述。例如，需要八个字母来表示七座桥的交叉。

6. 使用这种方法，我不关心使用了哪些桥；如果可以通过几座桥梁中的一座从一个区域穿行到另一个区域，那么使用哪座桥梁都没有区别，只要它通向所需的区域即可。因此，如果可以在七座哥尼斯堡桥上布置一条路线，以便每座桥只经过一次且仅一次，则可以使用八个字母来描述这条路线，并且在这一系列字母 AB（或 BA）中将有发生两次，因为有两座桥（a 和 b）连接区域 A 和 B 。类似地，组合 AC 将出现两次，并且组合 AD、BD 和 CD 各出现一次。

7. 我们的问题现在简化为是否可以从四个字母 A、B、C 和 D 组成一系列八个字母，其中刚才提到的所有组合都出现所需的次数。然而，在做出努力之前，我认为最好考虑一下它的存在在理论上是否可能。因为如果能够证明这样的安排实际上是不可能的，那么试图找到它所花费的努力就会被浪费。因此，我寻求一种规则，可以毫无困难地确定所要求的字母排列是否可行，以及类似的问题。



8. 为了找到这样的规则，我选用单个区域 A ，任意数量的桥 a、b、c、d 等通向该区域。在这些桥梁中，我首先考虑的只有一座。如果旅行者过这座桥，他必须从 A 出发过桥，或者在过桥之后到达 A ，这样根据上述表示方法，字母 A 将恰好出现一次。如果有三座桥通向 A ，并且旅行者穿过所有三座桥，则字母 A 将在表示他的旅程的表达式中出现两次，无论它是否从 A 开始出发。如果有五座桥通向 A ，则穿过所有桥的路线的表达式将包含字母 A 三次。如果桥的数量是奇数，则加一，除二；商（答案）代表字母 A 出现的次数。

9. 现在让我们回到哥尼斯堡问题。由于有五座桥梁通往（和来自）A 岛，因此字母 A 在描述路线的表达式中必须出现 3 次。字母 B 必须出现两次，因为三个桥通向 B ；类似地，D 和 C 必须都出现两次。也就是说，代表七桥交叉的一系列字母必须包含三个 A 和 B、C、D 各两次。但这对于八个字母的序列来说是完全不可能的，因为所需字母的总和是九个（3 + 2 + 2 + 2 = 9）。因此，显然无法按照要求的方式跨越七座桥梁。

10. 使用这种方法，每当通往特定区域的桥梁数量为奇数时，我们总是能够确定在一次旅程中是否可以只穿过每座桥梁一次。如果桥的数量加一除二等于指示每个单独字母必须出现的频率的数字之和，则存在这样的路线。另一方面，如果这个总和大于桥梁数量加一（如我们的示例中所示），则无法构建所需的路线。我给出的用于根据通向 A 的桥梁数量确定字母 A 在路线描述中出现的频率的规则与这些桥梁是否都来自单个区域B无关或来自多个区域，因为我只考虑区域 A ，并尝试确定字母 A 必须出现的频率。

11. 当通往 A 的桥梁数量为偶数时，我们必须考虑路线是否从 A 开始。例如，如果有两个桥通向 A 并且路线从 A 开始，那么字母 A 将出现两次；一次表示从 A 出发过一座桥，第二次表示从另一座桥返回 A 。然而，如果旅行者在另一个地区开始他的旅程，字母 A 只会出现一次，因为根据我的描述方法，A 的单次出现表示进入和离开 A 。

12. 假设在我们的例子中，有四座桥梁通向区域 A ，并且路线从 A 开始 。字母 A 将在整个路线的表达式中出现 3 次，而如果旅程是在其他地区开始的，则 A 只会出现两次。有 6 个桥通向 A ，如果 A 是起点，则字母 A 将出现四次，否则仅出现 3 次。一般来说，如果桥的数量是偶数，当起始区域不是 A 时，字母 A 出现的次数将是一半桥梁数量；当路线从 A 开始时，一半加一。

13. 当然，每条路线都必须从某个地区开始。因此，根据通往每个区域的桥梁数量，我确定了相应字母在描述整个路线的表达式中出现的次数，如下所示：当桥梁数量为奇数时，我将其加一并除以二; 当数字是偶数时，我只是将其除以二。然后，如果所得数字之和等于桥梁数量加一，则旅程可以完成，尽管它必须从奇数桥梁所接近的区域开始。但是，如果总和比桥梁数量加一少一，则如果从桥梁数量为偶数的区域作为起点，则该旅程是可行的，因为在这种情况下，总和总会增加一。

14. 我确定在任何河流和桥梁系统中是否可以精确地穿过每座桥梁一次的程序如下：首先，我指定被河流分割开的 A、B、C 等各个区域。第二，计算桥的总数，将其加一，并将结果写在页面顶部。第三，在这个数字下我写下字母 A、B、C 等在第一列中，并在每个字母所在行注明通向该特定区域的桥梁的数量。第四，我再次在每个旁边有偶数的字母上放置一个星号。第五，在第三列中，我在每个偶数的对面写上该数字的一半，在每个奇数的对面写上该数字加一除二所得到的数。第六，我将最后一列数字相加。如果总和小于或等于顶部的数字，我就断定可以完成所需的旅程。但需要注意的是，当总和比最上面的数字小 1 时，路线必须从标有星号的区域开始，当两个数字相等时，必须从没有星号的区域作为起始位置。

对于哥尼斯堡问题，我将建立如下表格：



最后一列现在加起来超过 8 ，因此无法完成所需的行程。

15. 让我们以两个岛屿为例，周围有四条河流。



十五座标记为 a、b、c、d 等的桥梁横跨两个岛屿和毗邻河流的水面。问题是是否可以安排一次经过所有桥梁但只能经过一次的旅程。我首先用字母 A、B、C、D、E 和 F 标记被河流分隔的区域，共有六个。其次，我将桥的数量（15）加一，并将数字（16）写在最上面。第三，我写字母 A，B，C 等在一列中，在每个字母的对面写下与该区域连接的桥的数量，例如 A 是八座桥，B 是四座桥等。第四，与偶数相对的字母标有星号。第五，在第三列中，我写下每个相应数字的一半，或者如果数字是奇数，我会加一，然后写下总和的一半。第六，将第三列中的数字相加，总和为 16 。



第三列的总和与上面出现的数字 16 相同，因此如果旅程从 D 或 E 区域开始（其符号没有星号），则旅程可以生效。下面的表达式代表了这样一条路线：

               EaFbBcFdAeFfCgAhCiDkAmEnApBoElD

在这里，我用大写字母之间的小写字母指出了哪些桥梁被跨越。

16. 通过这种方法，即使在相当复杂的情况下，我们也可以轻松确定是否可以按顺序单次穿越每座桥梁。但现在我想给出另一种更简单的方法，经过一些初步评论后，该方法很容易从前面的方法中推导出来。首先，我注意到第二栏中写下的数字总和必然是桥梁实际数量的两倍。原因是，在通往各个区域的桥梁的列表中，每座桥梁都被计数两次，对其连接的两个区域各计数一次。

17. 根据这一观察，第二列中的数字之和必须是偶数，因为其中一半代表桥梁的实际数量。因此，如果与字母 A、B、C 等相对的任何数字是奇数，则它们的数量一定是偶数个。例如，在哥尼斯堡问题中，与字母 A、B、C、D 相对的所有四个数字都是奇数，而在刚刚给出的示例中，只有两个数字是奇数，即与 D 和 E 相对的数字。

18. 由于 A、B、C 等相对数的总和是桥数的两倍，因此很明显，如果在后一个示例中将该总和增加 2 ，然后除以 2 ，则结果将是编号写在顶部。当第二列中的所有数字都是偶数，并且每个数的一半写在第三列中时，该列的总和将比顶部的数字少一。在这种情况下，总是有可能穿过所有的桥梁。因为无论旅程从哪个地区开始，通往那里的桥梁数量都是偶数，这是必要条件。

19. 此外，当与字母相对的数字中只有两个是奇数，而其他数字是偶数时，只要其起始点位于奇数个桥梁所连接的区域，则所需的路线是可能的。按照我们的程序要求，我们取每个偶数的一半，同样在加一后取每个奇数的一半：这些一半的总和将比桥的数量大一，因此等于写在顶部的数字。但是，当第二列中的数字中有两个以上是奇数时，很明显第三列中的数字之和将大于顶部数字，因此所需的旅程是不可能的。

20. 因此，对于可能出现的任何配置，确定是否可以一次性穿越所有桥梁的最简单方法是应用以下规则：

如果有两个以上的区域有奇数个桥梁到达，则无法找到满足所需条件的路线。

然而，如果只有两个区域的桥梁连接数为奇数，则只要起始于这些区域之一，就可以完成所需的旅程。

最后，如果没有任何区域具有奇数数量的桥，则无论从何处开始，都可以实现所需的旅程。

这些规则完全解决了最初提出的问题。

21. 在确定一条路线确实存在之后，我们剩下的问题是如何找到它。为此，将遵循以下规则：只要有可能，我们就在心理上消除连接相同两个区域的任何两座桥梁；这通常会大大减少桥梁的数量。然后，这应该不会太困难，我们继续沿着其余桥梁追踪所需的路线。这条路线的模式一旦找到，将不会受到最初被排除在外的桥梁修复的重大影响，稍加思考就会发现。因此，我认为我不需要再多说寻找路线本身了。

评论

在克服了最初不愿意解决这样一个平庸问题之后，欧拉在第 1 节中将该问题与数学探究的一个新兴领域——位置几何联系起来。在第 2 节中，他清楚地陈述了问题，并标记了岛 Kneiphof A 和桥梁 a、b、c、d、e、f 和 g 。在第 3 节中，尽管欧拉认识到可以通过枚举所有路径来解决问题，但他拒绝这种方法，因为这种方法太繁琐、太困难且无法扩展。

在第 4、5 和 6 节中，欧拉建立了他的符号方法，将单独的土地区域 A、B、C 和 D 以及从一个区域到另一个区域的路径或旅程标记为这些字母 ABDC 等的字符串。注意哪座桥可用于从一个区域到达另一个区域。然后他指出，用他的符号表示七座桥的交叉需要一串八个字母，并且组合 AB (或 BA) 需要出现两次，组合 AC 也需要出现两次（每个都有两个桥），而组合 AD , BD 和 CD 每个都会出现一次（每个 CD 都只有一个桥）。

在第 7 节中，欧拉指出，现在的问题已简化为是否可以从 A、B、C 和 D 这四个字母组成一系列八个字母，其中可以出现刚才提到的所有组合。但在浪费精力寻找可能的安排之前，他希望看看是否能找到一个简单的规则来说明任何安排是否可能。在第 8 节中，他想象了一个区域 A ，任意数量的桥梁 a、b、c、d 等通向该区域。他首先只考虑桥 a ，并指出如果旅行者穿过这座桥，他必须来自 A 或到达 A ，因此字母 A 只会出现一次。如果有 3 座桥通向 A ，则字母A将出现两次；如果有 5 座桥，则字母 A 将出现 3 次。

因此，上述问题要求表示所需路线的字符串中只有 8 个字母，而且要求 A 出现 3 次，B、C、D 各出现 2 次，总共 9 次 ( 3 + 3×2 = 9 )。要求是矛盾的，因此没有可行的路线。

解决了所提出的问题后，欧拉继续推广他的方法，并提供了一个逐步算法来解决任意数量的岛屿和任意数量的桥梁的问题。但欧拉仍然不满意，并继续提出一套更 简单的三个规则，确定在任何情况下，是否所有桥梁都可以被跨越一次，而不会被跨越两次。

平面图

虽然欧拉的论文被广泛认为是图论的起源，但有趣的是，它实际上并不包含任何看起来像图的东西，其主要贡献在于所采用的符号。按照习惯，在欧几里得几何中，大写字母 A、B、C 等表示 点，小写字母 a、b、c 等表示边。欧拉使用大写字母表示区域，使用小写字母表示桥（区域之间的连接）。这促进了这样的想法：区域可以用点表示，连接可以用边表示。因此哥尼斯堡桥梁问题可以用图形表示如下：



通过这样的图，我们可以轻松地计算出具有奇数条边进入的节点的数量（上面标记为红色）。如果有超过 2 个具有奇数边的节点，则不可能有路径，但如果只有 2 个具有奇数边的节点，则可以找到一条路径，前提是从奇数之一作为起始点。



正如欧拉所指出的，如果两个区域之间有两座（或任意偶数座）桥梁，则可以忽略这些桥梁，因为旅行者可以使用一座桥从 A 到 C ，而 另一座桥从 C 回到 A ，完成一个循环，消除两座桥并将他留在起点，并能够继续前往另一座桥。

为了表彰欧拉对图论的贡献，访问每个节点一次但不超过一次的路线称为欧拉回路。欧拉的解决方案也适用于我在学校学到的另一个平庸的问题，即在不将铅笔从纸上移开的情况下绘制图形的一笔画问题。



如果地图的彩色区域被图中相同颜色的顶点替换，则彩色地图可以表示为平面图，并且如果顶点在图中的对应区域共享一条边，则顶点通过图中的边连接。



事实上平面图是地图的对偶，并且可以由图生成地图。地图和图都遵循欧拉对图论的另一个贡献，即他的网络公式； 区域 + 顶点 – 边 = 1 。在上面的示例中，对于地图来说 7 个区域 + 11 个顶点 – 17 条边 = 1 ，对于图来说 10 个区域 + 8 个顶点 – 17 条边 = 1。

因此，平面图与地图完全等价，并且四色猜想可以表示为看图的顶点是否可以用 4 种颜色着色，以便没有 2 个相邻顶点具有相同的颜色。

更重要的是，平面图适合计算机操作，这反过来又导致了有争议的计算机支持的四色定理证明。请参阅此处了解更多详细信息。

有向图

对于平面图，两个节点 A 和 B 之间的边（或弧）是双向的，就像一座桥梁，允许从 B 到 A 以及从 A 到 B 的移动，因此只能表示 A 和 B 之间的对称关系，就像邻接一样。另一方面，在有向图中，边被定义为具有方向，因此从 A 到 B 的边就像十字转门或阀门一样，允许从 A 到 B 的移动，但阻止从 B 到 A 的移动。这允许将值添加到每个边缘，以便可以表示流量、电流、尺寸等并对网络进行建模。



有关应用于自动生成房屋平面图的电线电流的基尔霍夫定律的详细信息，请参阅此处。有向图还构成了优先图、关键路径分析和现代图形编程系统（例如 Grasshopper）的基础，其中输入位于每个块的左侧边缘，输出位于右侧，脚本化过程可以添加到块本身。



参考书目：

Appel, K., Haken, W. and Koch, J.  (1977) Every Planar Map is Four Colorable. I: Discharging. Illinois J. Math. 21, 429-490

Appel, K. and Haken, W. (1977 ) Every Planar Map is Four-Colorable, II: Reducibility. Illinois J. Math. 21, 491-567.

Euler, L. (1736) Solutio problematis ad geometriam situs pertinentis. Comment. Acad. Sci. U. Petrop. 8, 128-140. Reprinted in Opera Omnia Series Prima, Vol. 7. pp. 1-10, 1766.

Hopkins B. and Wilson R. (2004) The Truth about Konigsberg. College Mathematics Journal , 35, 198-207

March, L. and Steadman, P. (1971) The Geometry of Environment. RIBA Publications Ltd.

Newman J. R. (1953) The Konigsberg Bridges. In Mathematics: An Introduction to its Spirit and Use, Scientific American. June 1978 22 121-124.

Steadman, P. (1970) The Automatic Generation of Minimum Standard House Plans Working Paper 23 University of Cambridge Land Use and Built Form Studies

Tutte, W. T. (1958) Squaring the Square from ‘Mathematical Games’ column, Scientific American Nov 1958.

数学经纬网 2023-11-21 19:00 发表于北京

Ysu2008

玩过几天 LabVIEW 图形编程，非常有趣。