图论中的步行

引言

在本节中，我们可以学习关于行进的内容，但在此之前，我们必须先了解什么是图。只有这样，我们才能轻松理解行进。

什么是图？

图是由非空边集和顶点集组成的。图也可以表示为点和线的图形表示。图的两个线通过点连接。图的顶点用点表示，图的边用线表示。两个顶点通过边连接。在图中，至少使用一条边连接两个顶点。

我们也可以用另一个正式的定义来表示图，如下所示：

图可以表示为 G = (V, E)，其中顶点集由 V 表示，边集由 E 表示。边用于连接图的两个顶点。在本节中，我们将学习行进、行进的类型、行进的示例以及更多内容。

什么是行进？

行进是图中的顶点和边序列的集合。换句话说，它可以被描述为图的遍历，生成一个顶点和边序列，这个序列可以称为该图的行进。在行进中，边和顶点可以重复。在行进中，图中的每个顶点通过使用特定边与下一个顶点连接。

在该序列中，第一个顶点称为起始顶点，最后一个顶点称为结束顶点。行进的长度可以通过计算该行进所覆盖的边的总数来计算。换句话说，如果行进中有 n 个顶点，那么这个行进的长度将是 n-1。我们可以使用符号 |W| 来表示行进 W 的长度。行进也可以描述为由一系列顶点连接起来的有限或无限的边序列。因此，关于行进有两个主要点应该被满足以创建行进，如下所示：

• 行进可以包含重复的顶点。
• 行进可以包含重复的边。

图可以有两种类型：有向图和无向图。我们可以在这两种类型的图中找到行进。在无向图中，边没有方向，所以我们可以朝任何方向走，但在有向图中，边有方向，我们必须沿着边从一个顶点走到另一个顶点。现在，我们通过下面的示例分别理解这两种图：

无向图中的行进

此示例包含一个无向图，我们需要找出该图的所有可能行进。

解决方案：在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = 1 → 2 → 3 → 4 → 6

W2 = 3 → 4 → 6 → 3

W3 = 1 → 2 → 5 → 6 → 4

W4 = 1 → 5 → 2 → 3 → 4 → 6 → 3 → 2 → 1

现在，我们检查哪个序列是行进，哪个不是行进，并进行解释。

• W1 是行进（因为这个序列不包含任何重复的顶点和边。这个行进的长度是 4）。
• W2 是行进（因为这个序列不包含任何重复的顶点和边。这个行进的长度是 3）。
• W3 不是路径（因为在这个序列中，顶点 5 和 6 之间没有直接的边）。
• W4 是行进（因为这个序列不包含任何重复的顶点和边。这个行进的长度是 8）。

因此，W1、W2 和 W4 是行进。

有向图中的行进

此示例包含一个有向图，我们需要找出该图的所有可能行进。

解决方案：在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = A → B → C → F → E

W2 = A → E → C

W3 = A → D → E → F → B

现在，我们检查哪个序列是行进，哪个不是行进，并进行解释。

• W1 不是行进（因为这个序列不包含从顶点 F 到顶点 E 的边）。
• W2 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 2）。
• W3 不是路径（因为在这个序列中，顶点 F 和 B 之间没有直接的边）。

因此，W2 是行进。

行进的类型

行进可以有两种类型，描述如下：

1. 开行（Open Walk）

如果一个序列的起始顶点和结束顶点不相同，那么我们可以称这种类型的行进为开行。这意味着在开行的情况下，起始顶点和结束顶点必须不同。如果我们试图找出开行的长度，那么它应该大于 0。我们可以通过一个例子来理解开行，描述如下：

在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = 3 → 1 → 5 → 1 → 4（这个行进的长度是 4）

W2 = 2 → 1 → 4（这个行进的长度是 2）

W3 = 3 → 1 → 2 → 1 → 5（这个行进的长度是 4）

在以上所有序列中，起始顶点和结束顶点不相同。因此，所有行进都是开行。

