两座岛、两岸、七座桥。按岸数桥得 3、3、3 与 5,次数相加是 3 + 3 + 3 + 5 = 14(第一个链接;第三个链接用 3 × 3 + 5 得到同一个 14,那是更快的分组)。总数的一半就是桥数——第二个链接除到 7——而这个关系不是这张地图特有的:每座桥都算进两个岸,所以次数之和必是边数的两倍。第四个链接 4 × 3/2 = 6 是可供架桥的陆地块配对数,而七座桥要坐进六个配对里,于是至少有一对地块之间连着两座桥而不是一座。
Euler 的论证是:一条每座桥只过一次的路,凡是路过的地块都必须成对地进入与离开,所以被当作停留点的每个顶点次数都是偶数;只有整条路的第一个与最后一个顶点可以例外,而那样的顶点只有两个。柯尼斯堡有四个奇次数的顶点,所以所要求的那种走法不存在,而且还没等人去量河就已经证完了。这正是这篇论文被当作图论的第一条定理、而不是一个谜题解答的原因:距离、岸的形状、普列戈利亚河的宽度全都无关,Euler 自己就这么说——他把这个问题放进了位置几何,而不是大小几何。七座桥里有两座在 1944 年被毁且未重建,所以今天这个问题成了游客的问题;这里的算术说的是 1735 年寄给 Euler 的那张地图。
答案
14
口径说明
四个次数之和。第二个链接把它对半分成七座桥,第三个用另一种加法得到同一个数,第四个数陆地块的配对。
出处
Leonhard Euler, 'Solutio problematis ad geometriam situs pertinentis', 1736, the founding paper of graph theory; the Königsberg bridges on the Pregel were seven in Euler's map, two of which were destroyed in 1944 and not rebuilt
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。