词汇表

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

柯尼斯堡的桥梁

阅读时间: ~15 min

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

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

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

Map 1

Map 2

Map 3

Map 4

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

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

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

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

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

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

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

These graphs are not possible:

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

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

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

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

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