2. 闭行（Closed Walk）

如果一个序列的起始顶点和结束顶点相同，那么我们可以称这种类型的行进为闭行。这意味着在闭行的情况下，起始顶点和结束顶点必须相同。如果我们试图找出闭行的长度，那么它应该大于 0。我们可以通过一个例子来理解闭行，描述如下：

在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = 1 → 2 → 4 → 5 → 3 → 1（这个行进的长度是 5）

W2 = 2 → 3 → 5 → 4 → 2（这个行进的长度是 4）

W3 = 1 → 2 → 3 → 1（这个行进的长度是 3）

W4 = 4 → 5 → 2 → 4（这个行进的长度是 3）

在以上所有序列中，起始顶点和结束顶点相同。因此，所有行进都是闭行。

注意：有一些与行进相关的重要信息，如下所示：

• 如果我们发现行进的长度大于 0，那么我们可以称这种类型的行进为平凡行进。
• 在行进的情况下，边和顶点可以重复。在这里，行进是开行还是闭行并不重要，但边和顶点可以重复。

行进示例

行进有很多例子，其中一些如下所示：

示例 1

此示例包含一个图，我们需要找出该图的行进。

解决方案：在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = 42 → 50 → 59 → 66 → 72

W2 = 34 → 42 → 34 → 28

W3 = 66 → 72 → 59 → 50

W4 = 28 → 34 → 42 → 50 → 59 → 50 → 72

现在，我们检查哪个序列是行进，哪个不是行进，并进行解释。

• W1 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 4）。
• W2 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 3）。
• W3 不是行进（因为在这个序列中，顶点 72 和顶点 59 之间没有直接的边）。
• W4 不是行进（因为在这个序列中，顶点 50 和顶点 72 之间没有直接的边）。

因此，W1 和 W2 是行进。

示例 2

此示例包含一个图，我们需要找出该图的行进。

解决方案：在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = 0 → 1 → 2 → 3 → 0

W2 = 1 → 2 → 4 → 5 → 6 → 4 → 2

W3 = 4 → 5 → 6 → 7 → 6

W4 = 4 → 5 → 6 → 4

现在，我们检查哪个序列是行进，哪个不是行进，并进行解释。

• W1 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 4）。
• W2 不是行进（因为在这个序列中，没有边可以从顶点 4 到达 2。我们只能从 2 到 4）。
• W3 不是行进（因为在这个序列中，没有边可以从顶点 7 到达 6。我们只能从 6 到 7）。
• W4 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 3）。

因此，W1 和 W4 是行进。

示例 3

此示例包含一个图，我们需要找出该图的行进。

解决方案：在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = A → B → E → C → B → E → D

W2 = A → E → D → A

W3 = A → B → C → E

W4 = C → B → E → A

现在，我们检查哪个序列是行进，哪个不是行进，并进行解释。

• W1 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 6）。
• W2 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 3）。
• W3 不是行进（因为在这个序列中，没有边可以从顶点 B 到 C 和 C 到 E，但反之亦然）。
• W4 不是行进（因为在这个序列中，没有边可以从顶点 E 到 A）。

因此，W1 和 W2 是行进。

示例 4

此示例包含一个图，我们需要找出该图的行进。

解决方案：在上面的图中，可以创建不止一种行进。现在我们展示该图的一些可能行进，描述如下：

W1 = a → b → d → f → d → e → b → a

W2 = a → c → a → b → e

W3 = b → e → d → f → e

W4 = b → a → c → e

现在，我们检查哪个序列是行进，哪个不是行进，并进行解释。

• W1 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 7）。
• W2 是行进（因为这个序列包含重复的顶点和边。这个行进的长度是 4）。
• W3 不是行进（因为在这个序列中，没有边可以从顶点 f 到 e）。
• W4 不是行进（因为在这个序列中，没有边可以从顶点 c 到 e）。

因此，W1 和 W2 是行进。