84独立集,覆盖 1点覆盖和独立集 定义8.15:设无自环图G=(V,E若V的 个子集I中任意两个顶点在G中都不相邻, 则称是G的一个独立集。若G中不含有 满足的独立集',则称I为G的最大 独立集。它的顶点数称为G的独立数,记 为β(G) 对于无自环的图,单点是独立集
8.4独立集, 覆盖 1.点覆盖和独立集 定义 8.15:设无自环图G=(V,E),若V的一 个子集I中任意两个顶点在G中都不相邻, 则称I是G的一个独立集。若G中不含有 满足|I'|>|I|的独立集I', 则称I为G的最大 独立集。它的顶点数称为G的独立数, 记 为0 (G)。 对于无自环的图,单点是独立集
4 2 了3 定义8.16:若Ⅴ的一个子集C使得G的每 条边至少有一个端点在C中,则称C是G的 个点覆盖。若G中不含有满足C<(C的点覆 盖C,则称C是G的最小点覆盖。它的顶点数 称为G的点覆盖数,记为an(G) G中每条边端点在V中,故ⅴ为G的点覆盖
定义 8.16：若V的一个子集C使得G的每一 条边至少有一个端点在C中, 则称C是G的一 个点覆盖。若G中不含有满足|C'|<|C|的点覆 盖C', 则称C是G的最小点覆盖。它的顶点数 称为G的点覆盖数, 记为0 (G)。 G中每条边端点在V中，故V为G的点覆盖
定理8.11:V的子集I是G的独立集当且仅当V是 G的点覆盖。 证明:(1)V的子集I是G的独立集。 由独立集的定义,I中任意两个点不相邻, G中每条边至少有一个端点不在中,即在V中, G中每条边至少有一个端点在V中, V为G的点覆盖。 (2)V是G的点覆盖 G中每条边至少有一个端点在V-I中, 每条边至少有一个端点不在中 I中任意2点不相邻,即是独立集
定理 8.11：V的子集I是G的独立集当且仅当V-I是 G的点覆盖。 证明：(1) V的子集I是G的独立集。 由独立集的定义, I 中任意两个点不相邻， G中每条边至少有一个端点不在I中，即在V-I中， G中每条边至少有一个端点在V-I中， V-I为G的点覆盖。 (2) V-I是G的点覆盖 G中每条边至少有一个端点在V-I中, 每条边至少有一个端点不在I中 I中任意2点不相邻，即I是独立集
推论8.1:对于n个顶点的图G,有 aO(G)+B0(G)=n 证明:设I是G的最大独立集,C是G的最 小点覆盖,则V-C是G的独立集,V是G 的点覆盖
推论 8.1：对于n个顶点的图G, 有 0(G)+0(G)=n。 证明：设I是G的最大独立集, C是G的最 小点覆盖, 则V-C是G的独立集, V-I是G 的点覆盖
v1 v v2 5 v2 v3 v3 边覆盖与完美匹配的力: 1)M,L都要求每个端点关联M,L中的边 2)但M要求边不相交而L无此要求 G有边覆盖的充要条件是8(G)>0。 当G中有孤立点时,图G不存在边覆盖
2.边覆盖和边独立集 定义 8.17：若E的一个子集L使得G的每 一个顶点至少与L中一条边关联, 称L是G 的一个 边覆盖 。 若 G 中不含有满足 |L'|0。 当G中有孤立点时,图G不存在边覆盖
定义:设图G=(V,E),G中的匹配M也称 为G的边独立集,G中的最大匹配也称为 最大边独立集,最大边独立集的边数称 为G的边独立数,记为β(G 点独立集和点覆盖之间存在互补关系, 边独立集和边覆盖之间是否存在这种关 系? 4 V3
定义：设图G=(V,E)，G中的匹配M也称 为G的边独立集，G中的最大匹配也称为 最大边独立集，最大边独立集的边数称 为G的边独立数, 记为1 (G)。 点独立集和点覆盖之间存在互补关系, 边独立集和边覆盖之间是否存在这种关 系?
定理8.12对于n个顶点图G,且8(G)>0, 则a1(G)+B1(G)=n 证明:(1)a1(G)+B1(G)≤n 设M是G的最大匹配,M|=β1(G)。设F是 关于M的未饱和点集合, (2)al(G)+β1(G)≥n 设L是G的最小边覆盖,L|=1(G)。令 H=G(L,H有n个顶点。又设M是H的最 大匹配,显然也是G的匹配,且McL。以 U表示H中关于M的未饱和点集合
定理 8.12:对于n个顶点图G, 且(G)>0, 则1(G)+1(G)=n 证明:(1) 1(G)+1(G)n 设M是G的最大匹配, |M|=1(G)。设F是 关于M的未饱和点集合, (2) 1(G)+1(G)n 设L是G的最小边覆盖, |L|=1(G)。令 H=G(L), H有n个顶点。又设M是H的最 大匹配, 显然也是G的匹配,且 ML。以 U表示H中关于M的未饱和点集合
3科尼格(K6nig)定理 交叉关系,点覆盖与匹配的关系。 对于任一个点覆盖C和任一个匹配M, C中至少包含G中任一边的一个端点,而 匹配M是G的边集的子集,所以C中至少 包含M中任一边的一个端点,又因为M 是匹配,它们的边互不相交,即每条边 的端点无公共点,所以M≤Cl 因此:β1(G)≤0(G) 等式是否成立?
3.科尼格(König)定理 交叉关系，点覆盖与匹配的关系。 对于任一个点覆盖C和任一个匹配M， C中至少包含G中任一边的一个端点，而 匹配M是G的边集的子集，所以C中至少 包含M中任一边的一个端点，又因为M 是匹配，它们的边互不相交，即每条边 的端点无公共点，所以|M||C|。 因此：1(G)0(G)。 等式是否成立？
科尼格在1931年给出了结论:对于二分 图等式成立。 引理8.1:设M是一个匹配,C是一个点 覆盖,且M=C|,则M是最大匹配,C 是最小点覆盖。 证明:若M是最大匹配,C是最小点覆 盖, 则β1(G)=M*,a0(G)=C
科尼格在 1931 年给出了结论：对于二分 图等式成立。 引理 8.1：设M是一个匹配，C是一个点 覆盖，且|M|=|C|，则M是最大匹配，C 是最小点覆盖。 证明：若M*是最大匹配，C'是最小点覆 盖， 则1(G)=|M*|，0(G)=|C'|
A Vi-A V,V2) 中关于 M交 T=T(A) v2-T 匹配, 图8.18 由定理8.8可知U是Z中仅有的未被M饱和 的顶点集合,如图818所示
定理 8.13(科尼格定理)：在二分图G(V1,V2) 中, 有1(G)=0(G)。 证明：设M*是G的最大匹配, U是V1中关于 M*未饱和点集合。 又设Z表示与U中每一个顶点有关于M*交 错路相连的顶点集合, 因为M*是最大匹配， 所以G中不包含关于M*的增广路， 由定理8.8可知U是Z中仅有的未被M*饱和 的顶点集合, 如图 8.18 所示