图论中的独立集

独立集

独立集以集合的形式表示。独立集可以按以下方式解释：

• 图 G 的独立集可以包含顶点集 I，其中集合中的任意两个顶点都不相邻。这意味着图的两个顶点不应有共同的边。换句话说，独立集可以描述为一组不相邻的顶点。
• 图 G 的独立集可以包含边集，其中集合中的任意两条边都不相邻。这意味着图的两条边不应包含共同的顶点。
• 独立集还有另一个名称，即稳定集。
• 参数 α₀ (G) = max 被称为 G 的独立数，即不相邻顶点的最大数量。这里，|I| = α₀ (G) 用于表示 G 中的独立集。
• 如果任何独立集 I 满足关系 |I| = α₀(G)，则称其为最大独立集。

独立集示例

独立集有很多例子，如下所示：

示例 1

此示例包含一个图 G。我们需要计算该图所有可能的独立集。

解决方案：我们可以借助不相邻顶点的最大数量来计算独立集。上面的图包含一些独立集，如下所述：

第一个独立集 (I1) = {Y}

第二个独立集 (I2) = {Z}

第三个独立集 (I3) = {R}

第四个独立集 (I4) = {Y, Z, R}

因此，该图的独立集 α₀(G) = 3。

示例 2

此示例包含一个图 G。我们需要计算该图所有可能的独立集。

解决方案：我们可以借助不相邻顶点的最大数量来计算独立集。上面的图包含的独立集如下所述：

第一个独立集 (I1) = {1}

第二个独立集 (I2) = {3}

第三个独立集 (I3) = {6}

第四个独立集 (I4) = {1, 3}

第五个独立集 (I5) = {3, 6}

第六个独立集 (I6) = {1, 3, 6}

因此，该图的独立集 α₀(G) = 3。

示例 3

此示例包含一个图 G。我们需要计算该图所有可能的独立集。

解决方案：我们可以借助不相邻顶点的最大数量来计算独立集。上面的图包含的独立集如下所述：

第一个独立集 (I1) = {3},

第二个独立集 (I2) = {5},

第三个独立集 (I3) = {7}

第四个独立集 (I4) = {8}

第五个独立集 (I5) = {3, 5}

第六个独立集 (I6) = {3, 5, 7, 8} 等。

因此，该图的独立集 α₀(G) = 4。

示例 4

此示例包含一个图 G。我们需要计算该图所有可能的独立集。

解决方案：我们可以借助不相邻顶点的最大数量来计算独立集。上面的图包含的独立集如下所述：

第一个独立集 (I1) = {2},

第二个独立集 (I2) = {7},

第三个独立集 (I3) = {10}

第四个独立集 (I4) = {11}

第五个独立集 (I5) = {5}

第六个独立集 (I6) = {2, 7, 5}

第七个独立集 (I7) = {2, 5, 7, 10, 11} 等。

示例 5

此示例包含一个图 G。我们需要计算该图所有可能的独立集。

解决方案：我们可以借助不相邻顶点的最大数量来计算独立集。上面的图包含的独立集如下所述：

第一个独立集 (I1) = {1},

第二个独立集 (I2) = {4},

第三个独立集 (I3) = {5}

第四个独立集 (I4) = {6}

第五个独立集 (I5) = {1, 4, 5, 6} 等。

因此，该图的独立集 α₀(G) = 4。

示例 6

此示例包含一个图 G。我们需要计算该图所有可能的独立集。

解决方案：我们可以借助不相邻顶点的最大数量来计算独立集。上面的图包含总共 9 个独立集，通过蓝色显示。

因此，该图的独立集 α₀(G) = 9。

独立边集

在此，我们假设有一个图 G = (V, E)。如果存在一个边集 L 是 E 的子集，那么如果子集 L 中的任意两条边都不相邻，它就被称为 G 的独立边集。图的子集必须包含至少 2 条边才能构成独立边集。我们可以通过下面的例子来理解独立边集：

我们可以从这个图获得一些子集，如下所述：

第一个子集 L1 = {X, Y}

第二个子集 L2 = {X, U} {V, W} {Y, Z}

第三个子集 L3 = {Z, W} {X, V}

第四个子集 L4 = {X, Y} {Z, W} {U, V}

