图论中的柯尼斯堡七桥问题

如果我们要了解柯尼斯堡桥问题，我们需要了解一些词语，这些词语描述如下：

1. 顶点: 一个点被称为顶点。

2. 边: 图中的一条线被称为边。

3. 图: 点和线的集合被称为图。我们可以借助一个例子来理解它，如下所示

4. 简单路径: 它可以被描述为仅覆盖图的所有顶点一次的路径。我们可以借助一个例子来理解它，如下所示

5. 欧拉路径: 它可以被描述为仅覆盖图的所有边一次的路径。我们可以借助一个例子来理解它，如下所示

6. 度: 它可以被描述为与顶点相连的边的数量。我们可以借助一个例子来理解它，如下所示

柯尼斯堡桥问题

柯尼斯堡桥问题可以被描述为图论领域最早的问题之一。这个问题是发明图论的原因。普鲁士城市柯尼斯堡在18世纪被普雷格尔河分成四个部分。七座桥梁用于连接这个城市的不同区域，如下所示

我们标记城市的每个部分。第一部分位于河流北部大陆上，标记为 A；第二部分位于河流南部大陆上，标记为 B；第三部分位于岛屿上，标记为 C；第四部分位于半岛上，标记为 D (这是右侧的陆地)。我们还将城市的每座桥梁标记为 p、q、r、s、t、u 和 v。

在这个城市里，当地人养成了一个传统，即借助仅穿过每座桥一次的方式来访问城市的全部 4 个部分。在这次尝试和错误中，当地人没有找到这个问题的任何解决方案，但他们也无法证明这是不可能的。

柯尼斯堡的问题是如何解决的

1735 年，有一位名叫伦哈德·欧拉的著名数学家，他证明了借助仅穿过每座桥一次的方式来遍历城市是不可能的。为了证明这一点，他使用了图论的概念，并以图的形式创建了城市的简单表示。在这个表示中，他用点代替了每块陆地，用线代替了桥梁，如下所述

欧拉认为，如果我们想要一次成功的旅程（对于成功的旅程，每条线都必须只访问一次），那么最多应该有两个点通过奇数条线连接。 在这次旅程中，我们使用一个点，以便我们可以前往该点，并使用一个点，以便我们可以从该点离开。

因此，应该始终有偶数条线，以便我们可以仅使用每条线一次。 对于旅程中的每个点，此语句必须为真，除非旅程的开头和最后一个端点，因为旅程的第一个和最后一个点仅使用一条线，无论它们想要朝向终点还是远离起点。 因此，仍然有机会获得成功的旅程，必须满足某些条件，即要么所有点都与偶数条线的帮助相关，要么除了起点和终点之外的所有点都与偶数条线的帮助相关。 如果我们在图中获得一条偶数条线连接所有点的路径，则表示旅程必须在同一点开始和结束。

在柯尼斯堡桥问题中，每块土地都与奇数座桥梁有关。 由于这个原因，不可能获得成功的旅程。 为了理解这一点，我们将举一个例子，从中我们从上面的图中选择点 D。对于点 D，我们使用第一条线，以便我们可以前往它，一条线可以向外横穿，最后一条线可以返回，但之后，我们将被困在点 D，因为所有三条线已在此过程中使用。

注意：如果柯尼斯堡市的当地人尝试创建一座从 A 到 C 的八桥，那么我们检查是否有可能仅穿过所有八座桥梁一次而不游过河？ 答案是肯定的。 如果我们有八座桥，那么有可能只走过所有桥梁一次，因为这座八座桥的图恰好包含两个奇数顶点。

如果柯尼斯堡市的当地人尝试建造九座桥梁，那么与 7 座桥梁相同的问题将再次出现，因为它们包含超过两个奇数顶点。

一些重要点

在完成上述讨论之后，我们知道关于柯尼斯堡问题的一些重要点，这些点描述如下

• 如果图不包含任何奇数个顶点，则该图是可以遍历的。 在这种情况下，我们可以从任何顶点开始我们的路径，但同一个顶点必须是最后一个顶点，这意味着必须有相同的起点和终点顶点。
• 如果图恰好包含两个奇数顶点，则该图是可以遍历的。 在这种情况下，一个奇数顶点用于指示起点，一个奇数顶点用于指示终点。