支配集、独立集、覆盖集

1. 定义

1.1 支配集

• 设无向简单图 $G = \lt V,E \gt, V^* \subseteq V$，若 $\forall v_i \in V - V^*, \exists v_j \in V^*$ 使得 $(v_i,V_j) \in E$，则称 $V^*$ 为 $G$ 的一个支配集，并称 $v_j$ 支配 $v_i$ 。

• 设 $V*$ 是 $G$ 的支配集，且 $V*$ 的任何真子集都不是支配集，则称 $V*$ 为极小支配集。

• $G$ 的顶点最少的支配集称作 $G$ 的最小支配集。

• 最小支配集中的顶点个数称作 $G$ 的支配数，记作 $\gamma_0(G)$，简记为 $\gamma_0$ 。

1.2 独立集

1.2.1 点独立集

• 设无向简单图 $G = \lt V,E \gt, V^* \subseteq V$，若 $V*$ 中任何两个顶点均不相邻，则称 $V*$ 为 $G$ 的点独立集，简称独立集。

• 若 $V*$ 中再加入任何其他的顶点都不是独立集，则称 $V*$ 为极大点独立集。

• $G$ 的顶点数最多的点独立集称作 $G$ 的最大点独立集。

• 最大独立集的顶点数称作 $G$ 的点独立数，记作 $\beta_0(G)$，简记为 $\beta_0$ 。

1.2.2 边独立集

• 设无向简单图 $G = \lt V,E \gt, V^* \subseteq V$，若 $E^*$ 中任何两条边均不相邻，则称 $E^*$ 为 $G$ 的边独立集，也称作 $G$ 的匹配。

• 若在 *$G^*$ 中再加任意一条边后，所得集合都不是匹配，则称 $E^*$ 为极大匹配。

• $G$ 的边数最多的匹配称作最大匹配。

• 最大匹配中的边数称作边独立数或匹配数，记作 $\beta_1(G)$，简记为 $\beta_1$ 。

• 设 $M$ 为图 $G = \lt V,E \gt$ 的一个匹配：

1. 称 $M$ 中的边为匹配边，不在 $M$ 中的边为非匹配边。
2. 与匹配边相关联的顶点为饱和点，不与匹配边相关联的顶点为非饱和点。
3. 若 $G$ 中每个顶点都是饱和点，则称 $M$ 为 $G$ 的完美匹配。
4. $G$ 中由匹配边和非匹配边交替构成的路径称作交错路径，起点和重点都是非饱和点的交错路径称作可增广的交错路径。
5. $G$ 中由匹配边和非匹配边交替构成的圈称作交错圈。

• 设 $G = \lt V_1,V_2,E \gt$ 为二部图，$|V_1| \leq |V_2|$，$M$ 为 $G$ 的一个匹配且 $|M| = |V_1|$，称 $M$ 为 $V_1$ 到 $V_2$ 的完备匹配。

1.3 覆盖集

1.3.1 点覆盖集

• 设无向简单图 $G = \lt V,E \gt, V^* \subseteq V$，若 $\forall e \in E, \exists v \in V^*$ 使得 $v$ 与 $e$ 相关联，则称 $V^*$ 为 $G$ 的点覆盖集，简称为点覆盖，并称 $v$ 覆盖 $e$ 。

• 设 $V^*$ 是 $G$ 的点覆盖，若 $V^*$ 的任何真子集都不是点覆盖，则称 $V^*$ 为极小点覆盖。

• $G$ 的顶点个数最少的点覆盖称为 $G$ 的最小点覆盖。

• 最小点覆盖中的顶点个数称作 $G$ 的点覆盖数，记作 $\alpha_0(G)$，简记为 $\alpha_0$ 。

1.3.2 边覆盖集

• 设无向简单图 $G = \lt V,E \gt$ 没有孤立点，$E^* \subseteq E$，若 $\forall v \in V, \exists e \in E^*$ 使得 $v$ 与 $e$ 相关联，则称 $E^*$ 为边覆盖集，简称为边覆盖，并称 $e$ 覆盖 $v$ 。

• 设 $E^*$ 为边覆盖，若 $E^*$ 的任何真子集都不是边覆盖集，则称 $E^*$ 为极小边覆盖集。

• $G$ 的边数最少的边覆盖称为 $G$ 的最小边覆盖。

• 最小边覆盖中的边数称作 $G$ 的边覆盖数，记作 $\alpha_1(G)$，简记为 $\alpha_1$ 。

2. 性质

• 无向简单图的极大点独立集都是极小支配集。

• 设无向简单图 $G = \lt V,E \gt, V^* \subseteq V$，则 $V^*$ 为 $G$ 的点覆盖集当且仅当 $\overline{V^*} = V - V^*$ 为 $G$ 的点独立集。

推论

$$\begin{array}{c} \alpha_0 + \beta_0 = |V| \end{array}$$

• 设 $n$ 阶图 $G$ 中无孤立点：

1. 设 $M$ 为 $G$ 的一个最大匹配，对 $G$ 中每个非饱和点均取一条与其关联的边，组成边集 $N$，则 $W = M \cup N$ 为 $G$ 的最小边覆盖。
2. 设 $W_1$ 为 $G$ 的一个最小边覆盖，若 $W_1$ 中存在相邻的边就移去其中的一条，设移去的边集为 $N_1$，则 $M_1 = W_1 - N_1$ 为 $G$ 的最大匹配。
3. $G$ 的边覆盖数 $\alpha_1$ 与匹配数 $\beta_1$ 满足：$\alpha_1 + \beta_1 = n$ 。

推论

设图 $G$ 无孤立点，$M$ 是 $G$ 的一个匹配，$W$ 是 $G$ 的一个边覆盖，则 $|M| \leq |W|$，且当等号成立时，$M$ 是 $G$ 的完美匹配，$W$ 是 $G$ 的最小边覆盖。

• 二部图 $G = \lt V_1,V_2,E \gt$ 的完备匹配是最大匹配，但最大匹配不一定是完备匹配。当 $|V_1| = |V_2|$ 时，完备匹配是完美匹配。

• (相异性条件)：设二部图 $G = \lt V_1,V_2,E \gt$，其中 $|V_1| \leq |V_2|$，则 $G$ 中存在 $V_1$ 到 $V_2$ 的完备匹配当且仅当 $V_1$ 中任意 $k(k = 1,2,\cdots,|V_1|)$ 个顶点至少与 $V_2$ 中的 $k$ 个顶点相邻。

• (t 条件)：设二部图 $G = \lt V_1,V_2,E \gt$，如果存在正整数 $t$，使得 $V_1$ 中每个顶点至少关联 $t$ 条边，而 $V_2$ 中每个顶点至多关联 $t$ 条边，则 $G$ 中存在 $V_1$ 到 $V_2$ 的完备匹配。