覆盖
| 覆盖 | |
|---|---|
| 术语名称 | 覆盖 |
| 英语名称 | cover |
| 别名 | 集合覆盖, covering |
集合的覆盖(cover)是指对一个集合，一个集族仅包含其非空子集，且其中所有子集的并集包含原集合。
定义
对于集合 [math]\displaystyle{ A }[/math]，如果集族 [math]\displaystyle{ C = \{A_i\}_{i \in I} }[/math] 满足：
- [math]\displaystyle{ A_i\neq\varnothing }[/math]
- [math]\displaystyle{ A = \bigcup_{i \in I} A_i }[/math]
则称集族 [math]\displaystyle{ C }[/math] 是集合 [math]\displaystyle{ A }[/math] 的一个覆盖(cover)。
注：
- 以上定义为标准定义，但也存在不一致的说法。有些定义中要求 [math]\displaystyle{ A }[/math] 非空，也有一些定义中不要求 [math]\displaystyle{ A_i }[/math] 非空。
- 这一条件隐性地要求了子集关系，即 [math]\displaystyle{ \forall i \in I, A_i \subseteq A }[/math] 。有的定义中也会明确指出这些集合是子集，但不是必须明确指出。
性质
- 任意非空集合都至少存在一个覆盖，例如 [math]\displaystyle{ \{A\} }[/math] （由原集合自身构成的覆盖），称为平凡覆盖(trivial cover)。
- 如果 [math]\displaystyle{ C }[/math] 是 [math]\displaystyle{ A }[/math] 的覆盖，那么任何包含 [math]\displaystyle{ C }[/math] 的集族也是 [math]\displaystyle{ A }[/math] 的覆盖。
- 覆盖与划分的关系：每个划分都是覆盖，但覆盖不一定是划分（覆盖中的集合可以相交，有些定义不要求覆盖中的集合非空）。
- 覆盖的细化：如果覆盖 [math]\displaystyle{ \mathcal{D} }[/math] 中每个集合都包含于覆盖 [math]\displaystyle{ \mathcal{C} }[/math] 中的某个集合，则称 [math]\displaystyle{ \mathcal{D} }[/math] 是 [math]\displaystyle{ \mathcal{C} }[/math] 的加细。
特殊类型
子覆盖
如果覆盖 [math]\displaystyle{ \mathcal{C}' \subseteq \mathcal{C} }[/math] 本身也是覆盖，则称 [math]\displaystyle{ \mathcal{C}' }[/math] 是 [math]\displaystyle{ \mathcal{C} }[/math] 的子覆盖。
有限覆盖
如果覆盖 [math]\displaystyle{ \mathcal{C} }[/math] 是有限集，则称该覆盖为有限覆盖。