图论中的电路

在本节中，我们可以学习回路，但为此，我们必须首先学习什么是图。只有这样，我们才能更容易理解回路。

Graph

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

我们也可以用另一个更正式的定义来表示图，即图可以表示为 G = (V, E)，其中 V 表示顶点集，E 表示边集。边用于连接图的两个顶点。在本节中，我们将学习回路、回路的示例以及更多内容。

什么是回路？

回路是图中顶点和边的序列集合。换句话说，它可以描述为图的遍历，生成顶点和边的序列，并且序列的第一个和最后一个顶点必须相同。在回路的情况下，边不能重复，但顶点可以重复。在回路的情况下，图的每个顶点通过特定的边连接到下一个顶点。换句话说，我们也可以将回路称为一个闭合迹，其中必须有相同的起始顶点和结束顶点。因此，我们有两个与回路相关的要点，它们必须满足才能形成回路，如下所示

• 回路可以包含重复的顶点。
• 回路不能包含重复的边。

图可以是两种：有向图和无向图。我们可以在两种类型的图中找到回路。在无向图中，边不包含任何方向，因此我们可以朝任何方向前进，但在有向图中，边包含方向，我们必须沿着边从一个顶点到另一个顶点。在本节中，我们假设回路表示为 C。现在我们通过一个示例如下分别了解两种类型图中的回路

无向图中的回路

此示例包含一个无向图，我们必须找到此图的所有可能回路。

在上面的图中，可以创建多个回路。现在我们展示此图的一些可能回路，如下所述

第一个回路 C1 = 3 → 2 → 1 → 4 → 3

第二个回路 C2 = 3 → 2 → 1 → 5

现在，我们解释哪些序列是回路，哪些不是回路。

• C1 是一个回路（第一个序列是一个回路，因为它包含相同的起始顶点和结束顶点，并且序列中没有重复的边）。
• C2 不是一个回路（第二个序列不是一个回路，因为它不包含相同的起始顶点和结束顶点，并且序列中没有重复的边）。

因此，C1 是一个回路。

有向图中的回路

此示例包含一个有向图，我们必须找到此图的所有可能回路。

在上面的图中，可以创建多个回路。现在我们展示此图的一些可能回路，如下所述

第一个回路 C1 = B → A → C → D → B

第二个回路 C2 = E → D → B → A → C → D

第三个回路 C3 = A → C → D → E

现在，我们解释哪些序列是回路，哪些不是回路。

• C1 是一个回路（第一个序列是一个回路，因为它包含相同的起始顶点和结束顶点，并且没有重复的边）。
• C2 不是一个回路（第二个序列不是一个回路，因为它不包含相同的起始顶点和结束顶点，并且序列中没有重复的边）。
• C3 不是一个回路（第三个序列不是一个回路，因为没有边，通过这两条边我们可以从顶点 D 到顶点 E）。

因此，C1 是一个回路。

回路的示例

回路有各种示例。一些回路的示例如下所述

示例 1

此示例包含一个图，我们需要计算此图的所有可能回路。

解决方案：在上面的图中，可以创建多个回路。现在我们展示此图的一些可能回路，如下所述

第一个回路 C1 = 1 → 2 → 5 → 4 → 1

第二个回路 C2 = 3 → 6 → 4 → 1 → 3

第三个回路 C3 = 4 → 6 → 7 → 5 → 4

第四个回路 C4 = 3 → 1 → 2 → 5 → 7 → 6

第五个回路 C5 = 3 → 1 → 2 → 5 → 7 → 6 → 3 → 1 → 4 → 6 → 3

现在，我们解释哪些序列是回路，哪些不是回路。

