Untitled Course柯尼斯堡的桥梁

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

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

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

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

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

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

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

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

值

大小

素数

奇偶

这些图可能是:

这些图不可能是:

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

你可以在这个图中看到一个单独的，放大的顶点。

如果我们画出这张图，我们最终会有一条边指向这个顶点，然后另一条边会离开。这使两条边在顶点相交。

也许顶点是一个交叉点而不是一个角。在这种情况下，会有另一条边指向顶点，另一条边则远离顶点。现在我们有了四个边。

在一些图中，甚至可能会有第三对边指向或远离顶点。现在有六个边。

请注意，无论哪种方式，始终有偶数个边在顶点相交。

唯一的两个例外是路径起点和终点的顶点 - 这两个顶点的边数可能是奇数。如果起点和终点相同，则图中的所有顶点都是偶数。

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

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

更改语言