第五个子集 L5 = {X, V} {Z, W}

在给定图的子集 L2、L3、L4 和 L5 中，我们可以看到所有子集都不包含任何相邻的边。因此，所有子集都称为独立边集。然而，子集 L1 不称为独立边集，因为如果我们想构成一个独立边集，那么子集必须至少包含两条边。因此，L2、L3、L4 和 L5 是独立边集。

极大独立边集

极大独立边集还有一个名称，即极大匹配。极大独立边集可以描述为这样一个独立边集，即不可能将图 G 的任何其他边添加到子集 L 中。我们可以通过下面的例子来理解极大独立边集：

我们可以从这个图获得一些子集，如下所述：

第一个子集 L1 = {X, Y}

第二个子集 L2 = {X, U} {V, W} {Y, Z}

第三个子集 L3 = {Z, W} {X, V}

第四个子集 L4 = {X, Y} {Z, W} {U, V}

第五个子集 L5 = {X, V} {Z, W}

在所有子集中，子集 L2、L3、L4 和 L5 都没有可能将任何不相邻的其他边添加到其中。因此，L2、L3、L4 和 L5 是极大独立边集。

最大独立边集

图 G 的最大独立边集可以描述为包含最多边的边集。符号 β1 可以表示最大独立边集。有一个公式可以帮助我们找到最大独立边集，如下所述：

我们可以通过下面的例子来理解最大独立边集：

我们可以从这个图获得一些子集，如下所述：

第一个子集 L1 = {X, Y}

第二个子集 L2 = {X, U} {V, W} {Y, Z}

第三个子集 L3 = {Z, W} {X, V}

第四个子集 L4 = {X, Y} {Z, W} {U, V}

第五个子集 L5 = {X, V} {Z, W}

在所有子集中，子集 L4 包含的边数最多，并且这些边互不相邻。因此，L4 是最大独立边集，可以表示为 β1 = 3。

注意：如果图 G 中没有孤立顶点，则有：α1 + β1 = 图的顶点数 = |V|

例如，如果我们想表示完全图 Kn/Cn/wn 的边覆盖数，则可以如下表示：

边数或匹配数 = β₁ = [n/2] α₁ + β₁ = n。

独立顶点集

在此，我们假设有一个图 G = {V, E} 和一个子集 S。如果顶点集 V 的子集 S 是图 G 的独立顶点集，则 S 中的任意两个顶点都不相邻。我们可以通过下面的例子来理解独立顶点集：

我们可以从这个图获得一些子集，如下所述：

第一个子集 S1 = {X}

第二个子集 S2 = {X, Z, V}

第三个子集 S3 = {Y, R, W, U}

第四个子集 S4 = {V, Y}

第五个子集 S5 = {V, R}

子集 S2、S3、S4 和 S5 不包含任何与子集中其他顶点相邻的顶点。因此，我们可以说这些子集是独立顶点集。然而，子集 S1 不称为独立顶点集，因为如果我们想构成一个独立顶点集，那么子集必须至少包含两个顶点。因此，S2、S3、S4 和 S5 是独立顶点集。

极大独立顶点集

极大独立顶点集可以描述为这样一个独立顶点集，即不可能将图 G 的任何其他顶点添加到子集 S 中。我们可以通过下面的例子来理解极大独立顶点集：

我们可以从这个图获得一些子集，如下所述：

第一个子集 S1 = {X}

第二个子集 S2 = {X, Z, V}

第三个子集 S3 = {Y, R, W, U}

第四个子集 S4 = {V, Y}

第五个子集 S5 = {V, R}

在所有子集中，子集 S2 和 S3 都没有可能将任何不相邻的其他顶点添加到其中。在子集 S1 和 S3 中，可以添加其他顶点。因此，S2 和 S3 是极大独立边集。

最大独立顶点集

图 G 的最大独立顶点集可以描述为包含最多顶点的顶点集。符号 β2 可以表示最大独立顶点集。我们可以通过下面的例子来理解最大独立顶点集：

我们可以从这个图获得一些子集，如下所述：

第一个子集 S1 = {X}

第二个子集 S2 = {X, Z, V}

第三个子集 S3 = {Y, R, W, U}

第四个子集 S4 = {V, Y}

