柯尼斯堡的七座桥

欧拉的分析

首先，欧拉指出，每个地块内部路线的选择并不重要。一条路线的唯一重要属性是过桥的顺序。因此，他把问题改为抽象的术语。这奠定了图论的基础。他删除了所有的特征，只保留了陆块的清单和连接它们的桥梁。在图论的语言中，他用一个抽象的 "顶点 "或节点取代了每个陆块。然后，他用一个抽象的连接，即 "边 "来取代每座桥。一条边（道路）记录了两个顶点（陆块）的连接。通过这种方式，他形成了一个图。

→ →

所画的图是一个问题的抽象图。因此，边可以以任何方式连接。只有两点是否相连才是重要的。改变图形的图片并不改变图形本身。

接下来，欧拉观察到（除了行走的端点），只要人们通过桥梁进入一个顶点，就会通过桥梁离开该顶点。在图形的任何行走中，进入一个顶点的次数等于离开顶点的次数。如果每座桥都被精确地穿过一次，那么，对于每块土地（除了为起点和终点选择的土地），接触该土地的桥的数量必须是偶数。这是因为如果有n座桥，它就正好被穿越了2n次。然而，原问题中的四个地块都被奇数的桥梁所触及（一个地块被5座桥梁触及，其他三个地块各被3座桥梁触及）。最多有两个地块可以成为步行的终点。因此，步行穿过每座桥一次的命题导致了一个矛盾。

用现代语言来说，欧拉表明，走过图中每条边一次是否可能，取决于节点的度。节点的度是指接触到它的边的数量。欧拉表明，步行的一个必要条件是，该图是连接的，并且正好有零个或两个奇数程度的节点。欧拉说的这个结果后来被卡尔-海尔霍泽证明。这样的行走现在被称为欧拉路径或欧拉行走。如果存在奇数程度的节点，那么任何欧拉路径都将从其中一个节点开始，在另一个节点结束。由于代表历史上的柯尼斯堡的图有四个奇数度的节点，所以它不可能有欧拉路径。

欧拉的工作在1735年8月26日提交给圣彼得堡学院。1741年，它以Solutio problematis ad geometriam situs pertinentis（与位置几何有关的问题的解决方案）的名义发表在Commentarii academiae scientiarum Petropolitanae杂志上。它的英文版本在《数学的世界》中可以找到。

在数学史上的重要性

在数学史上，欧拉对柯尼斯堡桥问题的解决被认为是图论的第一个定理。图论是一门学科，现在一般被认为是组合学的一个分支。

桥梁的现状

原来的七座桥中有两座在二战中轰炸柯尼斯堡时被毁。另外两座后来也被拆除了。它们被一条现代的高速公路所取代。其他三座桥仍然存在，尽管其中只有两座是欧拉时代的（一座是1935年重建的）。因此，截至2000年，加里宁格勒有五座桥。

就图论而言，现在有两个节点的度数是2，另外两个节点的度数是3。因此，现在可以有一条欧拉路径，但由于它必须从一个岛开始，在另一个岛结束，所以对游客来说是不实际的。

相关页面

• 伊科西游戏
• 汉密尔顿路径
• 水、气、电
• 游动销售员问题