图论 - 独立集

---

独立集合用集合来表示，其中

• 不应有任何边缘彼此相邻。任何两条边之间不应有任何公共顶点。

• 不应有任何顶点彼此相邻。任何两个顶点之间不应有任何公共边。

独立线组

让 '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|

例子

_{行覆盖 K n} /C _n /w _n的数量，

$$\alpha 1 = \lceil\frac{n}{2}\rceil\begin{cases}\frac{n}{2}\:如果\:n\:是偶数 \\\frac{n+ 1}{2}\:如果\:n\:是奇数\end{情况}$$

行无关数（匹配数）=β ₁ = [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的独立顶点数(β ₂ )。

例子

对于完整图 K _n，

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

顶点独立数 = β ₂ = 1

你有 α ₂ + β ₂ = n

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

因此，β ₂ =1

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

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

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