词汇表

选择左侧的一个关键字...

Untitled Course柯尼斯堡的桥梁

阅读时间: ~10 min

Leonhard Euler是最早考虑图和网络的数学家之一。欧拉对波罗的海附近的柯尼斯堡(Königsberg)镇的一个老问题深感兴趣。

普雷格尔河将柯尼斯堡(Königsberg)分为四个独立的部分,由七个桥相连。是否可以一次穿越所有桥梁在城市中漫步-但不能超过一次? (您可以在任何地方开始和结束,而不必在同一地方。)

尝试通过在以下地图上绘制来找到有效的路线:

Map 1

Map 2

Map 3

Map 4

对于柯尼斯堡(Königsberg)来说,似乎不可能找到有效的路线,但其他一些城市也可以使用。欧拉设法使用图论找到了一条适用于任何城市的简单规则,而无需尝试很多可能性。

首先,我们需要将城市地图转换为带有边和顶点的图。每个岛屿或陆地区域都由表示, 和两个区域连接的每个桥都由相应的表示 。

现在,“在一次穿越每座桥梁的同时精确地游览城市”的问题已成为“在连续追踪每条边缘一次的同时绘制一个连续笔划的图”的问题。

在纸上,拿出一些不同的图,然后尝试找出可以用一笔连续绘制的图。

就像以前的城市地图一样,我们发现有些图是有可能的,而其他图则没有。为了帮助我们理解原因,让我们用度数标记每个顶点。然后,我们可以以不同的方式为顶点着色,并尝试揭示一个图案:

大小
素数
奇偶

这些图可能是:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

这些图不可能是:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

将这些数字与可能的图和不可能的图进行比较,看起来似乎如果一个图有那么它就能一笔绘制出来 。如果我们只看图中的一个顶点,就可以解释这种情况:

你可以在这个图中看到一个单独的,放大的顶点。
如果我们画出这张图,我们最终会有一条边指向这个顶点,然后另一条边会离开。这使两条边在顶点相交。
也许顶点是一个交叉点而不是一个角。在这种情况下,会有另一条边指向顶点,另一条边则远离顶点。现在我们有了四个边。
在一些图中,甚至可能会有第三对边指向或远离顶点。现在有六个边。
请注意,无论哪种方式,始终有偶数个边在顶点相交。
唯一的两个例外是路径起点和终点的顶点 - 这两个顶点的边数可能是奇数。如果起点和终点相同,则图中的所有顶点都是偶数。

如果您滚动回柯尼斯堡(Königsberg)地图,将会发现有两个以上的岛,桥的数量奇数。因此,确实不可能一次只穿过每座桥梁的路线–这就是伦纳德·欧拉(Leonard Euler)所发现的。

欧拉的发现在现实生活中似乎并不是特别有用,但是图表是许多其他地理问题(例如在两个位置之间找到方向)的基础。稍后我们将发现更多这类应用。

Archie