图论中的迹

为了理解迹，我们首先要了解图，之后我们就可以轻松地了解迹。

Graph

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

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

迹

迹被描述为顶点的序列，其中不应有任何重复的边，但它可以包含重复的顶点。因此，在迹的情况下，所有边都必须不同。学习欧拉回路时，有两点很重要，如下所述

• 迹的边不能重复。
• 迹的顶点可以重复。

我们可以借助一个例子来理解迹，如下所示

在这个图中，我们有7个顶点和11条边。该图包含多个迹，其中一些如下所示

• 迹: a → b → g → f → c → b (该图包含一个迹，因为没有重复的边)
• 迹: b → c → d → e → c → f → g → b (该图包含一个迹，因为没有重复的边)
• 不是迹: b → g → f → c → b → g → a → b (这个序列不是一个迹，因为有重复的边 "bg")
• 不是迹: c → e → f → c → a (这个序列不是一个迹，因为顶点 c 和 a 之间没有边)

迹的类型

迹主要有两种类型，如下所示

1. 开迹

如果迹的起始顶点和结束顶点不相同，那么这种类型的迹称为开迹。这意味着对于开迹，起始和结束顶点必须不同。我们可以借助一个例子来理解开迹，如下所示

在这个图中，我们有 6 个顶点和 5 条边。这个图可以包含多个开迹，如下所示

• 开迹: u → v → w → x → y → z (这个序列是一个开迹，因为它不包含相同的起始和结束顶点)
• 开迹: y → x → w → v (这个序列是一个开迹，因为它不包含相同的起始和结束顶点)

2. 闭迹

如果迹的起始顶点和结束顶点相同，那么这种类型的迹称为闭迹。这意味着对于闭迹，起始和结束顶点不能不同。我们可以借助一个例子来理解闭迹，如下所示

在这个图中，我们有 6 个顶点和 9 条边。该图可以包含开迹和闭迹。该图的一些闭迹如下所示

• 闭迹: V2→ V4 → V1 → V3 → V5 → V6 → V2 (这个序列是一个闭迹，因为它包含相同的起始和结束顶点，即 V2)
• 闭迹: V3→ V1 → V4 → V2 → V3 (这个序列是一个闭迹，因为它包含相同的起始和结束顶点，即 V3)
• 闭迹: V6→ V2 → V3 → V5 → V6 (这个序列是一个闭迹，因为它包含相同的起始和结束顶点，即 V6)

迹的例子

迹包含很多例子。一些例子如下所示

示例 1

这个例子包含一个图，我们需要找到该图的所有可能迹。

解决方案: 在这个图中，我们有 9 个顶点和 8 条边。该图包含多个迹，其中一些如下所示

• 迹: 3 → 2 → 1 → 7 → 8
• 迹: 6 → 5 → 1 → 7 → 9
• 不是迹: 4 → 2 → 1 → 7 → 9 → 7 → 8 (这个序列不是一个迹，因为有重复的边 “97”)
• 不是迹: 1 → 2 → 3 → 4 (这个序列不是一个迹，因为顶点 3 和 4 之间没有边)

示例 2

这个例子包含一个图，我们需要找到该图的所有可能迹。

解决方案: 在这个图中，我们有 5 个顶点和 7 条边。该图包含多个迹，其中一些如下所示

• 迹: 1 → 2 → 5 → 4 → 3 → 3 (这个序列是一个迹，因为没有重复的边)
• 不是迹: 5 → 3 → 3 → 4 (这个序列不是一个迹，因为顶点 3 和 4 之间没有边)
• 迹: 4 → 5 → 3 → 3 (这个序列是一个迹，因为没有重复的边)
• 不是迹: 1 → 2 → 1 → 2 → 5 → 4 (这个序列不是一个迹，因为有重复的边 “12”)

示例 3

这个例子包含一个图，我们需要找到该图的所有可能迹。

解决方案: 在这个图中，我们有 4 个顶点和 4 条边。该图包含多个迹，其中一些如下所示

• 迹: 1 → 2 → 3 → 4 → 2
• 迹: 4 → 2 → 1
• 不是迹: 4 → 3 → 2 → 1 → 2 → 3 (这个序列不是一个迹，因为有重复的边 “12”)

示例 4

这个例子包含一个图，我们需要找到该图的所有可能迹。

解决方案: 在这个图中，我们有 4 个顶点和 4 条边。在这个图中，不能有任何闭迹。它只能包含开迹，如下所述

• 迹: 5 → 2 → 3 → 4 → 6
• 迹: 6 → 4 → 3 → 2 → 5 → 6 (这个序列不是一个迹，因为顶点 5 和 6 之间没有边)
• 迹: 3 → 4 → 6
• 不是迹: 3 → 2 → 5 → 4 (这个序列不是一个迹，因为顶点 5 和 4 之间没有边)