柯尼斯堡七桥问题是一道数学问题:能否在柯尼斯堡城中走出一条路线,恰好经过城内七座桥各一次?1736 年,莱昂哈德·欧拉证明,即使允许终点与起点不同,这样的路线也不存在。他的解法用连接关系构成的结构取代了具体的地理细节,使这道问题成为图论的奠基性范例。
历史背景
柯尼斯堡是普鲁士的一座城市,即今加里宁格勒,沿普雷格尔河(今称普列戈利亚河)的各条支流发展起来。当时的布局涉及四块陆地:北岸、南岸,以及克奈普霍夫岛和洛姆瑟岛。七座桥将这四块陆地连接起来。
问题是,一个人能否走遍全部七座桥,而不重复经过任何一座。在同一块陆地内可以自由行走,但往来不同陆地之间必须经过桥梁。不允许游泳、乘船,或以其他方式绕开桥梁过河。
欧拉在拉丁文论文 Solutio problematis ad geometriam situs pertinentis 中研究了这道问题,论文标题意为“一个与位置几何有关的问题的解答”。这项工作通常被定年为 1736 年;论文实际于 1741 年刊印,收录在圣彼得堡科学院一卷标注较早年份的学报中。
Geometria situs 一词所指的是对空间关系的研究,有别于以测量为基础的几何学。欧拉的论证也与拓扑学的历史发展有关,不过按照现代术语,这道问题最直接地归属于图论。
用图表示
关键的简化在于忽略距离、桥梁长度、街道布局和岛屿的精确形状,只考虑每座桥连接的是哪两块陆地。
用一个顶点表示每块陆地,用一条连接相应顶点的边表示每座桥。由于某些陆地之间不止有一座桥,得到的结构是一个多重图,即允许同一对顶点之间存在多条边的图。
设:
- 表示克奈普霍夫岛;
- 表示洛姆瑟岛;
- 表示北岸;
- 表示南岸。
七条边为:
重复出现的顶点对表示不同的桥,而不是重复经过同一座桥。
顶点的度(图论)是与该顶点关联的边端数。因此,柯尼斯堡图中各顶点的度如下:
| 陆地 | 顶点 | 度 |
|---|---|---|
| 克奈普霍夫岛 | 5 | |
| 洛姆瑟岛 | 3 | |
| 北岸 | 3 | |
| 南岸 | 3 |
四个顶点的度均为奇数。
用现代术语来说,所求的路线是一条欧拉通路:恰好经过每条边一次的游走。顶点可以重复经过。如果这条路线还回到起始顶点,就称为欧拉回路。
为什么这样的路线不可能存在
论证的核心在于进入和离开一块陆地的方式。
每当行走者经由一座桥到达途中经过的某块陆地,就必须经由另一座尚未走过的桥离开。因此,在这块陆地上使用的桥总是以“进入—离开”的方式成对出现。
由此可分为两种情况:
- 路线的起点和终点是同一个顶点。 每次进入都与一次离开配对,因此每个顶点的度都必须为偶数。
- 路线的起点和终点是不同顶点。 起点有一次未配对的离开,终点有一次未配对的进入。这两个顶点的度为奇数,其余所有顶点的度均为偶数。
因此,恰好经过每条边一次的路线,只可能有零个或两个奇度顶点,不可能有四个。
柯尼斯堡图中各顶点的度为
所以它有四个奇度顶点。因此,无论从哪里出发,所要求的路线都不可能存在。
这一数学证明无需逐一检验七座桥所有可能的经过顺序。其结论只取决于连接关系,而不取决于具体选择哪条路线。
欧拉通路的一般判定条件
对于至少有一条边的有限无向图,存在欧拉通路的充要条件是:
- 所有与边关联的顶点都属于同一个连通分量;
- 奇度顶点的个数为零或二。
如果没有奇度顶点,就存在欧拉回路。如果恰有两个奇度顶点,就存在欧拉通路,且它必须从其中一个奇度顶点出发,在另一个奇度顶点结束。
连通性条件不可或缺。两个彼此分离的回路可以只有偶度顶点,但若不增加连接,就不可能用一条路线走遍二者。
“进入—离开”的配对论证说明了度数条件的必要性。充分性则可以通过构造来证明。在所有顶点的度均为偶数的连通图中,沿尚未使用的边前进,直到形成一条闭合迹。如果仍有未使用的边,连通性就保证已有迹上的某个顶点与未使用的边关联。从该顶点出发再构造一条闭合迹,并将其插入原来的迹中。反复进行这一过程,最终就能用尽所有边。
如果恰有两个顶点的度为奇数,就暂时添加一条连接它们的边。这样,所有顶点的度都变成偶数。构造一条欧拉回路,再删去新增的边;余下的序列就是连接这两个奇度顶点的欧拉通路。
这一构造方法是高效寻找欧拉通路的算法的基础。
改变桥梁布局
将问题表示为图后,就可以分析修改后的问题,而不必通过反复试错来重新寻找整条路线。
拆除一座桥
删除一条边会使其两个端点的度各减一。在原图中,这两个端点的度都是奇数,因此都会变成偶数。另外两个顶点的度则仍为奇数。
对于这个特定的图,拆除任意一座桥后,图仍然连通。因此,剩下的六座桥存在欧拉通路,但不存在欧拉回路。
增加一座桥
在两块不同陆地之间增加一座桥,会改变两个端点度数的奇偶性。由于原来四个顶点的度均为奇数,受影响的两个顶点的度会变成偶数,另外两个则仍为奇数。
因此,得到的八桥图存在欧拉通路,但仍不存在欧拉回路。
允许一座桥经过两次
如果放宽要求,允许其中一座桥经过两次,那么只要起点与终点可以不同,就能找到一条共过桥八次的路线。
在数学上,重复过桥可用复制一条边来表示。这会使两个奇度顶点变成偶度顶点,留下恰好两个奇度顶点。扩充后的图中的一条欧拉通路,就对应着在实际桥梁上行走的所需路线。
若要形成闭合路线,就还需要增加重复过桥的次数,因为所有顶点的度都必须为偶数。
数学意义与应用
这道问题的重要性在于其抽象方法:一个地理谜题被转化为关于顶点、边、连通性和奇偶性的问题。同样的推理也适用于实际形态完全不同的网络。
它的推广包括路线巡检问题,也称中国邮递员问题。该问题要求寻找一条最短的闭合路线,使其至少经过网络中的每条边一次。如果原本不存在欧拉回路,就必须重复经过某些边;优化的目标是以最低代价选择这些重复经过的边。这在道路巡检、街道清扫以及其他必须覆盖网络各条连接的服务中都有应用。
这类要求遍历所有边的问题不同于旅行商问题,后者要求在访问指定地点的同时,使总行程成本最小。柯尼斯堡问题要求恰好经过每座桥一次,而不是恰好到访每块陆地一次。重复到访同一块陆地是允许的,而且往往不可避免。
历史上的结论适用于最初的七桥布局。此后城市桥梁的变化会产生不同的图,因此需要重新分析其连通性和顶点的度。