第五个子集 S5 = {V, R}

在所有子集中，子集 S3 包含的顶点数最多，并且这些顶点互不相邻。因此，S3 是最大独立边集，可以表示为 β2 = 4。在 G 的最大独立顶点集中，顶点数也称为 G 的独立顶点数 (β2)。

例如，如果我们有一个完全图 Kn，那么有一个公式可以帮助我们找到顶点覆盖数和顶点独立数，如下所示：

顶点覆盖数 = α₂ = n-1

顶点独立数 = β₂ = 1

所以，我们可以说：

α₂ + β₂ = n

如果是一个完全图，那么该图的每个顶点都与其剩余的 (n-1) 个顶点相邻。因此，K_n 的最大独立集只能包含一个顶点。

因此，

β₂ = 1

α₂=|v| - β₂ = n-1

注意：如果我们有一个图 G = (V, E)，则该最大独立顶点集包含一些性质，如下所述：

• α₂ + β₂ = |V|
• 如果 S 是 G 的独立顶点集，则 G 的顶点覆盖可以通过 (V-S) 计算。

顶点覆盖

• 顶点覆盖可以描述为顶点集 K，用于覆盖图的所有边。换句话说，如果图 G 的每条边都被集合 K 中的一个顶点覆盖，那么它就称为顶点覆盖。
• 顶点覆盖数可以通过参数 β₀(G) = min 计算。换句话说，顶点覆盖数是能够覆盖图的所有顶点的最小顶点数。
• 最小顶点覆盖可以由任何顶点覆盖 K 表示，其中 |K| = β₀(G)。这里，|K|: K 用于表示 G 的顶点覆盖。

我们可以通过下面的例子来理解顶点覆盖：

我们可以从这个图获得一些顶点覆盖，如下所述：

第一个顶点覆盖 V1 = {1, 3}

第二个顶点覆盖 V2 = {2, 4}

第三个顶点覆盖 V3 = {1, 2, 3}

第四个顶点覆盖 V4 = {1, 2, 3, 4} 等。

顶点覆盖数可以通过能够覆盖图 G 的所有边的最小顶点数来计算。因此，在该图中，顶点覆盖数 β₀(G) = 2。

注意：如果我们有一个图 G，那么它包含关系 α₀(G) + β₀(G) = n。这里，顶点数用 n 表示。

边覆盖

• 边覆盖可以描述为边集 F，用于覆盖图的所有顶点。换句话说，如果图 G 的每个顶点都与集合 F 中的一条边相邻，那么它就称为边覆盖。
• 边覆盖数可以通过参数 β₁(G) = min 计算。换句话说，边覆盖数可以通过孤立顶点的数量加上能够覆盖图的所有顶点的最小边数来计算。
• 最小边覆盖可以由任何边覆盖 F 表示，其中 |F| = β₁(G)。这里，|F|: F 用于表示 G 的边覆盖。

我们可以通过下面的例子来理解边覆盖：

我们可以从这个图获得一些边覆盖，如下所述：

E1 = {a, b, c, d}, E2 = {a, d}, E3 = {b, c}

边覆盖数可以通过能够覆盖图 G 的所有顶点的最小边数来计算。因此，在该图中，边覆盖数 β1(G) = 2。

注意：如果我们有一个图 G，那么它包含关系 α₀(G) + β₀(G) = n。这里，边数用 n 表示。

匹配

• 匹配可以描述为一组不相邻的边。换句话说，匹配可以通过图 G 中那些在集合中不相邻的边的独立集来计算。
• 匹配数可以通过参数 α₁(G) = max 计算。换句话说，匹配数可以通过不相邻边的最大数量来计算。
• 最大匹配可以由任何匹配 M 表示，其中 |M| = α₁(G)。这里，|M|: M 用于表示 G 中的匹配。

我们可以通过下面的例子来理解匹配：

我们可以从这个图获得一些匹配，如下所述：

第一个匹配 M1 = {a}

第二个匹配 M2 = {b}

第三个匹配 M3 = {c}

第四个匹配 M4 = {d}

第五个匹配 M5 = {a, d}

第六个匹配 M6 = {b, c}

匹配数可以通过上述图的不相邻边的最小数量来计算。因此，在该图中，匹配数 α₁(G) = 2。