图论中的路径

引言

如果我们想了解路径，我们必须先了解什么是图。之后，我们就可以轻松地理解路径了。

什么是图？

图是由非空边集和顶点集组成的集合。图也可以表示为点和线的图形表示。图的顶点用点表示，图的边用线表示。图的两条线通过点连接。

换句话说，两个顶点通过一条边连接。在图中，至少有一条边用于连接两个顶点。我们还可以用另一个更正式的定义来表示图，如下所示：

图可以表示为 G = (V, E)，其中顶点集用 V 表示，边集用 E 表示。边用于连接图中的两个顶点。在本节中，我们将学习路径、路径的定义、路径的性质、路径的例子等等。

什么是路径？

路径是图中顶点和边序列的集合。换句话说，它可以被描述为一种“游走”，其中图的边和顶点不应重复。路径可以包含起始和最后一个顶点可能相同的这种情况。除了第一个和最后一个位置的顶点外，序列中的任何其他顶点都不能相同。换句话说，路径可以描述为由顶点序列连接的有限或无限的边序列。

路径也可以解释为一种图，其中起始和最后一个顶点的度为1，所有其余顶点的度为2。可以有开路径和闭路径。如果路径的起始顶点和最后一个顶点相同，则称为闭合路径。如果路径的起始顶点和最后一个顶点不相同，则称为开路径。因此，在图中查找路径时，有两个重要点，如下所示：

• 图的顶点不应重复。
• 图的边不应重复。

我们可以通过一个例子来理解路径，如下所述：

在上图中，可以通过两种方式创建路径，使得此图的顶点和边不重复，它们描述如下：

P1 = v1 - (e1) - v2 - (e2) - v3 或，

v1 → v2 → v3

P2 = v1 - (e1) - v2 - (e3) - v4 - (e4) - v3 或，

v1 → v2 → v4 → v3

双向路径 (Bipath)

如果一个图有有向边，那么这种图的路径称为双向路径。双向路径应包含所有相同方向的边。边的数量可以计算路径中路径的长度。我们可以使用符号 |P| 来表示路径 P 的长度。我们可以通过一个例子来理解双向路径，如下所述：

从上图中生成的路径是双向路径。通过三种方式创建双向路径，使得此图的顶点和边不重复，它们描述如下：

P1 = v1 - (e1) - v2 - (e2) - v3 - (e3) - v4 或，

v1 → v2 → v3 → v4

P2 = v1 - (e1) - v2 - (e4) - v5 或，

v1 → v2 → v5

P3 = v6 - (e5) - v5 或，

v6 → v5

路径的定义

假设有一个有向图 G (V, E)，其中顶点集用 V 表示，边集用 E 表示。如果两个顶点 x 和 y 之间存在简单路径，它可以表示为顶点序列 (y1, y2, y3, …, yn)，那么这个路径必须满足一些条件，如下所示：

• 所有顶点 y_i 都用于表示顶点集 V，其中 (1 ≤ i ≤ k)。
• x = y₁, y = y_k
• 如果存在两个连续的顶点 (y_i, y_i+1)，则它必须包含一条边 e = (y_i, y_i+1)，该边存在于边集 E 中。
• 图中不应包含序列中重复的任何顶点。换句话说，在简单图的情况下不应存在任何环。

现在，我们将使用一个例子来理解相关的图，如下所示：

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• 第一条路径 P1 = 1 → 2 → 3 → 4
• 第二条路径 P2 = 1 → 2 → 3 → 5 → 4
• 第三条路径 P3 = 1 → 3 → 2
• 第四条路径 P4 = 1 → 3 → 4
• 第五条路径 P5 = 1 → 3 → 4 → 5 → 4

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P1 是路径（第一个序列是路径，因为它不包含任何重复的顶点和边）
• P2 是路径（第二个序列是路径，因为它不包含任何重复的顶点和边。）
• P3 不是路径（第三个序列不是路径，因为它不包含从顶点 3 到顶点 2 的任何边。）
• P4 是路径（第四个序列是路径，因为它不包含任何重复的顶点和边。）
• P5 不是路径（第五个序列不是路径，因为它包含重复的顶点 4）。

因此，除了 P3 和 P5 之外，所有其他路径都是简单的，因为它们不包含任何重复的顶点和边。

因此，P1、P2 和 P4 是路径。

路径的性质

路径包含很多性质，其中一些如下所示：

• 如果图中存在包含每对顶点的路径，则该类型的图称为连通图。
• 如果一个有向图中存在包含每对顶点的相反方向的路径，则该类型的图称为强连通图。
• 如果存在一条路径，其中图的边不连接两个非连续的路径顶点，则该类型的路径称为诱导路径。
• 如果图中存在两条不包含任何内部边或顶点的公共部分的路径，则这些路径称为顶点不相交。同样，如果图中存在两条不包含任何公共边的路径，则这些路径称为边不相交。
• 如果存在两条内部不相交的路径，则它们称为边不相交，但如果我们尝试反过来，则不一定正确。
• 如果我们想计算图中路径的长度，那么我们必须计算路径中的边数。如果图包含两个顶点之间的一条或多条路径，那么我们可以计算两个顶点之间的距离，这可以称为它们之间最短路径的长度。如果从两个顶点中移除一个顶点，则图的距离将变为无穷大。
• 在连通图的情况下，我们可以通过计算顶点对之间的最长距离来找到其直径。

