离散数学中的行走、路径、路径、回路和圈

Walk（走）

行走（Walk）可以定义为图的边和顶点的序列。当我们有一个图并遍历它时，这个遍历就被称为一次行走。在一次行走中，可以重复出现边和顶点。行走所覆盖的边数称为行走的长度。在一个图中，可以有多条不同的行走。

因此，对于一次行走，以下两点很重要，描述如下：

• 边可以重复
• 顶点可以重复

例如：在此示例中，我们有一个图，描述如下：

在上图中，可以存在许多行走，但其中一些描述如下：

行走类型

行走有两种类型，描述如下：

1. 开放行走（Open walk）
2. 封闭行走（Closed walk）

开放行走

如果行走开始和结束的顶点不同，则在图论中将该行走称为开放行走。这意味着对于开放行走，起始顶点和结束顶点必须不同。在开放行走中，行走长度必须大于 0。

封闭行走

如果行走开始和结束的顶点相同，则在图论中将该行走称为封闭行走。这意味着对于封闭行走，起始顶点和结束顶点必须相同。在封闭行走中，行走长度必须大于 0。

注意：有一些重要的点需要我们学习：

• 如果行走长度为 0，则该行走称为平凡行走（Trivial walk）。
• 在开放行走和封闭行走的情况下，边和顶点都可以重复。

假设有一个图，描述如下：

在此图中，也有一个封闭行走和一个开放行走，描述如下：

路径（Trails）

路径（Trail）可以描述为一种开放行走，其中不允许重复任何边。在路径中，顶点可以重复。

因此，对于路径，以下一点很重要，描述如下：

• 顶点可以重复

在上图中，有一个路径和封闭路径，描述如下：

电路

回路（Circuit）可以描述为一种封闭行走，不允许重复任何边。在回路中，顶点可以重复。在图论中，封闭路径也被称为回路。

因此，对于回路，以下两点很重要，描述如下：

• 边不能重复
• 顶点可以重复

在上图中，有一个回路，描述如下：

环

在图论中，封闭路径也称为圈（Cycle）。圈是一种封闭行走，不允许重复边和顶点。只有起始顶点和结束顶点相同的可能性才算圈。

因此，对于圈，以下两点很重要，描述如下：

• 边不能重复
• 顶点不能重复

在上图中，有一个圈，描述如下：

路径

路径（Path）是一种开放行走，不允许重复边和顶点。只有起始顶点和结束顶点相同的可能性才算路径。在开放行走中，行走长度必须大于 0。

因此，对于路径，以下两点很重要，描述如下：

• 边不能重复
• 顶点不能重复

在上图中，有一个路径，描述如下：

注意：有一些重要的点需要我们学习：

• 在离散数学中，每一条路径都可以是一条路径（Trail），但并非每一条路径（Trail）都是一条路径（Path）。
• 在离散数学中，每一个圈都可以是一个回路（Circuit），但并非每一个回路（Circuit）都是一个圈（Cycle）。
• 如果是一个有向图，我们需要在上述所有定义前加上“有向”一词。
• 在行走和路径中，考虑了各种图论概念。例如，假设我们有一个图并想确定两个顶点之间的距离。在这种情况下，将考虑最短路径，它从一个顶点开始并以另一个顶点结束。这里的路径长度等于图中的边数。

重要图表

可以借助以下图表轻松记住上述定义。

行走示例

行走的各种示例描述如下：

示例 1：在此示例中，我们将考虑一个图。

现在我们需要找出哪些顶点序列决定了行走。序列描述如下：

1. A, B, G, F, C, D
2. B, G, F, C, B, G, A
3. C, E, F, C
4. C, E, F, C, E
5. A, B, F, A
6. F, D, E, C, B

对于那些是行走的序列，我们还需要确定它是否是圈、路径、回路或迹。

解答：在上图中，A、B、C、D、E、F 和 G 是顶点，两个顶点之间的连线是边，即 A 和 B 之间的连线是一条边。为了解决这个问题，我们将首先确定序列 1。之后，我们将继续处理下一个。

