欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    离散数学课件第四章(第4讲).ppt

    • 资源ID:71813738       资源大小:658KB        全文页数:25页
    • 资源格式: PPT        下载积分:9金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要9金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    离散数学课件第四章(第4讲).ppt

    5 覆盖与划分覆盖与划分定义定义:给定一非空集合,又设:给定一非空集合,又设 若若(1)(2)则称则称A为为S的覆盖。的覆盖。例:例:S=a,b,c,A=a,b,b,c,B=a,a,b,c,C=a,b,c,D=a,b,a,c 集合集合A,B,C,D都为都为S的覆盖。的覆盖。定义定义:给定一非空集合:给定一非空集合S,设非空集合,设非空集合 如果有:如果有:(i,j=1,2,m)则称集合则称集合A是集合是集合S的一个划分。的一个划分。例:例:S=a,b,c,A=a,b,c,B=a,c,b,C=a,b,c,D=a,b,c 集合集合A,B,C,D都为都为S的划分。的划分。讨论定义:讨论定义:(2)划分)划分A中的元素,称为划分的类,在定义中中的元素,称为划分的类,在定义中 都是都是A中的一个类,类的个数称为划分的秩;中的一个类,类的个数称为划分的秩;(1)集合的划分一定是一个覆盖,而覆盖不一定是划分;)集合的划分一定是一个覆盖,而覆盖不一定是划分;(3)集合)集合S上的秩最大的划分称最大划分,最小的称最小划分。上的秩最大的划分称最大划分,最小的称最小划分。例:设例:设S=a,b,c,下列,下列 均为均为S的一个划分:的一个划分:类有二个类有二个a,b,c,秩为秩为2;类有二个类有二个a,b,c,秩为秩为2;类有二个类有二个a,c,b,秩为秩为2;秩为秩为3;类有三个类有三个a,b,c,秩为秩为1。类有一个类有一个a,b,c,所以所以A4 是最大划分,是最大划分,A5 是最小划分是最小划分定义定义:设:设A和和A是非空集合是非空集合S的二种划分,并可表示成:的二种划分,并可表示成:若若A的每一个类的每一个类 都是都是A的某一个类的某一个类 的子集,则称划分的子集,则称划分A是划分是划分A的加细,的加细,或讲或讲A加细了加细了A,若,若A加细了加细了A且且 则称则称A是是A的真加细。的真加细。例:例:S=a,b,c,d,S的划分:的划分:A=a,b,c,d,A=abc,d,则,则A是是A的真加细的真加细 A=abcd,则则A 是是A的真加细的真加细 定义定义:设:设X是一个集合,是一个集合,R是是X中的二元关系,若中的二元关系,若R是是自反自反的,的,对称对称的和的和可传递可传递的,则称的,则称R是等价关系。是等价关系。例:实数集合上的例:实数集合上的“=”关系(相等)为等价关系关系(相等)为等价关系6 等价关系等价关系试验证试验证R是等价关系,是等价关系,画出画出R的关系图,列出的关系图,列出R的关系矩阵的关系矩阵 解:解:(1)R=(2)R的关系矩阵和关系图的关系矩阵和关系图 R满足自反、对称和传递性质,满足自反、对称和传递性质,R是等价关系是等价关系例:设例:设A=1,2,3,4,R是是A集合上的二元关系集合上的二元关系为整数为整数定义定义:设:设 若若为整数,为整数,则称则称x模模m等于等于y,记作:,记作:R=|,则,则R是一个等价关系。是一个等价关系。定理定理:任何集合:任何集合,R是集合是集合A中的关系,中的关系,例:设例:设A=0,1,2,3,6,R=x,y|xy(x,y A)yx(mod 3),计算计算domR和和ranR。定义定义:设:设R是是A集合中的等价关系,对于任何的集合中的等价关系,对于任何的 来讲,可把集合来讲,可把集合 规定成:规定成:并称是由并称是由 生成的生成的R等价类。等价类。例:设例:设A=a,b,c,d,R是是A中的等价关系,中的等价关系,R=(1)(2)(3)若)若,则,则(4)对于所有的)对于所有的,或者,或者 或者或者(5)定理定理:设:设A是一个非空集合,是一个非空集合,R是是A中的等价关系,则中的等价关系,则例:设例:设X=N,关系,关系R=是一等价关系,是一等价关系,则则R可以找出三个等价类:可以找出三个等价类:=0,3,6,9=1,4,7,10=2,5,8,11定理定理:设:设A是一非空集合,是一非空集合,R是是A中的等价关系,中的等价关系,R等价类的集合等价类的集合xR|x A是是A的一个划分,且此集合的一个划分,且此集合称为称为A关于关于R的商集,用的商集,用 表示之。例:设例:设A=x1,x2.xn(1)A集合中的全域关系集合中的全域关系:是一个等价关系,是一个等价关系,X关于关于R1的商集的商集它形成了它形成了A的一个最小划分的一个最小划分(2)A中的恒等关系中的恒等关系 它形成了它形成了A的一个最大划分的一个最大划分 定理定理:X是一非空集合,是一非空集合,A为为X的一个划分,且的一个划分,且A=A1,A2,.An,则由,则由A导出的导出的X中的一个等价关系中的一个等价关系 例:例:Xa,b,c,d,A=a,b,c,d则则 R(a,b a,b)(c,d c,d)=,因此:集合因此:集合X上的等价关系与上的等价关系与X的划分之间有一一对应关系。的划分之间有一一对应关系。定义定义:设:设X是一个集合,是一个集合,R是是X中的二元关系,若中的二元关系,若R是是自反的,对称的自反的,对称的,则称,则称R是是相容关系相容关系。由定义知由定义知,等价关系是具有等价关系是具有传递性传递性的相容关系的相容关系;相容关相容关 系是一个比等价关系更为普遍的关系。系是一个比等价关系更为普遍的关系。7 相容关系相容关系因为相容关系是自反和对称的因为相容关系是自反和对称的,其关系矩阵是对称的且其关系矩阵是对称的且主对角线元素全为主对角线元素全为1,因此我们可仅用下三角矩阵因此我们可仅用下三角矩阵T来表来表示和存储就够了示和存储就够了,即关系矩阵可以简化为即关系矩阵可以简化为“阶梯形阶梯形”。EX:设:设A=cat,teacher,cold,desk,knife,byR=x,y|x,y A 且且 x和和y至少有一个相同的字母至少有一个相同的字母R 是是 A上的一个相容关系上的一个相容关系,简记简记 A 中元素依次为中元素依次为x1,x2,x3,x4,x5,x6,则则R的关系矩阵的关系矩阵MR和对应简化的下三角矩阵和对应简化的下三角矩阵TR为:为:catteacher cold desk knife bycat teacher cold desk knife byEX:在相容关系的关系图上,每个顶点都有:在相容关系的关系图上,每个顶点都有自回路自回路且每两个顶点且每两个顶点间的弧线都是间的弧线都是成对出现成对出现的。为简化相容关系的关系图的。为简化相容关系的关系图,不画自回路不画自回路,并用无箭头的单线段代替来回弧线并用无箭头的单线段代替来回弧线,使之成为无向图。上例的关系使之成为无向图。上例的关系图如下图如下:x1x2x3x4x5x6定义定义1:设:设R是集合是集合A上的相容关系上的相容关系,若若C A,若任意若任意a,b C,有有aRb,则称则称C是由是由R产生的相容类。产生的相容类。例如上例的相容关系例如上例的相容关系R可产生相容类可产生相容类x1,x2,x1,x3,x2,x3,x6,x2,x4,x5,等等。,等等。对于前三个相容类,都能加进新的元素组成新的相容类,而对于前三个相容类,都能加进新的元素组成新的相容类,而后两个相容类,加入任一新元素,就不能组成相容类,我们后两个相容类,加入任一新元素,就不能组成相容类,我们称它为最大相容类。称它为最大相容类。x3x2x1求最大相容类的方法:求最大相容类的方法:关系图法:画出简化相容关系的关系图后,先确定结点最多的完关系图法:画出简化相容关系的关系图后,先确定结点最多的完全多边形,以后逐次减少。全多边形,以后逐次减少。最大完全多边形最大完全多边形:每个顶点都与其他所有顶点相联结的多边形。每个顶点都与其他所有顶点相联结的多边形。(1)一个结点的最大的完全多边形;一个结点的最大的完全多边形;(2)二个结点的最大完全多边形;二个结点的最大完全多边形;(3)三个结点的最大完全多边形;三个结点的最大完全多边形;(4)四个结点的最大完全多边形;四个结点的最大完全多边形;(5)五个结点的最大完全多边形五个结点的最大完全多边形;最大完全多边形最大完全多边形例:已知相容关系图,求出最大相容类例:已知相容关系图,求出最大相容类最大相容类集合为:最大相容类集合为:完全覆盖:设有完全覆盖:设有 集合集合 A 上的相容关系上的相容关系 R,其中最大相容,其中最大相容类的集合,称作集合类的集合,称作集合 A 的完全覆盖。的完全覆盖。定理:定理:A 上的每个相容关系,唯一的定义一个完全覆盖。上的每个相容关系,唯一的定义一个完全覆盖。最大相容类:最大相容类:b,g,f,e,b,a,e,b,c,d该集合的完全覆盖为:该集合的完全覆盖为:b,g,f,e,b,a,e,b,c,d gabcdef

    注意事项

    本文(离散数学课件第四章(第4讲).ppt)为本站会员(知****量)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开