相容关系-集合与关系-离散数学

相容关系第1页相容关系是另一种常见关系，如朋友关系、同学关系等。这些关系的共性是自反的、对称的。本节要点：相容关系定义、性质相容类概念，画图完全覆盖的计算第2页等价关系有向图等价类商集划分相容类最大相容类完全覆盖简化图二元关系性质自反对称传递反对称反自反相容关系第3页一、定义3-11.1给定集合A上的关系r，若r是自反的、对称的，则r是A上相容关系。例3-11.1：A是由一些英文单词构成的集合。A={fly,any,able,key,book,pump,fit},A上关系R:R={α,β|α∈A,β∈A，且α与β含有相同字母}（1）证明R是相容关系；（2）画出R的关系图；（3）写出R的关系矩阵.证明：(1)对A中任意单词x，必然与自身有相同字母，故x,x∈R，即R自反；设x,y∈R，即x与y有相同的字母，则y与x必有相同的字母，故y,x∈R，即R对称。所以R是相容关系。第4页（2）R的有向图：每个结点自回路，两个节点间有边则双向。自反、对称anyableflykeypumpfitybklyfybookMR=1111001111100011111001111100001110000000101000001（3）R的关系矩阵：R主对角线全1，关于主对角线对称。第5页二、简化图和简化矩阵图的简化:⑴不画环；⑵两条对称边用一条无向边代替。令x1=fly,x2=any,x3=able,x4=key,x5=book,x6=pump,x7=fit,X={x1,x2,x3,x4,x5,x6,x7},r的简化图为：x2x1x3x4x5x6x7每个节点都有自回路有向边成对出现anyableflykeypumpfitybklyfybook第6页二、简化图和简化矩阵(续）矩阵的简化：用下三角矩阵(不含主对角线)代替R的矩阵。主对角线全为1矩阵关于主对角线对称MR=1111001111100011111001111100001110000000101000001MR=111111001100000100000第7页三、相容类及最大相容类在等价关系中讨论了等价类，这里要讨论相容类。定义3-11.2设r是集合A上的相容关系，CA，若对于C中任意两个元素x,y有x,y∈r，称C是r的一个相容类。例3-11.1中{x1,x2},{x3,x4},{x1,x2,x3},{x2,x3,x4},{x1,x2,x4},{x1,x3,x4},{x3,x4,x5},{x1,x2,x3,x4},{x1,x7},{x6}{x2,x3,x5}上述相容类中，有些相容类间有真包含关系。x2。x1。。x3x4。x5。x6。x7。能添加元素不能添加元素都是相容类。不是相容类第8页定义3-11.3设r是集合A上的相容关系，C是r的一个相容类，若C不能真包含于任何其它相容类中，则称C是一个最大相容类，记作：Cr。也可以说，C是一个相容类，若C中加入任意一个新元素，就不再是相容类，C就是一个最大相容类。x2。x1。。x3x4。x5。x6。x7。{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}都是最大相容类。第9页(1)一个孤立结点构成最大相容类；(2)最大完全多边形的顶点集合构成最大相容类：含有结点最多的多边形中，每个结点都与其它结点相联结。三角形------完全3边形；完全4边形，…如下图所示：(3)不是完全多边形边的两个顶点集合构成最大相容类。即两个结点间有连线(非三角形中的一边)---完全1边形；。。。x1。。。。。。。从简化图找最大相容类：第10页在相容关系简化图中，每个最大完全多边形的结点集合构成一个最大相容类。图中所有的最大相容类：{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}分别对应最大完全四、三、一、零边形。x2。x1。。x3x4。x5。x6。x7。第11页给定X上相容关系r’，如图所示,r’所有的最大相容类：{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5},x2x3x1x4x5练习：第12页定义3-11.5r是A中的相容关系，由r的所有最大相容类为元素构成的集合，称之为X的完全覆盖。记作Cr(A)。Cr(A)={{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}}Cr’(A)={{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5}}注意：给定集合A的覆盖不是唯一的，但完全覆盖是唯一的。定理给定集合A的覆盖{A1，A2，…，An}，由它确定的关系R=A1×A1∪A2×A2∪…∪An×An是相容关系。四、完全覆盖x2。x1。。x3x4。x5。x6。x7。x2。x3。x1。x4。x5。第13页不同的覆盖可能构造出相同的相容关系。例设A={1，2，3，4}，集合{{1，2，3}，{3，4}}和{{1，2}，{2，3}，{1，3}，{3，4}}都是A的覆盖，定理：集合A上相容关系r与完全覆盖Cr(A)存在一一对应。R1={1,2,3}×{1,2,3}∪{3,4}×{3,4}={1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3,3,4,4,3,4,4}R2={1,2}×{1,2}∪{2,3}×{2,3}∪{1,3}×{1,3}∪{3,4}×{3,4}={1,1,1,2,2,1,2,2,2,3,3,2,3,3,1,3,3,1,3,4,4,3,4,4}R1=R2,不同覆盖产生相同的相容关系第14页本节要求：相容关系、相容类概念，画图，求完全覆盖。作业第139页(2)第15页