aiwiki.page
中文
数学 / 离散数学与逻辑 / seven-bridges-of-konigsberg

柯尼斯堡七桥问题

柯尼斯堡七桥问题是一道历史悠久的路线规划难题,欧拉证明其无解,为图论的建立奠定了基础。

11 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
莱昂哈德·欧拉图论几何学拓扑学度(图论)数学证明算法旅行商问题柯尼斯堡七…

柯尼斯堡七桥问题是一道数学问题:能否在柯尼斯堡城中走出一条路线,恰好经过城内七座桥各一次?1736 年,莱昂哈德·欧拉证明,即使允许终点与起点不同,这样的路线也不存在。他的解法用连接关系构成的结构取代了具体的地理细节,使这道问题成为图论的奠基性范例。

历史背景

柯尼斯堡是普鲁士的一座城市,即今加里宁格勒,沿普雷格尔河(今称普列戈利亚河)的各条支流发展起来。当时的布局涉及四块陆地:北岸、南岸,以及克奈普霍夫岛和洛姆瑟岛。七座桥将这四块陆地连接起来。

问题是,一个人能否走遍全部七座桥,而不重复经过任何一座。在同一块陆地内可以自由行走,但往来不同陆地之间必须经过桥梁。不允许游泳、乘船,或以其他方式绕开桥梁过河。

欧拉在拉丁文论文 Solutio problematis ad geometriam situs pertinentis 中研究了这道问题,论文标题意为“一个与位置几何有关的问题的解答”。这项工作通常被定年为 1736 年;论文实际于 1741 年刊印,收录在圣彼得堡科学院一卷标注较早年份的学报中。

Geometria situs 一词所指的是对空间关系的研究,有别于以测量为基础的几何学。欧拉的论证也与拓扑学的历史发展有关,不过按照现代术语,这道问题最直接地归属于图论。

用图表示

关键的简化在于忽略距离、桥梁长度、街道布局和岛屿的精确形状,只考虑每座桥连接的是哪两块陆地。

用一个顶点表示每块陆地,用一条连接相应顶点的边表示每座桥。由于某些陆地之间不止有一座桥,得到的结构是一个多重图,即允许同一对顶点之间存在多条边的图。

设:

  • KK 表示克奈普霍夫岛;
  • LL 表示洛姆瑟岛;
  • NN 表示北岸;
  • SS 表示南岸。

七条边为:

KN, KN, KS, KS, KL, LN, LS.KN,\ KN,\ KS,\ KS,\ KL,\ LN,\ LS.

重复出现的顶点对表示不同的桥,而不是重复经过同一座桥。

顶点的度(图论)是与该顶点关联的边端数。因此,柯尼斯堡图中各顶点的度如下:

陆地 顶点 度
克奈普霍夫岛 KK 5
洛姆瑟岛 LL 3
北岸 NN 3
南岸 SS 3

四个顶点的度均为奇数。

用现代术语来说,所求的路线是一条欧拉通路:恰好经过每条边一次的游走。顶点可以重复经过。如果这条路线还回到起始顶点,就称为欧拉回路。

为什么这样的路线不可能存在

论证的核心在于进入和离开一块陆地的方式。

每当行走者经由一座桥到达途中经过的某块陆地,就必须经由另一座尚未走过的桥离开。因此,在这块陆地上使用的桥总是以“进入—离开”的方式成对出现。

由此可分为两种情况:

  • 路线的起点和终点是同一个顶点。 每次进入都与一次离开配对,因此每个顶点的度都必须为偶数。
  • 路线的起点和终点是不同顶点。 起点有一次未配对的离开,终点有一次未配对的进入。这两个顶点的度为奇数,其余所有顶点的度均为偶数。

因此,恰好经过每条边一次的路线,只可能有零个或两个奇度顶点,不可能有四个。

柯尼斯堡图中各顶点的度为

5, 3, 3, 3,5,\ 3,\ 3,\ 3,

所以它有四个奇度顶点。因此,无论从哪里出发,所要求的路线都不可能存在。

这一数学证明无需逐一检验七座桥所有可能的经过顺序。其结论只取决于连接关系,而不取决于具体选择哪条路线。

欧拉通路的一般判定条件

对于至少有一条边的有限无向图,存在欧拉通路的充要条件是:

  1. 所有与边关联的顶点都属于同一个连通分量;
  2. 奇度顶点的个数为零或二。

如果没有奇度顶点,就存在欧拉回路。如果恰有两个奇度顶点,就存在欧拉通路,且它必须从其中一个奇度顶点出发,在另一个奇度顶点结束。

连通性条件不可或缺。两个彼此分离的回路可以只有偶度顶点,但若不增加连接,就不可能用一条路线走遍二者。

“进入—离开”的配对论证说明了度数条件的必要性。充分性则可以通过构造来证明。在所有顶点的度均为偶数的连通图中,沿尚未使用的边前进,直到形成一条闭合迹。如果仍有未使用的边,连通性就保证已有迹上的某个顶点与未使用的边关联。从该顶点出发再构造一条闭合迹,并将其插入原来的迹中。反复进行这一过程,最终就能用尽所有边。

如果恰有两个顶点的度为奇数,就暂时添加一条连接它们的边。这样,所有顶点的度都变成偶数。构造一条欧拉回路,再删去新增的边;余下的序列就是连接这两个奇度顶点的欧拉通路。

这一构造方法是高效寻找欧拉通路的算法的基础。

改变桥梁布局

将问题表示为图后,就可以分析修改后的问题,而不必通过反复试错来重新寻找整条路线。

拆除一座桥

删除一条边会使其两个端点的度各减一。在原图中,这两个端点的度都是奇数,因此都会变成偶数。另外两个顶点的度则仍为奇数。

对于这个特定的图,拆除任意一座桥后,图仍然连通。因此,剩下的六座桥存在欧拉通路,但不存在欧拉回路。

增加一座桥

在两块不同陆地之间增加一座桥,会改变两个端点度数的奇偶性。由于原来四个顶点的度均为奇数,受影响的两个顶点的度会变成偶数,另外两个则仍为奇数。

因此,得到的八桥图存在欧拉通路,但仍不存在欧拉回路。

允许一座桥经过两次

如果放宽要求,允许其中一座桥经过两次,那么只要起点与终点可以不同,就能找到一条共过桥八次的路线。

在数学上,重复过桥可用复制一条边来表示。这会使两个奇度顶点变成偶度顶点,留下恰好两个奇度顶点。扩充后的图中的一条欧拉通路,就对应着在实际桥梁上行走的所需路线。

若要形成闭合路线,就还需要增加重复过桥的次数,因为所有顶点的度都必须为偶数。

数学意义与应用

这道问题的重要性在于其抽象方法:一个地理谜题被转化为关于顶点、边、连通性和奇偶性的问题。同样的推理也适用于实际形态完全不同的网络。

它的推广包括路线巡检问题,也称中国邮递员问题。该问题要求寻找一条最短的闭合路线,使其至少经过网络中的每条边一次。如果原本不存在欧拉回路,就必须重复经过某些边;优化的目标是以最低代价选择这些重复经过的边。这在道路巡检、街道清扫以及其他必须覆盖网络各条连接的服务中都有应用。

这类要求遍历所有边的问题不同于旅行商问题,后者要求在访问指定地点的同时,使总行程成本最小。柯尼斯堡问题要求恰好经过每座桥一次,而不是恰好到访每块陆地一次。重复到访同一块陆地是允许的,而且往往不可避免。

历史上的结论适用于最初的七桥布局。此后城市桥梁的变化会产生不同的图,因此需要重新分析其连通性和顶点的度。