数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究线/边覆盖
覆盖图是一个子图，它包含与另一个图对应的所有顶点或所有边。包含所有顶点的子图称为**线/边覆盖**。包含所有边的子图称为**顶点覆盖**。
线覆盖
设 G = (V, E) 为一个图。如果 G 的每个顶点至少与 C 中的一条边关联，则子集 C(E) 称为 G 的线覆盖，即：
deg(V) ≥ 1 ∀ V ∈ G
因为每个顶点都通过一条边与另一个顶点连接。因此，它具有至少 1 的最小度。
示例
请查看以下图形 -
其具有线覆盖的子图如下 -
C1 = {{a, b}, {c, d}}
C2 = {{a, d}, {b, c}}
C3 = {{a, b}, {b, c}, {b, d}}
C4 = {{a, b}, {b, c}, {c, d}}当且仅当 'G' 具有孤立顶点时，'G' 的线覆盖不存在。具有 'n' 个顶点的图的线覆盖至少具有 [n/2] 条边。
最小线覆盖
如果无法从 C 中删除任何边，则图 G 的线覆盖 C 被称为最小**线覆盖**。
示例
在上图中，具有线覆盖的子图如下 -
C1 = {{a, b}, {c, d}}
C2 = {{a, d}, {b, c}}
C3 = {{a, b}, {b, c}, {b, d}}
C4 = {{a, b}, {b, c}, {c, d}}这里，C1、C2、C3 是最小线覆盖，而 C4 不是，因为我们可以删除 {b, c}。
最小线覆盖
它也被称为**最小的最小线覆盖**。具有最少边数的最小线覆盖称为 'G' 的最小线覆盖。'G' 中最小线覆盖中的边数称为 'G' 的**线覆盖数**(α1)。
示例
在上例中，C1 和 C2 是 G 的最小线覆盖，α1 = 2。
每个线覆盖都包含一个最小线覆盖。
并非每个线覆盖都包含一个最小线覆盖（C3 不包含任何最小线覆盖）。
没有最小线覆盖包含环。
如果线覆盖 'C' 不包含长度为 3 或更大的路径，则 'C' 是一个最小线覆盖，因为 'C' 的所有组成部分都是星形图，并且从星形图中无法删除任何边。
更新于: 2019年8月23日
240 次浏览
广告