查找路径

在图中，我们可以通过各种算法来查找最短路径和最长路径。最著名的算法是Dijkstra 算法、Bellman-Ford 算法和 Floyd-Warshall 算法。

1. Dijkstra 算法： Dijkstra 算法用于查找从起始顶点到图中每个顶点的最短路径列表。此算法可应用于有向图和无向图，具有带权或无权边。如果图包含带权边，则权重必须是非负数。
2. Bellman-Ford 算法： Bellman-Ford 算法也用于查找从单个起始顶点到图中每个顶点的最短路径列表。此算法可应用于带权边的有向图。Bellman-Ford 算法比 Dijkstra 算法慢。如果一个图中的某些边包含负数，在这种情况下，我们可以使用 Bellman-Ford 算法。
3. Ford-Warshall 算法： 通过Ford-Warshall 算法，我们可以计算所有顶点对之间的最短路径。此算法可应用于带权边的有向图。此算法可用于存在正或负边权重的情况，但图中不应存在任何负环。

路径示例

路径可以有很多例子，其中一些如下所示：

示例 1

此示例包含一个图，我们需要找到该图的路径。

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• 第一条路径 P1 = 1 → 2 → 4 → 5
• 第二条路径 P2 = 4 → 1 → 2 → 4
• 第三条路径 P3 = 1 → 2 → 4 → 5 → 4

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P1 是路径（第一个序列是路径，因为它不包含任何重复的顶点和边）
• P2 是闭合路径（第二个序列是路径，因为它不包含除起始和结束边之外的任何重复顶点和边。这是一条闭合路径）
• P3 不是路径（第三个序列是路径，因为在这个序列中，我们有一个重复的顶点 4）

因此，P1 和 P2 是路径。

示例 2

此示例包含一个图，我们需要找到该图的路径。

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• 第一条路径 P1 = 1 → 0 → 2
• 第二条路径 P2 = 4 → 3 → 0 → 2 → 1
• 第三条路径 P3 = 3 → 0 → 1 → 2 → 0

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P1 是路径（因为这个序列不包含任何重复的顶点和边）
• P2 是路径（因为这个序列不包含任何重复的顶点和边）
• P3 不是路径（因为在这个序列中，我们有一个重复的顶点 0）

示例 3

此示例包含一个图，我们需要找到该图的路径。

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• 第一条路径 P1 = 1 → 2 → 3
• 第二条路径 P2 = P2 = 3 → 2 → 1

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P1 是路径（因为这个序列不包含任何重复的顶点和边）
• P3 不是路径（因为在这个序列中，顶点 3 和 2 之间，以及 2 和 1 之间没有直接边）

因此，P1 是一条路径。

示例 4

此示例包含一个图，我们需要找到该图的路径。

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• 第一条路径 P1 = 1 → 3 → 2 → 1 → 5
• 第二条路径 P2 = 3 → 2 → 1 → 4
• 第三条路径 P3 = 5 → 1 → 3 → 2 → 4
• 第四条路径 P4 = 4 → 3 → 2 → 1 → 5

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P1 不是路径（因为这个序列包含重复的边 1）
• P2 是路径（因为这个序列不包含任何重复的顶点和边）
• P3 不是路径（因为在这个序列中，顶点 2 和 4 之间没有边）
• P4 是路径（因为这个序列不包含任何重复的顶点和边）

因此，P2 和 P4 是路径。

示例 5

此示例包含一个图，我们需要找到该图的路径。

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• P1 = 42 → 50 → 59 → 66 → 72
• P2 = 34 → 42 → 59 → 66
• P3 = 59 → 66 → 72 → 59 → 50
• P4 = 28 → 34 → 42 → 50 → 59

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P2 是路径（因为这个序列不包含任何重复的顶点和边）
• P1 不是路径（因为在这个序列中，顶点 42 和顶点 59 之间没有直接边）
• P3 不是路径（因为在这个序列中，我们有一个重复的顶点 59，并且顶点 72 和 59 之间没有有向边）
• P4 是路径（因为这个序列不包含任何重复的顶点和边）

因此，P1 和 P4 是路径。

示例 6

此示例包含一个图，我们需要找到该图的路径。

解：在上图中，可以创建多个路径。现在我们展示一些此图的可能路径，描述如下：

• P1: V6 → V5 → V3 → V1
• P2: V2→ V4 → V1 → V3 → V5 → V6 → V2
• P3: V4 → V2 → V3 → V6 → V5 → V3 → V1

现在，我们检查哪个序列是路径，哪个不是路径，并附带解释。

• P2 是路径（因为这个序列不包含任何重复的顶点和边）
• P1 是路径（因为这个序列不包含任何重复的顶点和边。它是一个闭合路径，因为这个路径的起始和结束顶点是相同的。）
• P3 不是路径（因为在这个序列中，我们有一个重复的顶点 V3）

因此，P1 和 P2 是路径。