最后更新: 2024-04-06 21:42 查看: 163 次反馈刷题

覆盖集、独立集和匹配

## 覆盖集、独立集和匹配
定义 23 设 $G=<V, E>$ 为无向简单图, $V^* \subseteq V$, 若 $G$ 的每条边至少有一个端点属于 $V^*$, 则称 $V^*$ 为 $G$ 的一个结点对边的覆盖集 (或点覆盖集或点覆盖)。若点覆盖 $V *$ 的任一真子集都不是点覆盖, 则称 $V *$ 为极小点覆盖。结点数最少的极小点覆盖称为最小点覆盖,其结点数称为点覆盖数, 记作 $\alpha_0$ 。

定义 24 设 $G=<V, E>$ 为无向简单图, $E^* \subseteq E$, 若 $G$ 的每个结点是 $E^*$ 中至少一条边的端点, 则称 $E^*$ 为 $G$ 的一个边对结点的覆盖集 (或边覆盖集或边覆盖). 若边覆盖 $E *$ 的任一真子集都不是边覆盖, 则称 $E^*$ 为极小边覆盖。边数最少的极小边覆盖称为最小边覆盖,其边数称为边覆盖数, 记作 $\alpha_1$ 。

定义 25 设 $G=<V, E>$ 为无向图, $V^* \subseteq V$, 若 $V *$ 中任意两结点不相邻, 则称 $V *$ 为 $G$ 的点独立集。若在点独立集 $V *$ 中再加入任一结点 $v$, 则 $V * \mathrm{Y}\{v\}$ 不是点独立集, 则称 $V *$为极大点独立集。结点数最多的极大点独立集称为最大点独立集, 其结点数称为点独立数,记作 $\beta_0$ 。

定义 26 设 $G=<V, E>$ 为无向图, $E^* \subseteq E$, 若 $E^*$ 中任意两条边不相邻, 则称 $E^*$ 为 $G$中一个边独立集或匹配。若在匹配 $E^*$ 中再加入任一边 $e$, 则 $E^* \mathrm{Y}\{e\}$ 不是边独立集, 则称为 $E^*$ 为极大匹配或极大边独立集。边数最多的极大匹配称为最大匹配或最大边独立集, 其边数称为匹配数或边独立数, 记作 $\beta_1$ 。又常记匹配为 $M$ 。
定理 30 设 $G=(n, m)$ 为非平凡无向简单图, 则 $\alpha_0+\beta_0=n$ 。
定理 31 设 $G=(n, m)$ 为无孤立点的无向简单图, 则 $\alpha_1+\beta_1=n ; \beta_1 \leq \alpha_0 ; \beta_0 \leq \alpha_1$ 。
定义 27 设 $M$ 是 $G$ 中一匹配, 若 $G$ 的结点 $v$ 与 $M$ 中某条边关联, 则称 $v$ 为 $M$ 一饱和点或饱和点; 否则, 称 $v$ 为 $M$ 一非饱和点或非饱和点。若 $G$ 中所有结点都是 $M$ 一饱和点,则称 $M$ 为 $G$ 的一个完美匹配。

匹配问题与二部图密切相关, 有不少实际问题可化为在一个二部图中求匹配问题。例如, 有 $m$ 个人和 $n$ 项工作, 每个人都只熟悉这 $n$ 件工作中的某几件, 每一件工作需要一个人干, 能否将这 $n$ 件工作都安排给熟悉它的人干? 用一个二部图来表示该问题, $V_1$ 中的结点代表工作, $V_2$ 中的结点代表人, 当且仅当 $u \in V_2$ 熟悉工作 $v \in V_1$, 图中有边 $(u, v)$ 。因此,我们的问题就是能否在此二部图中确定一个匹配 $M$, 使 $V_1$ 中所有结点都是 $M$ 一饱和点。

定义 28 设 $G=<V_1, V_2, E>$ 为二部图, 若 $M$ 为 $G$ 中一最大匹配, 且 $|M|=\min \left\{\left|V_1\right|,\left|V_2\right|\right\}$, 则称 $M$ 为 $G$ 中一完备匹配。若 $\left|V_1\right| \leq\left|V_2\right|$, 则称 $\mathrm{M}$ 为 $V_1$ 到 $V_2$ 的完备匹配或 $V_1$ 对 $V_2$ 的完备匹配。若 $\left|V_1\right|=\left|V_2\right|$, 则 $G$ 中的完备匹配就是完美匹配。

并不是所有二部图都有完备匹配, 判定一个二部图是否存在完备匹配自然是一个重要问题。

定理 32 设 $G=<V_1, V_2, E>$ 为二部图, $\left|V_1\right| \leq\left|V_2\right|, G$ 中存在从 $V_1$ 到 $V_2$ 的完备匹配, 当且仅当 $V_1$ 中任意 $\mathrm{k}$ 个结点 $\left(\mathrm{k}=1,2, \cdots,\left|V_1\right|\right)$ 至少与 $V_2$ 中 $k$ 个结点相连接（该条件称为相异性条件)。

用相异性条件判定一个二部图是否存在完备匹配, 常常不很方便, 下面给出一个充分条件, 较便于实际使用。
定理 33 设 $G=<V_1, V_2, E>$ 为二部图, $\left|V_1\right| \leq\left|V_2\right|, G$ 中存在从 $V_1$ 到 $V_2$ 的完备匹配的充分条件是: 存在正整数 $t$, 使 $V_1$ 中每个结点的度 $\geq t, V_2$ 中每个结点的度 $\leq t$ (该条件称为 $t$条件)。

定义 29 设 $M$ 为 $G=<V, E>$ 中一匹配, 边在 $M$ 和 $E-M$ 中交替出现的路径称为 $M$ 的交错路径。起点和终点都是 $M$-非饱和点的交错路径称为 $M$ 的可增广路径。
定理 34 图 $G=<V, E>$ 中匹配 $M$ 是最大匹配, 当且仅当 $G$ 不含 $M$ 的可增广路径。
若 $M$ 不是 $G$ 的最大匹配, 则存在 $M$ 的可增广路径 $e_1 e_2 e_3 \Lambda e_{2 k} e_{2 k+1}$, 其中 $e_2 e_4 \Lambda, e_{2 k} \in M, e_1, e_3, \Lambda, e_{2 k+1} \in E-M$ 。令 $M^{\prime}=\left(M-\left\{e_2, e_4, \Lambda, e_{2 k}\right\}\right) \mathrm{Y}\left\{e_1, e_3, \Lambda, e_{2 k+1}\right\}$,则 $M^{\prime}$ 是比 $M$ 多一条边的匹配。如此重复, 最终可得到 $G$ 的一个最大匹配。

刷题

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

上一篇：平面图

下一篇：图的着色

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