最后更新: 2025-01-22 10:32 查看: 67 次反馈刷题

独立集、覆盖

设无自环图 $G=(V, E)$ ，考虑如下的 $V$ 的子集：
定义 11.13 （独立集）若 $V$ 的一个子集 $I$ 中任意两个顶点在 $G$ 中都不相邻，则称 $I$ 是 $G$ 的一个独立集。若 $G$ 中不含有满足 $\left|I^{\prime}\right|>|I|$ 的独立集 $I^{\prime}$ ，则称 $I$ 为 $G$ 的最大独立集。它的顶点数称为 $G$的独立数，记为 $\beta_0(G)$ 。

定义 11.14 （点覆盖）若 $V$ 的一个子集 $C$ 使得 $G$ 的每一条边至少有一个端点在 $C$ 中，则称
$C$ 是 $G$ 的一个点覆盖。若 $G$ 中不含有满足 $\left|C^{\prime}\right|<|C|$ 的点覆盖 $C^{\prime}$ ，则称 $C$ 是 $G$ 的最小点覆盖。它的顶点数称为 $G$ 的点覆盖数，记为 $\alpha_0(G)$ 。

一个图的点覆盖数与独立点数之间有着密切而简单的联系。
定理11．10 $V$ 的子集 $I$ 是 $G$ 的独立集当且仅当 $V-I$ 是 $G$ 的点覆盖。
证明：由独立集的定义，$I$ 是 $G$ 的独立集当且仅当 $G$ 中每一条边至少有一个端点在 $V-I$中，即，$V-I$ 是 $G$ 的点覆盖。

推论11．1 对于 $n$ 个顶点的图 $G$ ，有 $\alpha_0(G)+\beta_0(G)=n$ 。
证明：设 $I$ 是 $G$ 的最大独立集，$C$ 是 $G$ 的最小点覆盖，则 $V-C$ 是 $G$ 的独立集，$V-I$ 是 $G$ 的点覆盖，所以 $n-\beta_0=|V-I| \geqslant \alpha_0, n-\alpha_0=|V-C| \leqslant \beta_0$ ，因此 $\alpha_0+\beta_0=n^{\circ}$

设图 $G=(V, E)$ ，上一节讨论了 $E$ 的子集即匹配，称最大匹配的边数为 $G$ 的边独立数，记为 $\beta_1(G)$ 。下面考虑 $E$ 的另一个子集。

定义 11.15 （边覆盖）若 $E$ 的一个子集 $L$ 使得 $G$ 的每一个顶点至少与 $L$ 中一条边关联，称 $L$是 $G$ 的一个边覆盖。若 $G$ 中不含有满足 $\left|L^{\prime}\right|<|L|$ 的点覆盖 $L^{\prime}$ ，则称 $L$ 是 $G$ 的最小边覆盖。它的边数称为 $G$ 的边覆盖数，记为 $\alpha_1(G)$ 。

显然 $G$ 有边覆盖的充要条件是 $\delta>0$ 。
$\alpha_1(G)$ 和 $\beta_1(G)$ 也有类似于 $\alpha_0(G)$ 和 $\beta_0(G)$ 的一个简单关系式。但是匹配和边覆盖之间并没有定理11．9的互补关系。

定理11．11 对于 $n$ 个顶点图 $G$ ，且 $\delta(G)>0$ ，则 $\alpha_1(G)+\beta_1(G)=n$ 。
证明：设 $M$ 是 $G$ 的最大匹配，$|M|=\beta_1(G)$ 。设 $F$ 是关于 $M$ 的未饱和点集合，有 $|F|=n-2|M|$ 。又 $\delta>0$ ，对于 $F$ 中每个顶点 $v$ ，取一条与 $v$ 关联的边，这些边与 $M$ 构成边集 $L$ ，显然 $L$ 是一个边覆盖，且 $|L|=|M|+|F|$ ，于是 $|M|+|L|=n$ 。又 $|L| \geqslant \alpha_1(G)$ ，所以 $\alpha_1(G) \leqslant n-\beta_1(G)$ ，即 $\alpha_1(G)+\beta_1(G) \leqslant n$ 。

