图论中的同构图

如果一个图可以通过多种方式创建，并且创建的图与原始图具有相同的顶点数、边数和边连通性，那么这个图就被称为同构图。在本节中，我们将学习同构图、其必要条件、充分条件、应用、同构图示例以及更多内容。

同构的必要条件

我们可以通过以下三个条件来检查两个图 G1 和 G2 是否是同构的，它们描述如下：

1. 两个图必须包含相同数量的顶点。
2. 两个图必须包含相同数量的边。
3. 两个图必须具有相同的度序列。
4. 如果第一个图包含顶点 1, 2, 3, 4, ..., nk，并且这些顶点形成一个长度为 k 的环，那么第二个图的顶点 {f(1), f(2), f(3), f(4), ..., f(nk)} 也必须形成一个长度为 k 的环。

注意：度序列可以通过将所有顶点的度序列按升序排列来计算。

现在我们可以通过一个例子来理解同构，如下所示：

图 G1 和 G2 的顶点数均为 5，两个图的边数均为 4。两个图的边连通性相同，即边 AB、BC、CD 和 DE 在图 G1 中相连，在图 G2 中也是相同的边相连。因此，该图满足同构的性质。因此，这些图是同构图。

同构图的重要要点

• 以上描述的 4 个条件是证明两个给定图是同构图的必要条件。
• 然而，如果我们要证明两个图是同构图，所有这些条件并不总是充分的。
• 即使两个图满足以上所有 4 个条件，也不能保证它们是同构图。
• 但是，如果一个图无法满足以上任何一个条件，那么就可以保证这两个图不是同构图。

同构图的充分条件

以上定义的 4 个条件不足以证明两个图是同构图。有一些充分条件可以证明这一点。如果我们能够满足以下任一条件，则认为这两个图一定是同构的。所有同构的充分条件如下所示：

• 如果两个给定图的补图是同构的，那么这些类型的图被称为同构图。
• 如果两个给定图的邻接矩阵彼此相似，那么这些图是同构的。
• 如果通过从第一个图中删除一些顶点及其在另一个图中的对应顶点得到的子图是同构的，那么这些图被称为同构图。

同构的应用

同构在工程领域有很多应用。其中一些描述如下：

1. 网络分析：可用于网络分析，以发现结构相同的网络，这在网络分析和优化中起着至关重要的作用。
2. 化学信息学：可用于化学信息学，以比较通常以图的形式表示的分子结构。
3. 模式识别：可用于模式识别，以匹配模式和形状，这在计算机视觉和模式识别中有所应用。

图连通性

图连通性主要可以分为两种类型：顶点连通性和边连通性。现在，我们逐一学习它们。

• 顶点连通性：通过计算删除后能使图的剩余顶点断开连接的最少顶点数来计算。
• 边连通性：通过计算删除后能使图的剩余顶点断开连接的最少边数来计算。

同构图示例

同构有许多例子，其中一些描述如下：

示例 1

在此示例中，我们有两个图，需要检查它们是否为同构图。

解答：这里，我们使用上述四个必要条件来检查这些图是否为同构图。

条件 1：两个图都必须包含相同数量的顶点。

• 图 1 包含 5 个顶点，即 a, b, c, d, e，所以 G = 5。
• 图 2 也包含 5 个顶点，即 a, b, c, d, e，所以 H = 5。

两个图都满足第一个条件，因为它们包含相同数量的顶点。

条件 2：两个图都必须包含相同数量的边。

• 图 1 包含 6 条边，所以 G = 6。
• 图 2 也包含 6 条边，所以 H = 6。

两个图都满足第二个条件，因为它们包含相同数量的边。

条件 3：两个图都必须包含相同的度序列。

• G 的度序列 = {2, 2, 2, 3, 3}
• H 的度序列 = {1, 2, 2, 3, 4}

图 G 和 H 的度序列不相同。因此，这些图不满足第三个条件。

因此，这些图无法满足同构的所有必要条件。因此，这些图不是同构图。

∴ 图 G 和 H 不是同构图。

示例 2

在此示例中，我们有三个图，需要检查它们是否为同构图。

解答：这里，我们使用上述四个必要条件来检查这些图是否为同构图。

条件 1：所有图都必须包含相同数量的顶点。

• 图 1 包含 6 个顶点，即 a, b, c, d, e, f，所以 G1 = 6。
• 图 2 也包含 6 个顶点，即 a, b, c, d, e, f，所以 G2 = 6。
• 图 3 也包含 6 个顶点，即 1, 2, 3, 4, 5, 6，所以 G3 = 6。

所有图都满足第一个条件，因为它们包含相同数量的顶点。

条件 2：所有图都必须包含相同数量的边。

• 图 1 包含 6 条边，所以 G1 = 6。
• 图 2 也包含 6 条边，所以 G2 = 6。
• 图 3 也包含 6 条边，所以 G3 = 6。

所有图都满足第二个条件，因为它们包含相同数量的边。

条件 3：所有图都必须包含相同的度序列。

• G1 的度序列 = {2, 2, 2, 2, 2, 2}
• G2 的度序列 = {2, 2, 2, 2, 2, 2}
• G3 的度序列 = {2, 2, 2, 2, 2, 2}

所有图都满足第三个条件，因为它们包含相同的度序列。

条件 4：所有图都必须包含相同长度的相同环。

