文档介绍：第六章序关系和结构OrderRelationsandStructures§´BArelationonAisasubsetofA´A矩阵表示,图表示。性质自反reflextiveDÍR对称symmetric,asymmetric,antisymmetricR-1=R,R-1ÇRÍD,R-1ÇR=Æ传递transiveR2ÍRorR¥=R传递闭包Wallshall算法O(n3)等价关系=偏序关系PartialOrder£"aÎA,(a,a)Î"a,bÎA(a,b)∈R∧(b,a)∈RÞa="a,b,cÎA(a,b)∈R∧(b,c)∈RÞ(a,c)∈<N,£>,<Q,£>,<N,|>,<D12,|>,<P(A),Í>,S都是A上等价关系,RÍSÛxRy→xSy,R:A上全体等价关系,(R,Í)构成偏序。对偶偏序集:如果R是A上偏序,则R-1也是A上偏序。(A,R-1)称为(A,R)的对偶偏序集。(A,≥)是(A,≤)的对偶偏序。全序关系,线性序关系linearorder,.+44."a,bÎA,(a,b)ÎR∨(b,a)∈(A,≤),(B,≤)是偏序,则(A×B,≤)是乘积偏序productpartialorder,其中≤定义为:(a,b)≤(a’,b’)Ûa≤a’Ùb≤b’偏序与严格序设(A,≤)是偏序,令a<bÛa≤b,a≠b,称(A,<)严格序,大于,小于都是严格线性序。反之若(A,<)是严格序,令a≤bÛa<bÚa=b,则(A,≤)是偏序。字典序二元(A×B,≤)中,令(a,b)<(a’,b’)Ûa<a’ora=a’,b<b’<元(A,≤)是偏序,An=A×A×……×A(a1,a2,……,an)<(b1,b2,……,bn)Ûa1<b1∨a1=b1∧a2<b2∨……∨a1=b1∧……∧an<bn不等长(a1,a2,……,an)<(b1,b2,……,bm)Ifn=mIfn<m(a1,a2,……,an)£(b1,b2,……,bn)Ifn>m(a1,a2,……,am)<(b1,b2,……,bm)。423哈斯图HasseDiagram1paritalorder,digraphandthematrixofD6?从关系图到哈斯图Deletingalltheself-?={a,b,c},A=P(S).问题()给定偏序关系R,哈斯图是否唯一?计算哈斯图的算法?传递闭包逆运算?拓扑排序(A,≤)是偏序集,构造一个线性序(A,≤’)使a<bÞa<’b,算法原理:,。?O(n3)同构Isomorphic定义f:(A,≤)→(A’,≤’)f是A→A’的一一对应,a≤bifff(a)≤’f(b)。例15.(Z,≤)→(2Z,≤)f:(Z,≤)→(2Z,≤)是同构。f(a)=2aa≤biff2a≤:(A,≤)@(A’,≤’)。则A,A’对应的性质都相同。序同构与哈斯图的关系如果f是同构,则A的哈斯图中所有标记a换成对应的标记f(a),得到A’的哈斯图。如果A的哈斯图中所有标记a换成对应的标记f(a),得到A’的哈斯图,则f是同构。={1,2,3,6},A’=P({a,b})={Æ,{a},{b},{a,b}}HomeworkP200-2015,6,14,16,24,28,35,36§:a∈A,Ø$b∈A,a<:a∈A,Ø$b∈A,b<,至少有一个极大元,至少有一个极小元。最大元greatestelement:a∈A,任意b∈A,b£:a∈A,任意b∈A,a£,至多有一个最大元,至多有一个最小