---

图论 - 独立集

独立集以集合表示，其中

• 不应存在任何相邻的边。任何两个边之间都不应有任何共同顶点。

• 不应存在任何相邻的顶点。任何两个顶点之间都不应有任何共同边。

独立线集

设"G"= (V, E) 为图。如果 L 中没有两条边相邻，则 E 的子集 L 称为"G"的独立线集。这样的集合称为独立线集。

示例

让我们考虑以下子集 −

L1 = {a,b}
L2 = {a,b} {c,e}
L3 = {a,d} {b,c}

在此示例中，子集 L2 和 L3 显然不是给定图中的相邻边。它们是独立线集。但是 L1 不是独立线集，因为要制作独立线集，至少应该有两条边。

最大独立线集

如果"G"没有其他边可以添加到"L"，则独立线集被称为图"G"的最大独立线集。

示例

让我们考虑以下子集 −

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L₂ 和 L₃ 是最大独立线集/最大匹配。只有这两个子集没有机会添加任何其他非相邻边。因此这两个子集被视为最大独立线集。

最大独立线集

具有最大边数的"G"的最大独立线集称为"G"的最大独立线集。

Number of edges in a maximum independent line set of G (β1)
   = Line independent number of G
   = Matching number of G

示例

让我们考虑以下子集 −

L1 = {a, b}
L2 = {{b, e}, {c, f}}
L3 = {{a, e}, {b, c}, {d, f}}
L4 = {{a, b}, {c, f}}

L₃ 是 G 中最大独立线集，其中最大边不是图中的相邻边，用 β1 = 3 表示。

注意 − 对于任何没有孤立顶点的图 G，

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

示例

Kn/C_n/w_n 的线覆盖数，

$$\alpha 1 = \lceil\frac{n}{2} ceil\begin{cases}\frac{n}{2}\:if\:n\:is\:even \\frac{n+1}{2}\:if\:n\:is\:odd\end{cases}$$

线独立数（匹配数）= β₁ = [n/2] α₁ + β₁ = n。

独立顶点集

设'G' = (V, E) 为图。如果'S' 中没有两个顶点相邻，则'V' 的子集称为'G' 的独立集。

示例

考虑上述图中的以下子集 −

S1 = {e}

S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

显然 S₁ 不是独立顶点集，因为要得到独立顶点集，图中至少应该有两个顶点。但这里情况并非如此。子集 S₂、S₃ 和 S₄ 是独立顶点集，因为没有顶点与子集中的任何一个顶点相邻。

最大独立顶点集

假设"G"是一个图，如果"G"中没有其他顶点可以添加到"S"，则"G"的独立顶点集被称为最大。

示例

考虑上述图中的以下子集。

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

S₂ 和 S₃ 是"G"的最大独立顶点集。在 S₁ 和 S₄ 中，我们可以添加其他顶点；但在 S₂ 和 S₃ 中，我们不能添加任何其他顶点。

最大独立顶点集

具有最大顶点数的"G"的最大独立顶点集称为最大独立顶点集。

示例

考虑上图中的以下子集 −

S1 = {e}
S2 = {e, f}
S3 = {a, g, c}
S4 = {e, d}

只有 S₃ 是最大独立顶点集，因为它覆盖了最多的顶点。"G"的最大独立顶点集的顶点数称为 G 的独立顶点数 (β₂)。

示例

对于完全图 Kn，

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

顶点独立数 = β₂ = 1

您有 α₂ + β₂ = n

在完全图中，每个顶点都与其剩余的 (n − 1) 个顶点相邻。因此，Kn的最大独立集仅包含一个顶点。

因此，β₂=1

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

注意 − 对于任何图 'G' = (V, E)

• α₂ + β₂ = |v|
• 如果 'S' 是 'G' 的独立顶点集，则 (V – S) 是 G 的顶点覆盖。

---