1. 序列 1 是一个路径（Trail），因为序列 ABGFCB 中没有重复的边。
2. 序列 2 是一个行走（Walk），因为序列 BGFCBGA 包含重复的边和顶点。
3. 序列 3 是一个圈（Cycle），因为序列 CEFC 中除了起始顶点 C 之外，不包含任何重复的顶点或边。
4. 序列 4 是一个行走（Walk），因为序列 CEFCE 包含重复的边和顶点。
5. 序列 5不是行走（Walk），因为没有直接的路径可以从 B 到 F。这就是为什么我们可以说序列 ABFA 不是行走。
6. 序列 6 是一个路径（Path），因为序列 FDECB 不包含任何重复的边和顶点。

示例 2：在此示例中，我们将考虑一个图。

根据以下序列，我们需要确定每种情况下的行走性质：

1. v1, e1, v2, e2, v3, e2, v2
2. v4, e7, v1, e1, v2, e2, v3, e3, v4, e4, v5
3. v1, e1, v2, e2, v3, e3, v4, e4, v5
4. v1, e1, v2, e2, v3, e3, v4, e7, v1
5. v6, e5, v5, e4, v4, e3, v3, e2, v2, e1, v1, e7, v4, e6, v6

解答：在上图中，v1, v2, v3, v4, v5, v6 是顶点，e1, e2, e3, e4, e5, e6, e7 是边。为了解决这个问题，我们将首先确定序列 1。之后，我们将继续处理下一个。

1. 序列 1 是一个开放行走（Open Walk），因为起始顶点和最后一个顶点不相同。起始顶点是 v1，最后一个顶点是 v2。
2. 序列 2 没有路径。它是一个路径（trail），因为路径可以包含重复的边和顶点，而序列 v4v1v2v3v4v5 包含重复的顶点 v4。
3. 序列 3 是一个路径（Path），因为序列 v1e1, v2e2, v3e3, v4e4, v5 不包含任何重复的边和顶点。
4. 序列 4 是一个圈（Cycle），因为序列 v1e1, v2e2, v3e3, v4e7, v1 中除了起始顶点 v1 之外，不包含任何重复的顶点或边。
5. 序列 5 没有圈。它是一个回路（Circuit），因为回路可以包含重复的顶点，但它不能包含重复的边（除了起始顶点）。序列 v6e5, v5e4, v4e3, v3e2, v2e1, v1e7, v4e6, v6 包含重复的顶点 v4。

示例 3：在此示例中，我们将考虑一个图。

与上述图相关的序列描述如下：

1. D, B, E, C, B
2. D, A, D, A, D
3. D, A, B, E, D
4. D, B, E, C, B, A, D

现在我们需要确定下面各种问题的答案，描述如下：

1. 我们需要确定哪些序列是有向行走。
2. 我们需要确定有向行走的长度。
3. 我们需要确定哪些有向行走也是有向路径。
4. 我们还需要确定哪些有向行走也是有向圈。

解决方案

在这里，我们将解决第一个问题，找出哪些序列是有向行走。之后，我们将继续处理下一个。

第一部分

这里序列 1 和 2 是有向行走，因为有向行走可以包含重复的顶点和边。

序列 2 不是有向行走，因为序列 DABED 不包含 A 和 B 之间的任何边。

序列 3 也不是有向行走，因为序列 DBECBAD 不包含 B 和 A 之间的任何边。

第二部分

通过以上部分，我们可以说序列 1 和 2 是有向图。所以我们只能找到序列 1 和 2 的长度。有向行走 1 和 2 的长度为 4。

第三部分

序列 3 和 4 不是有向行走，所以我们只找出序列 1 和 2 是否为有向路径。

序列 1 和 2 不是有向路径，因为这两个序列都包含重复的顶点。序列 1 包含重复的顶点 B，序列 2 包含重复的顶点 A。

第四部分

序列 1 和 2 不包含有向圈，因为圈不包含重复的顶点和边。序列 1 包含重复的顶点 B，序列 2 包含重复的顶点 A。