设 $L$ 是 $G$ 的最小边覆盖，$L=\alpha_1(G)$ 。令 $H=G(L), H$ 有 $n$ 个顶点。又设 $M$ 是 $H$ 的最大匹配，显
然也是 $G$ 的匹配，且 $M \subseteq L$ 。以 $U$ 表示 $H$ 中关于 $M$ 的未饱和点集合，且有 $|U|=n-2|M|$ 。因为 $M$ 是 $H$ 的最大匹配，所以 $H$ 中 $U$ 的顶点互不相邻，即 $U$ 中顶点关联的边在 $L-M$ 中。因此 $|L|-|M|=|L-M|$ $\geqslant|U|=n-2|M|$ 。于是 $\alpha_1(G)+\beta_1(G) \geqslant n$ 。

所以 $\alpha_1(G)+\beta_1(G)=n$ 。
科尼格（König）定理
对于任一个点覆盖 $C$ 和任一个匹配 $M, C$ 中至少包含匹配 $M$ 中每一边的一个端点，所以总有 $|M| \leqslant|C|$ ，显然 $\beta_1(G) \leqslant \alpha_0(G)$ 。下面可以证明对于二分图 $G$ ，等式成立。这个结果是科尼格在 1931 年给出的，它与霍尔定理紧密相关。在给出它的证明之前，先证明引理。

引理11．1 设 $M$ 是一个匹配，$C$ 是点覆盖，且 $|M|=|C|$ ，则 $M$ 是最大匹配，$C$ 是最小点覆盖。
证明：若 $M^*$ 是 $G$ 的最大匹配，$\check{C}$ 是 $G$ 的最小点覆盖，$\beta_1(G)=\left|M^*\right|, \alpha_0(G)=|C \check{C}|$ ，则 $|M| \leqslant \beta_1(G)$ $\leqslant \alpha_0(G) \leqslant|C|$ 。由于 $|M|=|C|$ ，所以 $|M|=\left|M^*\right|=\beta_1(G),|C|=|C \check{C}|=\alpha_0(G)$ 。

定理 11.12 （科尼格定理）：在二分图 $G\left(V_1, V_2\right)$ 中，有 $\beta_1(G)=\alpha_0(G)$ 。
证明：设 $M^*$ 是 $G$ 的最大匹配，$U$ 是 $V_1$ 中关于 $M^*$ 未饱和点集合。又设 $Z$ 表示与 $U$ 中每一个顶点有关于 $M^*$ 交错路相连的顶点集合，因为 $M^*$ 是最大匹配，所以 $G$ 中不包含关于 $M^*$ 的增广路，由 $M$ 为 $G$ 的一个最大匹配当且仅当 $G$ 中不存在关于 $M$ 的增广路，$U$ 是Z中仅有的未被 $M *$ 饱和的顶点集合。令 $A=Z \cap V_1, T=Z \cap V_2$ ，由定理 11.8 的证明，可知 $T$ 中顶点关于 $M^*$ 是饱和的，并且 $\Gamma(A)=T$ 。
定义 $\check{C}=\left(V_1-A\right) \cup T, G$ 中每一边至少有一个顶点在 $\check{C}$ 中，因为否则至少有一边，其一端点在 $A$ 中，另一端点在 $V_2-T$ 中，这与 $\Gamma(A)=T$ 矛盾，所以 $\check{C}$ 是 $G$ 的一个点覆盖。显然，$|\check{C}|=\left|M^*\right|$ 。又由引理 11．1，得 $\beta_1(G)=\alpha_0(G)$ 。

推论11．2 在 $\delta>0$ 的二分图 $G\left(V_1, V_2\right)$ 中，有 $\beta_0(G)=\alpha_1(G)$ 。
证明：利用定理 11.9 的推论 11.1 以及定理 11.10 可知 $\alpha_1(G)+\beta_1(G)=\alpha_0(G)+\beta_0(G)$ 。再由定理 11.11 即得 $\beta_0(G)=\alpha_1(G)$ 。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇： Hall定理

下一篇：没有了

本文对您是否有用？有用 (0) 无用 (0)