最后更新: 2025-01-22 10:32 查看: 135 次纠错评论(0) 课件开VIP

独立集、覆盖

设无自环图 $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)$ 。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇： Hall定理

下一篇：没有了

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