文档介绍：Forpersonaluseonlyinstudyandresearch;mercialuse芅第六章序关系和结构OrderRelationsandStructures芄§´B羄ArelationonAisasubsetofA´A蒂矩阵表示,图表示。薇性质莈自反reflextive蚅DÍR芀对称symmetric,asymmetric,antisymmetric罿R-1=R,R-1ÇRÍD,R-1ÇR=Æ螇传递transive蒅R2Í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,.+4罿4."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’<是字典序lexicographic莄n元(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=m袄Ifn<m(a1,a2,……,an)£(b1,b2,……,bn)肂Ifn>m(a1,a2,……,am)<(b1,b2,……,bm)。蚅4膃***2羈3哈斯图HasseDiagram莅羀1paritalorder,digraphandthematrixofD6?薀从关系图到哈斯图蒇Deletingalltheself-?={a,b,c},A=P(S).肁问题()芆给定偏序关系R,哈斯图是否唯一?莂计算哈斯图的算法?袀传递闭包逆运算?腿拓扑排序蚆(A,≤)是偏序集,构造一个线性序(A,≤’)