离散数学中的独立集

独立集可以描述为一个包含以下细节的集合

• 独立集中不能有任何相互相邻的顶点。集合的两个顶点不能有相同的边。独立集也可以通过计算 G 中一组不相邻的顶点来确定。
• 独立集中不能有任何相互相邻的边。集合的两个边不能有相同的顶点。
• 独立集也称为稳定集。
• 参数 α₀ (G) = max |I| 可以称为 G 的独立数。这里，I 用于表示 G 的独立集。独立数也可以称为不相邻顶点的最大数量。
• 如果存在独立集 I，且 |I| = α₀ (G)，则称其为最大独立集。独立集的示例如下所述

从上图中，我们有以下关于独立集的细节。

I1= {x}

I2 = {y}

I3 = {z}

I4 = {u}

I5 = {x, z}

I6 = {y, u}

因此，不相邻顶点的最大数量或独立数 α₀ (G) = 2。

独立边集

假设有一个图 G = (V, E)。如果存在一个子集 L，并且该子集中没有两条边相邻，在这种情况下，E 的子集 L 将被称为 G 的独立边集。独立边集的示例如下所述

从上图中，我们将考虑以下子集。

L1= {x, y}

L2 = {x, y} {z, v}

L3 = {x, u} {y, z}

在上面的图中，我们可以看到子集 L2 和 L3 不包含相邻边。因此，子集 L2 和 L3 是独立边集。但是子集 L1 不是独立边集，因为我们可以借助至少两条边形成一个独立边集，但在 L1 中只有一条边。因此，我们可以说子集 L1 不是独立边集的示例。

最大独立边集

最大独立边集也称为最大匹配。如果无法将 G 的任何额外边添加到子集 L 中，则独立边集将被称为 G 的最大独立边集。最大独立边集的示例如下所述

从上图中，我们将考虑以下子集。

L1= {x, y}

L2 = {{y, v} {z, f}}

L3 = {{x, v} {y, z}, {u, f}}

L4 = {{x, y} {z, f}}

子集 L2 和 L3 是最大独立边集，因为在上面的图中，我们可以看到子集 L2 和 L3 无法添加任何其他不相邻的边。因此，我们可以说子集 L2 和 L3 被称为最大独立边集。

最大独立边集

我们可以通过计算该图中的最大边数来计算 G 的最大独立边集。我们可以借助以下公式计算最大独立边集

G 的最大独立边集中的边数 (β₁

) = G 的匹配数 = G 的独立边数

最大独立边集的示例如下所述

从上图中，我们将获得关于子集的以下细节。

L1= {x, y}

L2 = {{y, v} {z, f}}

L3 = {{x, v} {y, z}, {u, f}}

L4 = {{x, y} {z, f}}

在上面的图中，我们可以看到子集 L3 具有最大边数，并且这些边不相邻。因此，子集 L3 可以称为最大独立边集。子集 L3 的最大独立边集可以这样表示

β1 = 3

注意：如果存在一个没有孤立顶点的图 G，那么它将是

α1 + β1 = 图中顶点的数量 = |V|

例如：在此示例中，我们将展示 K_n/C_n/W_n 的边覆盖数，如下所示

独立边数 = β₁ = [n/2] α₁ + β₁ = n。

边覆盖

• 图 G 的边覆盖可以描述为一组边 F，它能够覆盖 G 的所有顶点。在边覆盖过程中，图 G 的每个顶点都与集合 F 中的一条边关联。
• 参数 β₁(G) = min |F| 可以称为图 G 的边覆盖数。这里，F 用于表示 G 的边覆盖。边覆盖数也可以称为孤立顶点（如果存在）的数量与能够覆盖所有顶点的最小边数之和。
• 如果存在边覆盖 F，且 |F| = β₁(G)，则称其为最小边覆盖。边覆盖的示例如下所述

从上图中，我们有以下关于边覆盖的细节。

E1= {x, y, z, u}

E2 = {x, u}

E3 = {y, z}

因此，边覆盖数或覆盖所有顶点的最小边数 β₁ (G) = 2。

注意：对于图 G，α₁(G) + β₁(G) = n，其中 n 用于表示 G 中顶点的数量。

独立顶点集

假设有一个图 G = (V, E)。如果存在一个子集 S，其中该子集中没有两个顶点相邻，在这种情况下，V 的子集 S 将被称为 G 的独立顶点集。独立顶点集的示例如下所述