• 图 1 包含一个长度为 6 的环，它由度为 {2, 2, 2, 2, 2, 2} 的顶点形成。
• 图 2 也包含一个长度为 6 的环，它由度为 {2, 2, 2, 2, 2, 2} 的顶点形成。
• 图 3 包含两个长度为 3 的环，它们由度为 {2, 2, 2} 的顶点形成。

图 G1 和 G2 包含 1 个长度为 6 的环，而图 G3 包含 2 个长度为 3 的环。因此，图 G1 和 G2 满足第四个条件，因为它们包含相同长度的相同环，但图 G3 包含不同长度的不同环。因此，G1 和 G2 可以是同构图，但图 G3 不能是同构图。

∴ 图 G1 和 G2 可能是同构图。

现在，我们将检查图 G1 和 G2 的充分条件，以确认这些图是否为同构图。

充分条件：根据此条件，如果图 G1 和 G2 的补图是同构图，则这些图是同构图。

为了验证这一点，我们按以下方式绘制两个图的补图：

在这些图中，我们可以看到 G1 和 G2 的补图是同构的。

∴ 图 G1 和 G2 是同构图。

示例 3

在此示例中，我们有两个图，需要检查它们是否为同构图。

解答：这里，我们使用上述四个必要条件来检查这些图是否为同构图。

条件 1：两个图都必须包含相同数量的顶点。

• 图 1 包含 6 个顶点，即 1, 2, 3, 4, 5, 6，所以 G1 = 6。
• 图 2 也包含 6 个顶点，即 1, 2, 3, 4, 5, 6，所以 G2 = 6。

两个图都满足第一个条件，因为它们包含相同数量的顶点。

条件 2：两个图都必须包含相同数量的边。

• 图 1 包含 9 条边，所以 G1 = 9。
• 图 2 包含 8 条边，所以 G2 = 8。

图 G1 和 G2 的边数不相同。因此，这些图不满足第二个条件。

因此，这些图无法满足同构的所有必要条件。

∴ 图 G1 和 G2 不是同构图。

示例 4

在此示例中，我们有两个图，需要检查它们是否为同构图。

解答：这里，我们使用上述四个必要条件来检查这些图是否为同构图。

条件 1：两个图都必须包含相同数量的顶点。

• 图 1 包含 6 个顶点，即 u1, u2, u3, u4, u5, u6，所以 G = 6。
• 图 2 也包含 6 个顶点，即 v1, v2, v3, v4, v5, v6，所以 H = 6。

两个图都满足第一个条件，因为它们包含相同数量的顶点。

条件 2：两个图都必须包含相同数量的边。

• 图 1 包含 7 条边，所以 G = 7。
• 图 1 包含 7 条边，所以 G = 7。

所有图都满足第二个条件，因为它们包含相同数量的边。

条件 3：两个图都必须包含相同的度序列。

• G 的度序列 = {2, 2, 2, 2, 3, 3}
• H 的度序列 = {2, 2, 2, 2, 3, 3}

两个图都满足第三个条件，因为它们包含相同的度序列。

条件 4：两个图都必须包含相同长度的相同环。

• 图 1 包含一个长度为 5 的环，它由度为 {2, 2, 2, 3, 3} 的顶点形成。
• 图 2 包含一个长度为 5 的环，它由度为 {2, 2, 2, 3, 3} 的顶点形成。

两个图都满足第四个条件，因为它们包含相同长度的环。两个图都满足所有 4 个必要条件。

∴ 图 G 和 H 可能是同构图。

现在，我们将检查图 G 和 H 的充分条件，以确认这些图是否为同构图。

充分条件：根据此条件，如果图 G 和 H 的补图是同构图，则这些图是同构图。

为了验证这一点，我们按以下方式绘制两个图的补图：

在这些图中，我们可以看到 G 和 H 的补图是同构的。

∴ 图 G 和 H 是同构图。

示例 5

在此示例中，我们有两个图，需要检查它们是否为同构图。

解答：这里，我们使用上述四个必要条件来检查这些图是否为同构图。

条件 1：两个图都必须包含相同数量的顶点。

• 图 1 包含 4 个顶点，即 1, 2, 3, 4，所以 G1 = 4。
• 图 2 也包含 4 个顶点，即 1, 2, 3, 4，所以 G2 = 4。

所有图都满足第一个条件，因为它们包含相同数量的顶点。

条件 2：两个图都必须包含相同数量的边。

• 图 1 包含 5 条边，所以 G1 = 5。
• 图 2 也包含 5 条边，所以 G2 = 5。

所有图都满足第二个条件，因为它们包含相同数量的边。

条件 3：两个图都必须包含相同的度序列。

• G 的度序列 = {2, 2, 3, 3}
• H 的度序列 = {2, 2, 3, 3}

所有图都满足第三个条件，因为它们包含相同的度序列。

条件 4：两个图都必须包含相同长度的相同环。

• 图 1 包含一个长度为 3 的环，它由度为 {2, 3, 3} 的顶点形成。
• 图 2 包含一个长度为 3 的环，它由度为 {2, 3, 3} 的顶点形成。

两个图都满足第四个条件，因为它们包含相同长度的环。两个图都满足所有 4 个必要条件。

∴ 图 G1 和 G2 可能是同构图。

现在，我们将检查图 G1 和 G2 的充分条件，以确认这些图是否为同构图。

充分条件：根据此条件，如果图 G1 和 G2 的补图是同构图，则这些图是同构图。

为了验证这一点，我们按以下方式绘制两个图的补图：

在这些图中，我们可以看到 G1 和 G2 的补图是同构的。

∴ 图 G1 和 G2 是同构图。