01.支配集、点独立集与点覆盖集

一、支配集理论

定义9.1.1（支配集）

设无向简单图$G=(V,E)$，$V^* \subseteq V$满足：

1. 支配条件：$\forall v_i \in V \setminus V^*,\ \exists v_j \in V^*$使得$(v_i, v_j) \in E$
2. 极小性：$V^*$的任何真子集都不满足支配条件 → 称为极小支配集
3. 最优性：顶点数最少的支配集称为最小支配集
4. 支配数：记作$\gamma_0(G)$，表示最小支配集的顶点数

二、点独立集理论

定义9.1.2（点独立集）

设无向简单图$G=(V,E)$，$V^* \subseteq V$满足：

1. 独立性：$V^*$中任意两顶点不相邻
2. 极大性：$V^*$添加任何新顶点后失去独立性 → 称为极大点独立集
3. 最优性：顶点数最多的点独立集称为最大点独立集
4. 独立数：记作$\beta_0(G)$，表示最大点独立集的顶点数

三、点覆盖集理论

定义9.1.3（点覆盖集）

设无向简单图$G=(V,E)$，$V^* \subseteq V$满足：

1. 覆盖性：$\forall e \in E,\ \exists v \in V^*$与$e$关联
2. 极小性：$V^*$的任何真子集都不满足覆盖性 → 称为极小点覆盖
3. 最优性：顶点数最少的点覆盖称为最小点覆盖
4. 覆盖数：记作$\alpha_0(G)$，表示最小点覆盖的顶点数

四、核心定理体系

定理9.1.1（独立集与支配集关系）

设无孤立点的无向简单图$G$，则：

定理9.1.2（覆盖集与独立集对偶性）

设无孤立点的无向简单图$G$，则：

推论9.1.1（参数关系定理）

对于$n$阶无孤立点图$G$：

1. 极小-极大对应： $$V^*\text{是极小点覆盖} \iff V \setminus V^*\text{是极大点独立集}$$
2. 数值关系： $$\alpha_0(G) + \beta_0(G) = n$$

五、概念关系图谱