独立集和覆盖.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.7 独立集和覆盖,监控系统的设计,a,b,c,d,e,f,g,h,I,b,c,d,f,h,i形成了一个控制集,定义5.7.1,设 是图 的一个点子集，若 中的每一条边至少有一个端点在 中，则称 是 的一个,点覆盖,。若 中不存在满 足 的点覆盖 ，则称 是 的一个,最小点覆盖,。的最小点覆盖集的点数称为 的,点覆盖数,，记为,一、点覆盖,一个图的点覆盖数和最大对集的边数 之间的关系：,引,理5.7.1,设 是 的一个对集，是 的一个覆盖，且 ，则 是 的最大对集，是 的一个最小点覆盖。,分析：取出最大对集 和最小点覆盖 进行比较。,点覆盖数大于等于最大对集的边数。,定理5.7.2,对每一个二分图 ，有,证明,：取出最大对集 ，分两种情况讨论：,Case1,饱和 中所以顶点.则由于 构成 的一个点覆盖，并且 ，由引理5.7.1，是G的最小点覆盖，故定理成立。,Case2 不,饱和 中所以顶点，记 是 中所有非饱和点。置,Case1 饱和 中所以顶点.,G中每一条边至少有一个端点属于 或 ,从而,1节二分图与(0,1)矩阵的关系，由 构造一个二分图 ，则 中两两不属于同一条直线上的1的集合对应于 中的对集。,约定,而包含 中全部1的线的集合对应于 的点覆盖。,g,1，是G的最小点覆盖，故定理成立。,a,点覆盖数大于等于最大对集的边数。,f,1，是G的最小点覆盖，故定理成立。,1 设 是 的一个对集，是 的一个覆盖，且 ，则 是 的最大对集，是 的一个最小点覆盖。,3 图 的一个点子集 是 的独立集当且仅当 是 的点覆盖。,b,c,d,f,h,i形成了一个控制集,f,约定,由于 中顶点与B中顶点在 下配对。因此,由定理5.3.1类似证明，知 ,因此,G中每一条边至少有一个端点属于 或 ,从而,构成G的点覆盖。根据U定义：,可见K是G的最小点覆盖，故证毕。,例1,设 是一个 的(0,1)矩阵。的一行或一列称为一条线，试证明：中两两不属于同一线上的1的个数的最大值等于包含 中所有1的线数的最小值。,证明,：利用本章5.1节二分图与(0,1)矩阵的关系，由 构造一个二分图 ，则 中两两不属于同一条直线上的1的集合对应于 中的对集。而包含 中全部1的线的集合对应于 的点覆盖。由定理5.7.2立即得到例中的结论成立。,证明：由独立集和点覆盖的定义分析。,二、独立集,定义5.7.2,设 是 的一个点子集，若 中任意两个顶点不相邻，则称 是 的一个,独立集,，若 中不存在满足 的独立集 ,则称 是 的,最大独立集,。最大独立集的点数称为 的,独立数,，记为,定理5.7.3,图 的一个点子集 是 的独立集当且仅当 是 的点覆盖。,推论5.7.4,若 阶图 没有孤立顶点，则,定义5.7.3,设 是图 的一个边子集，若 的每一个顶点至少与 中的一条边关联，则称 是 的一个,边覆盖,。若 不含有满足 的边覆盖 ,则称 是 的,最小边覆盖,，它的边数称为 的,边覆盖数,，记为,三、边覆盖,(1)有边覆盖的充要条件是,(2)边覆盖与对集之间没有互补性,(3)若 有完美对集 ,则 也是 的完美对集,注:,5 设 是 阶无孤立顶点的图，则,是的关于 的非饱和点集合，则有 。,1 设 是 的一个对集，是 的一个覆盖，且 ，则 是 的最大对集，是 的一个最小点覆盖。,设 是一个 的(0,1)矩阵。,2立即得到例中的结论成立。,3 图 的一个点子集 是 的独立集当且仅当 是 的点覆盖。,是的关于 的非饱和点集合，则有 。,2 对每一个二分图 ，有,1节二分图与(0,1)矩阵的关系，由 构造一个二分图 ，则 中两两不属于同一条直线上的1的集合对应于 中的对集。,定理5.7.5,设 是 阶无孤立顶点的图，则,证明:(1)设 是 的最大对集，。是的关于 的非饱和点集合，则有 。由于无孤立点，对于 的每一个顶点 ，取一条与 关联的一条边，所以这样的边与 一起构成的边子集记为 ，显然 构成 的一个边覆盖。可以推出：,（2）令 是 的最小边覆盖，则 是 的生成子图，又设 是 的最大对集，显然也是 的对集，且 。现以 表示 中关于 的非饱和点的集合，则有 。可以推出：,最后得出结论。,推论5.7.6,对任一个二分图 ，如果 ，则,