JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
Back to the library
数学 1736

关于位置几何之一问题的解答

莱昂哈德·欧拉

能否一次走遍柯尼斯堡的七座桥、每座恰好一次?欧拉的「不能」开创了图论。

Choose your version
In depth · the introduction

七座桥,一座城,一个简单的挑战:把每座桥都恰好走一次。那位证明「办不到」的人,悄然发明了一整门新的数学。

核心想法

古老的普鲁士城市柯尼斯堡,坐落在一条河的两岸、又环抱着河中的一座岛,全由七座桥缝合在一起。当地流行的周日挑战,是穿城走一圈、把每座桥都走一次、且只走一次——任何一座都不许重复。没人走得通,却也没人说得清为什么。

莱昂哈德·欧拉——他那个时代最高产的数学家——意识到街道的布局根本无关紧要。要紧的只有一件事:每块陆地连着多少座桥。他证明:要让这趟散步可行,几乎每一块陆地都得连着偶数座桥——而柯尼斯堡的每一块,连的都是奇数座。于是散步不可能办到,而他无需离开书桌,就能把它证明出来。

它是如何诞生的

这道谜题大约在 1735 年传到欧拉手中,当时他正在圣彼得堡科学院。起初他觉得它配不上严肃的数学——是个谜语,而非定理。但解它,逼着他发明出一种思考方式:用他的话说,是位置要紧、而距离不要紧的问题——一门莱布尼茨命过名、却无人发展过的「位置几何」。

欧拉没有去试那成千上万条可能的路线,而是找到一条计数规则,一举判定了问题,并意识到:无论哪座城、有多少座桥,它都同样管用。他在 1735 年把它呈给科学院;论文于 1741 年印行。数学家们如今把图论的诞生,定在这篇论文。

它为何重要

欧拉表明:你可以把某件事「不可能」干净、确定地证明出来;而这证明,能丢开一个问题几乎所有具体的东西,只留下它连接的图样。这一手——抛掉距离与形状、去研究纯粹的结构——一下子开启了两门学科:图论,网络的数学;以及拓扑学,不靠测量的形状之数学。

一个可以想象的画面

想象一幅连点成形的图画,你想用一笔连续的笔画把它描完,既不抬笔、也不让任何一条线被重描两次。试一下,你会摸到那条规则:每一个你经过的点,都需要一进一出两条线——也就是偶数条线。只有起点和终点那两个点,才可以是奇数条线。如果有三个或更多的点是「奇数」,一笔就画不成。柯尼斯堡是四个奇数点——没指望。

可交互的柯尼斯堡地图:四块陆地、七座桥;点一座桥可拆掉或重建,也可打开第八座桥。组件会显示每块陆地的度数,高亮连着奇数座桥的陆地并计数,并判定是否存在把每座桥恰走一次的路线:无奇数陆地时为环行,恰有两块时为单程,否则不存在。

它的位置

欧拉写下它时,正值一门关于结构的新数学破晓。同样的直觉——留住连接、丢开测量——后来长成了拓扑学,也长成他自己那条把任何立体的顶点、棱、面联系起来的公式 V − E + F = 2。今天每一个替你找路的地图软件、你叫得出名字的每一张网络,都是普鲁士小城里七座桥的远房后代。

The original document
Original source text

§1 · 位置几何

L. Euler · Commentarii academiae scientiarum Petropolitanae 8 (1741): 128–140 · presented 1735 (E53)
The branch of geometry that deals with magnitudes has been zealously studied throughout the past, but there is another branch that has been almost unknown up to now; Leibniz spoke of it first, calling it the “geometry of position” (geometria situs).
This geometry, Euler explains, is concerned not with measuring lengths or computing quantities but only with how things are positioned and connected. The Königsberg bridge puzzle, he says, seemed to belong to it — and offered a chance to give the almost-empty field a first real method.

§2 · 七座桥

At Königsberg in Prussia, Euler writes, the river Pregel divides the town into regions linked by seven bridges. An island, Kneiphof, sits in the river; he labels the four land regions A, B, C and D, and the seven bridges a, b, c, d, e, f and g.
The question: can one arrange a single journey that crosses each of the seven bridges once and only once? Rather than chase the many possible routes by trial, Euler sets out to decide the matter by a general method.
[ … ]

§§3–13 · 路线化为字母

Euler records a crossing by the sequence of regions it visits: a route is written as a string of capital letters, and crossing one bridge adds one letter. A journey over all seven bridges is therefore a string of eight letters — and a region reached by several bridges must appear several times in that string.
He turns the geography into bookkeeping: if a region is met by an odd number of bridges, he reasons, it must appear a fixed number of times in any complete route — about half the bridge-count, rounded up.
[ … ]

§§14–21 · 计数法则

Summing the required appearances, Euler reaches his criterion. Restated in today's terms: count, for each region, the number of bridges meeting it. If more than two regions have an odd number of bridges, no route crossing every bridge once can exist; if exactly two are odd, a route exists that must begin at one and end at the other; if none is odd, a route exists that returns to its start.
Königsberg's four regions carry 5, 3, 3 and 3 bridges — all four odd. Four odd regions exceed the two that any single journey allows, so the walk is impossible. Euler notes the same rule decides any such network at once, however many bridges it has.
Leonhard Euler · St. Petersburg Academy · presented 1735