离散数学二元关系.pptVIP

相容关系**1定义:给定集合X上的关系r,若r是自反的、对称的,则r是A上相容关系。2例子：X是由一些英文单词构成的集合。3X={fly,any,able,key,book,pump,fit},X上关系r:r={α,β|α∈X,β∈X且α与β含有相同字母}pump。**any。。ablefly。key。。bookfit。yaebklyfyr的有向图：看出有自反、对称性。而不传递。相容关系的简化图和简化矩阵图的简化：⑴不画环；⑵两条对称边用一条无向直线代替。矩阵的简化：因为r的矩阵是对称阵且主对角线全是1，用下三角矩阵(不含主对角线)代替r的矩阵。令x1=fly,x2=any,x3=able,x4=key,x5=book,x6=pump,x7=fit,X={x1,x2,x3,x4,x5,x6,x7},r的简化图为：x2x1x3x5x4x7x6x21x6x1x2x3x4x5x7x6x5x4x311111111000000000000相容类及最大相容类上例中{x1,x2},{x3,x4},{x1,x2,x3},{x2,x3,x4},{x1,x2,x4},{x3,x4,x5},{x1,x3,x4},{x1,x2,x3,x4},{x1,x7},{x6}都是相容类。上述相容类中，有些相容类间有真包含关系。定义：设r是集合X上的相容关系,C?X,如果对于C中任意元素x,y有x,y∈r,称C是r的一个相容类。定义：设r是集合X上的相容关系，C是r的一个相容类，如果C不能被其它相容类所真包含，则称C是一个最大相容类。也可以说，C是一个相容类，如果C中加入任意一个新元素，就不再是相容类，C就是一个最大相容类。{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}都是最大相容类。logo从简化图找最大相容类：----找最大完全多边形。即：含有结点最多的多边形中，每个结点都与其它结点相联结。在相容关系简化图中，每个最大完全多边形的结点集合构成一个最大相容类。上例中最大相容类{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}分别对应最大完全四、三、一、零边形。给定X上相容关系r,如图所示,r的最大相容类：{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5},完全覆盖：定义：r是X中的相容关系，由r的所有最大相容类为元素构成的集合，称之为X的完全覆盖。记作Cr(X)。Cr(X)={{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}}Cr’(X)={{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5}}作业P139(2)x1x2x3x4x54-10次序关系**一.偏序(半序)关系(partialorderrelation)［定义］：R是A上自反、反对称和传递的关系，则称R是A上的偏序关系。并称A,R是偏序集。例如数值的≤、≥关系和集合的?都是偏序关系。用符号“≤”表示任意偏序关系，但要注意“≤”不一定是“小于或等于”的含义。例1A={1,2,4,6},≤是A中的整除关系，其关系图如右图，显然≤是自反、反对称和传递的，即它是个偏序。2。。1。。64从此图中删去回路中k-j(k-j≥1)条边后得x,y∈Ri-(k-j)，i-(k-j)i,与i是最小的矛盾。所以i≤n,所以x,y∈R,于是R?R。最后得R=R，所以t(R)=R∪R2∪...∪Rn定理证毕。。。。。。。。。xe1ej-1ej=ekej+1。。。。……….。ej+2ek-1ek-2ek+1ek+2…...…...ei-1y求t(R)的矩阵Warshall算法：|X|=n,R?X×X,令MR=AR2的矩阵为A2，…Rk的矩阵为Ak.于是t(R)的矩阵记作MR+=A+A2+…+Ak+…(+是逻辑加)⑴置新矩阵A:=MR;⑵置i=1;⑶对所有j,如果A[j,i]=1,则对k=1,2,…,nA[j,k]:=A[j,k]+A[i,k];/*第j行+第i行,送回第j行*