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'|<|L|的边覆盖L'，则称L是G的最小边 覆盖。它的边数称为G的边覆盖数，记 为1 (G)。 边覆盖与完美匹配的区别: 1)M,L都要求每个端点关联M,L中的边 2)但M要求边不相交,而L无此要求 G有边覆盖的充要条件是(G)>0。 当G中有孤立点时,图G不存在边覆盖