图论中的同构和同态

在图论领域，同构是一个至关重要的概念。通过图同构，可以判断两个图在结构上是否相同。如果一个图可以有不同的形式，但具有相同数量的顶点、边和相同的边连接性，那么这些类型的图就被称为同构图。同构图的外观可能不同。它们在计算机设计、生物学、网络设计等不同领域有广泛的应用。

什么是同构？

假设有两个简单图 G 和 H。如果存在一种结构，可以用来表示图中边和顶点的“一对一”对应关系，那么这两个图就被称为同构图。换句话说，只有当这两个图仅在顶点和边的名称上有所不同，但结构上等价时，它们才被称为同构图。我们可以通过下面的例子来理解同构。

上面的图包含一些细节，描述如下：

• 一个图以多种形式展示。
• 它们包含相同数量的边、顶点和相同的边连接性。
• 因此，这些图是同构的。

注意：所以，如果有两个同构图，那么一个图被称为另一个图的“调整版本”。

如果两个图 G1 和 G2 满足 G1 ≡ G2（此处 ≡ 用于表示同构），则必须满足某些条件。这些条件也称为必要条件，描述如下：

• |V(G1)| = |V(G2)|
• |E(G1)| = |E(G2)|
• 两个图 G1 和 G2 的度数序列相同。
• 如果图 G1 包含顶点 V1, V2, V3, V4, ....., Vn，并且该图形成一个长度为 k 的环，那么图 G2 的顶点 {f(V1), f(V2), f(V3), f(V4), ....., f(Vn)} 也必须形成一个长度为 k 的环。

通过上述条件，只能说明图 G1 和 G2 可能是同构的，所以这些是必要条件。然而，这些条件不足以证明图是同构的。有一些充分条件，如果满足其中的任何一个条件，则图是同构的。充分条件描述如下：

• 如果图 G1 和 G2 满足 (G1- ≡ G2-)，则称 G1 和 G2 是同构图；这里 G1 和 G2 表示简单图。这意味着对于同构，G1 和 G2 的补图必须是同构的。
• 如果图 G1 和 G2 具有相同的邻接矩阵，则称它们是同构图。
• 如果通过从第一个图中移除一些顶点以及从另一个图中移除它们的对应顶点所得到的子图是同构的，则称图 G1 和 G2 是同构图。

同构图示例

同构图有各种示例，描述如下：

示例 1

在这个例子中，我们有两个图，需要判断它们是否是同构图。

解答：在上面的图 G1 中，有 5 个顶点，7 条边，该图所有顶点的度数序列为 {2, 2, 3, 3, 4}。在图 G2 中，有 5 个顶点，7 条边，该图所有顶点的度数序列为 {2, 3, 3, 3, 3}。因此，两个图的度数序列不相同。所以，这些图不是同构图。

∴ 图 G1 和 G2 不是同构图。

示例 2

在这个例子中，我们有三个图，需要判断它们是否是同构图。

解答：在上面的图 G1 中，有 5 个顶点，5 条边，该图所有顶点的度数序列为 {2, 2, 2, 2, 2}。在图 G2 中，有 5 个顶点，5 条边，该图所有顶点的度数序列为 {2, 2, 2, 2, 2}。在图 G3 中，有 5 个顶点，6 条边，该图所有顶点的度数序列为 {2, 2, 2, 3, 3}。

因此，图 G1 和 G2 的度数序列相似，但图 G3 的度数序列与图 G1 和 G2 不相同。所以，图 G1 和 G2 可能是同构图，但 G3 不可能是同构图。

现在，我们对图 G1 和 G2 进行补图操作，以确认它们是否是同构图。

在这些图中，我们可以看到图 G1 和 G2 的补图是同构的，即 (G1- ≡ G2-)。因此，我们可以说图 G1 和 G2 是同构图。

∴ 图 G1 和 G2 是同构图。

示例 3

在这个例子中，我们有两个图，需要判断它们是否是同构图。

解答：在上面的图 G1 中，有 6 个顶点，8 条边，该图所有顶点的度数序列为 {2, 2, 3, 3, 3, 3}。在图 G2 中，有 6 个顶点，9 条边，该图所有顶点的度数序列为 {2, 3, 3, 3, 3, 4}。因此，两个图的度数序列不相同。所以，这些图不是同构图。

∴ 图 G1 和 G2 不是同构图。

平面图

如果一个图可以在平面上绘制，使得图中的两条边在非顶点点上不相交，那么这种图就被称为平面图。这种绘制的图也称为平面嵌入图或平面图。但平面图和平面图之间有一个区别，即在平面图中，两条边不应该相交，但我们可以绘制一个平面图而没有这种情况。形式上，平面图可以描述为平面图的同构。

平面图示例

平面图有很多例子，其中一些描述如下：

示例 1

在这个例子中，我们有一个图，需要判断它是平面图还是非平面图。

解答：该图是平面图，因为该图的所有边都不相交。

示例 2

在这个例子中，我们有两个图，需要判断它们是平面图还是非平面图。