• C1 是一个回路（它是一个回路，因为它包含相同的起始顶点和结束顶点，并且没有重复的边）。
• C2 是一个回路（它是一个回路，因为它包含相同的起始顶点和结束顶点，并且没有重复的边）。
• C3 是一个回路（它是一个回路，因为它包含相同的起始顶点和结束顶点，并且没有重复的边）。
• C4 不是一个回路（它不是一个回路，因为它不包含相同的起始顶点和结束顶点，并且没有重复的边）。
• C5 不是一个回路（它不是一个回路，因为它包含相同的起始顶点和结束顶点，但有重复的边）。

因此，C1、C2 和 C3 是回路。

示例 2

此示例包含一个图，我们计算此图的所有可能回路。

解决方案：在上面的图中，我们尝试通过以下方式创建回路

第一个回路 C1 = D → A → C → B（此序列不是回路，因为起始顶点和结束顶点不相同）

第二个回路 C2 = A → C → B → A（此序列不是回路，因为没有边可以从顶点 B 到 A）。

上述图不是一个完整图。因此，它永远不能包含相同的起始顶点和结束顶点，这是回路的属性之一。因此，此图中没有回路。

示例 3

此示例包含一个图，我们计算此图的所有可能回路。

解决方案：在上面的图中，我们可以创建多个回路。现在我们展示此图的一些可能回路，如下所述

第一个回路 C1 = A → B → D → E → C → A

第二个回路 C2 = A → C → E → G → F → G → E → C → A

第三个回路 C3 = A → C → D → B → A

第四个回路 C4 = C → E → D → C

第五个回路 C5 = G → E → C → A → B → D → E

现在，我们解释哪些序列是回路，哪些不是回路。

• C1 是一个回路（第四个序列是一个回路，因为起始顶点和结束顶点相同，并且没有重复的边）。
• C2 不是一个回路（第二个序列不是一个回路，因为此序列中有重复的边，但此序列的起始顶点和结束顶点相同）。
• C3 是一个回路（第四个序列是一个回路，因为起始顶点和结束顶点相同，并且没有重复的边）。
• C4 是一个回路（第四个序列是一个回路，因为起始顶点和结束顶点相同，并且没有重复的边）。
• C5 不是一个回路（第五个序列不是一个回路，因为它没有相同的起始顶点和结束顶点）。

因此，C1、C3 和 C4 是回路。

示例 4

此示例包含一个图，我们必须找到此图的回路。

解决方案：在上面的图中，我们尝试通过以下方式创建回路

第一个回路 C1 = A → B → D → E → C（此序列不是回路，因为起始顶点和结束顶点不相同）

第二个回路 C2 = C → E → D → B → C（此序列不是回路，因为没有边可以从顶点 B 到 C）。

上述图不是一个完整图。因此，它永远不能包含相同的起始顶点和结束顶点，这是回路的属性之一。因此，此图中没有回路。

示例 5

此示例包含一个图，我们必须找到此图的回路。

解决方案：在上面的图中，可以创建多个回路。现在我们展示此图的一些可能回路，如下所述

第一个回路 C1 = A → B → C → F → E → D

第二个回路 C2 = D → E → G → D

第三个回路 C3 = E → F → H → E

第四个回路 C4 = B → C → F → E → B

第五个回路 C5 = D → E → F → H → G → D

现在，我们解释哪些序列是回路，哪些不是回路。

• C1 不是一个回路（第一个序列不是一个回路，因为它不包含任何重复的边，但此序列的起始顶点和结束顶点不相同）。
• C2 是一个回路（第二个序列是一个回路，因为它不包含任何重复的边，并且此序列的起始顶点和结束顶点相同）。
• C3 是一个回路（第三个序列是一个回路，因为它不包含任何重复的边，并且此序列的起始顶点和结束顶点相同）。
• C4 不是一个回路（第四个序列不是一个回路，因为它不包含从 B 到 E 的任何边）。
• C5 不是一个回路（第五个序列不是一个回路，因为在此序列中，起始顶点和结束顶点相同，但顶点 G 和 H 之间没有边）。

因此，C2 和 C3 是回路。