图论 - 覆盖

覆盖图是包含所有顶点或与某个其他图相对应的所有边的子图。包含所有顶点的子图称为线/边覆盖。包含所有边的子图称为顶点覆盖。

线覆盖

设 G = (V, E) 为图。如果 G 的每个顶点都与 C 中的至少一条边相关，则子集 C(E) 称为 G 的线覆盖，即

deg(V) ≥ 1 ∀ V ∈ G

因为每个顶点都通过一条边与另一个顶点相连。因此，它的最小度为 1。

示例

查看以下图表 −

其具有线覆盖的子图如下 −

C₁ = {{a, b}, {c, d}}

C₂ = {{a, d}, {b, c}}

C₃ = {{a, b}, {b, c}, {b, d}}

C₄ = {{a, b}, {b, c}, {c, d}}

当且仅当"G"具有孤立顶点时，"G"的线覆盖才不存在。具有"n"个顶点的图的线覆盖至少有 [n/2] 条边。

最小线覆盖

如果图 G 的线覆盖 C 没有边可从 C 中删除，则称该线覆盖为最小。

示例

在上图中，具有线覆盖的子图如下 −

C₁ = {{a, b}, {c, d}}

C₂ = {{a, d}, {b, c}}

C₃ = {{a, b}, {b, c}, {b, d}}

C₄ = {{a, b}, {b, c}, {c, d}}

这里，C₁、C₂、C₃是最小线覆盖，而C₄不是，因为我们可以删除{b，c}。

最小线覆盖

它也被称为最小最小线覆盖。具有最少边数的最小线覆盖称为"G"的最小线覆盖。 'G' 中最小线覆盖的边数称为 'G' 的线覆盖数 (α₁)。

示例

在上面的例子中，C₁ 和 C₂ 是 G 的最小线覆盖，并且 α₁ = 2。

• 每个线覆盖都包含一个最小线覆盖。

• 每个线覆盖都不包含最小线覆盖（C₃ 不包含任何最小线覆盖。

• 没有最小线覆盖包含循环。

• 如果线覆盖 'C' 不包含长度为 3 或更大的路径，则 'C' 是最小线覆盖，因为 'C' 的所有组件都是星形图，并且从星形图中，没有边可以已删除。

顶点覆盖

设'G' = (V, E) 为一个图。如果'G' 的每条边都与'K' 中的顶点相关或被'K' 中的顶点覆盖，则 V 的子集 K 称为'G' 的顶点覆盖。

示例

查看以下图 −

可从上图得出的子图如下 −

K₁ = {b, c}

K₂ = {a, b, c}

K₃ = {b, c, d}

K₄ = {a, d}

这里，K1、K2和K3具有顶点覆盖，而K4没有任何顶点覆盖，因为它不覆盖边{bc}。

最小顶点覆盖

如果图"G"的顶点"K"中没有顶点可以从"K"中删除，则称该顶点"K"为​​最小顶点覆盖。

示例

在上图中，具有顶点覆盖的子图如下 −

K1 = {b, c

K2 = {a, b, c

K3 = {b, c, d

这里，K1和K2 是最小顶点覆盖，而在 K3 中，可以删除顶点"d"。

最小顶点覆盖

它也被称为最小最小顶点覆盖。图"G"的顶点数最少的最小顶点覆盖称为最小顶点覆盖。

"G"的最小顶点覆盖中的顶点数称为 G 的顶点覆盖数 (α₂)。

示例

下图中，具有顶点覆盖的子图如下 −

K1 = {b, c

K2 = {a, b, c

K3 = {b, c, d

这里，K1 是 G 的最小顶点覆盖，因为它只有两个顶点。α₂ = 2.