图论 - 覆盖

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

线路覆盖

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

deg(V) ≥ 1 ∀ V ∈ G

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

例子

看一下下图 -

线路覆盖

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

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

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

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

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

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

最小线覆盖

如果无法从 C 中删除任何边，则称覆盖图 G 的 C 的线是最小的。

例子

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

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

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

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

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

这里，C 1、C 2、C 3是最小线覆盖，而 C 4不是，因为我们可以删除 {b, c}。

最小线路覆盖

它也称为最小最小线覆盖。具有最少边数的最小线覆盖称为“G”的最小线覆盖。覆盖“G”的最小线中的边数称为“G”的线覆盖数（α 1）。

例子

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

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

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

  • 最小线覆盖不包含循环。

  • 如果覆盖“C”的线不包含长度为 3 或以上的路径，则“C”是最小线覆盖，因为“C”的所有组件都是星形图，并且从星形图中不能删除任何边。

顶点覆盖

让 'G' = (V, E) 成为一个图。如果“G”的每条边都与“K”中的顶点重合或被“K”中的顶点覆盖，则 V 的子集 K 称为“G”的顶点覆盖。

例子

看一下下图 -

顶点覆盖

从上图可以得出的子图如下 -

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b,c,d}

K 4 = {a, d}

这里，K 1、K 2和K 3具有顶点覆盖，而K 4没有任何顶点覆盖，因为它不覆盖边{bc}。

最小顶点覆盖

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

例子

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

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b,c,d}

这里，K 1和K 2是最小顶点覆盖，而在K 3中，顶点“d”可以被删除。

最小顶点覆盖

它也被称为最小最小顶点覆盖。具有最少顶点数的图“G”的最小顶点覆盖称为最小顶点覆盖。

“G”的最小顶点覆盖中的顶点数称为G的顶点覆盖数(α 2 )。

例子

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

K 1 = {b, c}

K 2 = {a, b, c}

K 3 = {b,c,d}

最小顶点覆盖

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