从上图中，我们将考虑以下子集。

S1= {v}

S2 = {v, f}

S3 = {x, g, z}

S4 = {v, u}

在上面的图中，我们可以看到子集 S2、S3 和 S4 不包含任何与其他顶点相邻的顶点。因此，我们可以说子集 S2、S3 和 S4 被称为独立顶点集。但是子集 S1 不是独立顶点集，因为我们可以借助至少两个顶点形成一个独立顶点集，但在 S1 中只有一个顶点。因此，独立顶点集不能用子集 S1 表示。

最大独立顶点集

假设有一个图 G。如果存在一个子集 S，其中无法将 G 的任何其他额外顶点添加到 S 中，在这种情况下，独立顶点集将被称为最大独立顶点集。独立顶点集的示例如下所述

从上图中，我们将考虑以下子集。

S1= {v}

S2 = {v, f}

S3 = {x, g, z}

S4 = {v, u}

子集 S2 和 S3 是最大独立顶点集，因为在上面的图中，我们可以看到子集 L2 和 L3 无法添加任何其他顶点。因此，我们可以说子集 S2 和 S3 被称为最大独立边集。但是子集 S1 和 S4 不是最大独立顶点集，因为我们可以向其中添加另一个顶点。

最大独立顶点集

我们可以通过计算该图中的最大顶点数来计算 G 的最大独立顶点集。最大独立顶点集的示例如下所述

从上图中，我们将考虑以下子集。

S1= {v}

S2 = {v, f}

S3 = {x, g, z}

S4 = {v, u}

在上面的图中，我们可以看到子集 S3 覆盖了最大数量的顶点。因此，我们可以说子集 S3 被称为 G 的最大独立顶点集。在最大独立顶点集中，顶点的数量可以称为 G 的独立顶点数 (β₂)。

例如

如果存在完全图 K_n，则顶点覆盖数和顶点独立数可以通过以下公式确定

顶点独立数 = α₂ = n−1

顶点覆盖数 = β₂ = 1

所以我们有以下内容

α₂ + β₂ = n

完全图的每个顶点都将与其余的 (n-1) 个顶点相邻。因此，K_n 的最大独立集将只有一个顶点。

因此，β₂ = 1 且 α₂=|v| − β₂ = n-1

注意：如果存在图 G = (V, E)，则它将包含以下内容
α₂ + β₂ = |V|

如果 S 是图 G 的独立顶点集，则 G 的顶点覆盖将是 (V - S)。

顶点覆盖

• 图 G 的顶点覆盖可以描述为一组顶点 K，它能够覆盖 G 的所有边。在顶点覆盖过程中，一个顶点应该覆盖集合 K 中 G 的每条边。
• 参数 β₀(G) = min |K| 可以称为图 G 的顶点覆盖数。这里，K 用于表示 G 的顶点覆盖。顶点覆盖数也可以称为能够覆盖所有边的最小顶点数。
• 如果存在顶点覆盖 K，且 |K| = β₀(G)，则称其为最小顶点覆盖。顶点覆盖的示例如下所述

从上图中，我们有以下关于顶点覆盖的细节。

V1= {x, z}

V2 = {y, u}

V3 = {x, y, z}

V4 = {x, y, z, u} 等

因此，顶点覆盖数或覆盖所有边的最小顶点数 β₀ (G) = 2。

注意

• 对于图 G，α₀(G) + β₀(G) = n，其中 n 用于表示该图中的顶点数。
• 当且仅当存在 V(G) 时，I 才被称为图 G 中的独立集。这里，I 用于表示 G 的顶点覆盖。

匹配

• 我们可以通过计算不相邻边的集合来确定匹配。对于匹配，集合中的任意两条边不应相互相邻。
• 参数 α₁(G) = max { |M| 可以称为图 G 的匹配数。这里，M 用于表示 G 中的匹配。匹配数也可以称为不相邻边的最大数量。
• 如果存在匹配 M，且 |M| = α₁(G)，则称其为最大匹配。匹配的示例如下所述

从上图中，我们有以下关于匹配的细节。

M1= {x}

M2 = {y}

M3 = {z}

M4 = {u}

M5 = {x, u}

M6 = {y, z}

因此，匹配数或不相邻边的最大数量 α₁(G) = 2。

完全匹配

如果一个图的匹配包含 G 的所有顶点，在这种情况下，该匹配将被称为完全匹配。我们也可以称完全匹配为完美匹配。