《离散数学课件：3-8 集合的划分和覆盖》由会员分享，可在线阅读，更多相关《离散数学课件：3-8 集合的划分和覆盖（7页珍藏版）》请在金锄头文库上搜索。
1、 八、集合的划分和覆盖八、集合的划分和覆盖 设设X为非空集，为非空集，S=S1, S2, , Sm, Si X， Si (i=1, 2, , m)且且S1S2Sm=X，称，称S是是X的的覆盖覆盖(covering). 若再加若再加SiSj=(ij, i,j=1,2,m)，则称则称S是是X的的划分划分(partition), m称为称为S的秩的秩.(一一) 集合的划分和覆盖的定义集合的划分和覆盖的定义(a)集合的覆盖集合的覆盖(b)集合的划分集合的划分例例例例3.8.13.8.1设设X=1,2,3,4,5，则，则C=1,2,3,4,5B=1,2,2,3,4,5A=1,2,3,4U=1,2,3,4
2、,5V=1,2,3,4,5U称为称为X的的最小划分最小划分，V称为称为X的的最大划分最大划分.划分划分划分划分划分划分非覆盖非覆盖覆盖覆盖集合的划分和覆盖的定义集合的划分和覆盖的定义八、集合的划分和覆盖八、集合的划分和覆盖(二二) 交叉划分交叉划分 若若A1, A2, , Ar与与B1, B2, , Bs是同一集是同一集合合X的两种划分，则其中所有的两种划分，则其中所有AiBj组成的集合，组成的集合，称为是原来两种划分的称为是原来两种划分的交叉划分交叉划分.例例例例3.8.23.8.2 给定一个玩具积木的集合给定一个玩具积木的集合按颜色得划分：按颜色得划分： 按形状得划分：按形状得划分： 同时
3、考虑颜色和形状，得交叉划分：同时考虑颜色和形状，得交叉划分： , x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7X= , x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7 , , , 八、集合的划分和覆盖八、集合的划分和覆盖交叉划分交叉划分 设设A1, A2, , Ar与与B1, B2, , Bs是同一集是同一集合合X的两种划分，则其交叉划分亦是原集合的一种划的两种划分，则其交叉划分亦是原集合的一种划分分.证：证：设设A1, A2, , Ar与与B1, B2, , Bs的交叉划的交叉划分为分为 T=AiBj |1 i r, 1 j s.(1)=X.八、集合的划
4、分和覆盖八、集合的划分和覆盖交叉划分交叉划分 设设A1, A2, , Ar与与B1, B2, , Bs是同一集是同一集合合X的两种划分，则其交叉划分亦是原集合的一种划的两种划分，则其交叉划分亦是原集合的一种划分分.证：证：(2)任取任取AiBj , AhBk T ，所以，所以，T是是X的一个划分的一个划分.(AiBj) (AhBk)=, i h i=h, j k , 八、集合的划分和覆盖八、集合的划分和覆盖(三三) 划分的加细划分的加细 设设A1, A2, , Ar与与B1, B2, , Bs是同一集是同一集合合X的两种划分，若对于每个的两种划分，若对于每个Aj均有均有Bk，使，使Aj Bk
5、,则则A1, A2, , Ar称为是称为是B1, B2, , Bs的的加细加细. 性质：性质：任何两种划分的交叉划分都是原划分的一任何两种划分的交叉划分都是原划分的一种加细种加细.证：证： 设设A1, A2, , Ar与与B1, B2, , Bs的交叉划的交叉划分为分为 T=AiBj |1 i r, 1 j s.则对则对T中任意元素中任意元素AiBj ，均有均有AiBj Ai , AiBj Bj ,故故T是原划分的加细是原划分的加细.八、集合的划分和覆盖八、集合的划分和覆盖例例例例3.8.23.8.2 给定一个玩具积木的集合给定一个玩具积木的集合按颜色得划分：按颜色得划分： 按形状得划分：按形状得划分： 同时考虑颜色和形状，得交叉划分：同时考虑颜色和形状，得交叉划分： , x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7X= , x2x1x6x5x3x8x4x7x2x1x6x5x3x8x4x7 , , , 划分的加细划分的加细从这个例子可以看到：从这个例子可以看到：&交叉划分也是原集合的一种划分；交叉划分也是原集合的一种划分；&交叉划分是原来各划分的加细交叉划分是原来各划分的加细. HW: 3-9习题习题 (1);(5)八、集合的划分和覆盖八、集合的划分和覆盖
