8.4独立集, 覆盖 1.点覆盖和独立集 定义 8.15:设无自环图G=(V,E),若V的一个子集I中任意两个顶点在G中都不相邻, 则称I是G的一个独立集。若G中不含有满足|I'|>|I|的独立集I', 则称I为G的最大独立集。它的顶点数称为G的独立数, 记为0(G)。 对于无自环的图,单点是独立集。

Presentation on theme: "8.4独立集, 覆盖 1.点覆盖和独立集 定义 8.15:设无自环图G=(V,E),若V的一个子集I中任意两个顶点在G中都不相邻, 则称I是G的一个独立集。若G中不含有满足|I'|>|I|的独立集I', 则称I为G的最大独立集。它的顶点数称为G的独立数, 记为0(G)。 对于无自环的图,单点是独立集。"— Presentation transcript:

1 8.4独立集, 覆盖 1.点覆盖和独立集 定义 8.15:设无自环图G=(V,E),若V的一个子集I中任意两个顶点在G中都不相邻, 则称I是G的一个独立集。若G中不含有满足|I'|>|I|的独立集I', 则称I为G的最大独立集。它的顶点数称为G的独立数, 记为0(G)。 对于无自环的图,单点是独立集。

2 定义 8.16：若V的一个子集C使得G的每一条边至少有一个端点在C中, 则称C是G的一个点覆盖。若G中不含有满足|C'|<|C|的点覆盖C', 则称C是G的最小点覆盖。它的顶点数称为G的点覆盖数, 记为0(G)。 G中每条边端点在V中，故V为G的点覆盖。

3 定理 8.11：V的子集I是G的独立集当且仅当V-I是G的点覆盖。
G中每条边至少有一个端点不在I中，即在V-I中， G中每条边至少有一个端点在V-I中， V-I为G的点覆盖。 (2) V-I是G的点覆盖 G中每条边至少有一个端点在V-I中, 每条边至少有一个端点不在I中 I中任意2点不相邻，即I是独立集。

4 推论 8.1：对于n个顶点的图G, 有0(G)+0(G)=n。
证明：设I是G的最大独立集, C是G的最小点覆盖, 则V-C是G的独立集, V-I是G的点覆盖

5 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不存在边覆盖.

6 定义：设图G=(V,E)，G中的匹配M也称为G的边独立集，G中的最大匹配也称为最大边独立集，最大边独立集的边数称为G的边独立数, 记为1(G)。
点独立集和点覆盖之间存在互补关系, 边独立集和边覆盖之间是否存在这种关系?

7 定理 8.12:对于n个顶点图G, 且(G)>0, 则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的匹配,且 ML。以U表示H中关于M的未饱和点集合

8 3.科尼格(König)定理 交叉关系，点覆盖与匹配的关系。 对于任一个点覆盖C和任一个匹配M， C中至少包含G中任一边的一个端点，而匹配M是G的边集的子集，所以C中至少包含M中任一边的一个端点，又因为M是匹配，它们的边互不相交，即每条边的端点无公共点，所以|M||C|。 因此：1(G)0(G)。 等式是否成立？

9 科尼格在 1931 年给出了结论：对于二分图等式成立。
引理 8.1：设M是一个匹配，C是一个点覆盖，且|M|=|C|，则M是最大匹配，C是最小点覆盖。 证明：若M*是最大匹配，C'是最小点覆盖， 则1(G)=|M*|，0(G)=|C'|。

10 定理 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 所示。

11 推论8.2：在(G)>0的二分图G=G(V1,V2)中，有0(G)=1(G)。
证明：利用定理 8.11 的推论 8.1 以及定理 8.12得，1(G) +1(G)=0(G)+0(G)。 再由定理 8.13 即得0(G)=1(G)。

12 作业:P ,22