解答：左侧的图不是平面图，但它可以是平面图。在这个图中，边相互交叉。但这个图可以绘制在平面区域而不交叉。因此，左侧的图是平面图。右侧的图也是平面图，因为它绘制在平面中，并且该图的边不相交。因此，左侧图和右侧图都是平面图。

示例 3

在这个例子中，我们有两个图，需要判断它们是平面图还是非平面图。

解答：在左侧的图中，边不相交，但在右侧的图中，边相互交叉。因此，左图是平面图，右图是非平面图。

区域

区域可以描述为平面中由边界定的区域。在这种情况下，区域不能进一步细分。借助平面图，平面可以划分为多个区域。

当我们成功绘制一个平面图而不交叉边时，在这种情况下，平面可以根据顶点和边划分为区域。有界区域 r 的度数可以用符号 deg(r) 表示。

区域示例

区域有各种例子，其中一些描述如下：

示例 1

在这个例子中，我们有一个包含 6 个区域的图，需要找出每个有界区域的度数。

解答：每个区域的度数可以通过以下公式确定，该公式描述如下：

deg(r) = 穿过区域 r 的边数。

现在我们通过以下方式确定每个有界区域（1、2、3、4、5 和 6）的度数：

Deg(1) = 3

Deg(2) = 3

Deg(3) = 3

Deg(4) = 3

Deg(5) = 3

Deg(6) = 7

示例 2

在这个例子中，我们有一个包含 6 条边的图。我们需要找出该图的一个区域。

解答：每个无界区域的度数可以通过以下公式确定，该公式描述如下：

deg(r) = 穿过区域 r 的边数。

现在，我们通过以下方式确定每个有界区域（R1 和 R2）的度数：

Deg(R1) = 4

Deg(R2) = 6

平面图的性质

平面图包含许多性质，其中一些描述如下：

• 如果一个平面图包含 n 个顶点，则有一个公式可以通过它来确定所有顶点的度数之和，该公式描述如下：
  n Σ i = 1 deg(Vi) = 2|E|
• 假设一个平面图包含 n 个区域。在这种情况下，有一个公式可以通过它来确定区域度数之和，该公式基于区域度数之和定理，描述如下：
  n Σ i = 1 deg(ri) = 2|E|

根据上述定理，我们得出一个结论，描述如下：

在平面图中，根据区域的度数，可以以多种方式计算图中区域度数之和，描述如下：

• 如果一个图的每个区域的度数都为 k，则有一个公式可以通过它来计算区域度数之和，该公式描述如下：
  K|R| = 2|E|
• 如果一个图的每个区域的最小度数都为 K (≥K)，则有一个公式可以通过它来计算区域度数之和，该公式描述如下：
  K|R| ≤ 2|E|
• 如果一个图的每个区域的最大度数都为 K (≤K)，则有一个公式可以通过它来计算区域度数之和，该公式描述如下：
  K|R| ≥ 2|E|

注意：我们假设所有区域都具有相同的度数。

基于平面图的欧拉公式，我们可以描述如下：

• 如果有一个连通平面图 G，则顶点、边和区域之间存在一个关系，该关系描述如下：
  |V| + |R| = |E| + 2
• 如果一个平面图包含 K 个连通分量，则顶点、边和区域之间存在一个关系，该关系描述如下：
  |V| + |R| = |E| + (K+1)
  其中 |V| 表示顶点数，|E| 表示边数，|R| 表示区域数。

边-顶点不等式

如果一个连通平面图的每个区域的度数最小为 K，则可以通过以下公式确定边-顶点不等式：

我们知道 |V| + |R| = |E| + 2

假设存在一个简单连通平面图 G，则它包含以下特性：

至少存在一个顶点 V •∈ G，使得 deg(V) ≤ 5。

如果存在一个简单连通图 G，它包含至少 2 条边且不包含任何三角形，则它满足以下关系：

Kuratowski 定理

根据这个定理，如果一个图 G 包含一个同胚于 K5 或 K3,3 的子图 G'，则该图被称为非平面图。换句话说，它可以被描述为一种算法，帮助判断给定的图是否强连通。如果图中的每个顶点都能到达图中的其他任何顶点，则称该图为强连通图。

什么是同态？

假设有两个图 G1 和 G2。如果这两个图都是从同一个图 G 派生而来，通过将 G 的某些边划分成多个顶点，则称它们是同态图。现在我们通过下面的例子来理解同态：

现在我们将边 'rs' 通过在其中间添加一个顶点来划分成两条边，如下所示：

下面的图是第一个图的同态图。

如果图 G1 同构于图 G2，那么图 G 同态于图 G2。如果我们尝试反过来，则不一定成立。

• 如果我们有一个顶点数小于或等于 4 的图，那么这种图是平面图。
• 如果我们有一个边数小于或等于 8 的图，那么这种图是平面图。
• 如果一个完全图 K_n 满足 n ≤ 4 的关系，那么这种图是平面图。
• 如果一个完全二分图 K_{m, n} 满足 m ≤ 2 或 n ≤ 2 的关系，那么这种图是平面图。
• 假设有一个简单的非平面图。如果它包含最少数量的顶点，则该图为完全图 k₅。
• 假设有一个简单的非平面图。如果它包含最少数量的边，则该图为 K_{3, 3}。