文档介绍：第六章序关系和结构 Order Relations and Structures § 偏序集 Partial Ordered Sets 关系 Relation 定义 A Relation R From A toB isa subset ofA?B A relation onA isa subset ofA?A 矩阵表示,图表示。性质自反 reflextive R 对称 symmetric, asymmetric, antisymmetric R -1 =R, R -1R,R -1 R= 传递 transive R 2R orR =R 传递闭包 Wallshall 算法 O(n 3) 等价关系= 偏序关系 Partial Order Definition 1. 自反 Reflexive ?a? A, (a,a) ?R2 .反对称 antisymmetric ? a,b ?A (a,b) ∈R∧(b,a) ∈R? a=b 3 .传递 Transitive ? a,b,c ?A (a,b) ∈R∧(b,c) ∈R?(a,c) ∈R. Examples <N, >, <Q, >, <N, |>, <D 12 ,|>, <P(A), > ,S 都是 A 上等价关系, R?S? xRy → xSy ,R:A 上全体等价关系, (R,) 构成偏序。对偶偏序集: 如果 R是A 上偏序,则 R -1 也是 A 上偏序。(A,R -1) 称为(A,R) 的对偶偏序集。(A, ≥)是( A,≤)的对偶偏序。全序关系,线性序关系 linear order ,链 chain 偏序 . +44.? a,b ? A,(a,b) ?R∨(b,a) ∈ R. 字典序偏序乘积定理 1 如果(A, ≤), (B, ≤) 是偏序,则(A× B,≤) 是乘积偏序 product partial order , 其中≤定义为: (a,b) ≤(a’,b’)a ≤a’?b≤b’偏序与严格序设( A,≤)是偏序, 令a<ba ≤b,a≠b, 称( A,< ) 严格序, 大于,小于都是严格线性序。反之若(A,< ) 是严格序,令a≤b a<b a=b, 则(A, ≤) 是偏序。字典序二元(A ×B,≤) 中, 令(a,b)<(a ’,b’)? a<a ’ or a=a ’,b<b ’< 是字典序 lexicographic n元(A,≤)是偏序, A n=A×A ×……× A (a 1 ,a 2, ……,a n )<(b 1 ,b 2, ……,b n)?a 1 <b 1∨a 1=b 1∧a 2 <b 2 ∨……∨a 1=b 1 ∧……∧ a n <b n 不等长(a 1 ,a 2, ……,a n )<(b 1 ,b 2, ……,b m) If n=m If n<m (a 1 ,a 2, ……,a n)?(b 1 ,b 2, ……,b n) If n>m (a 1 ,a 2, ……,a m )<(b 1 ,b 2, ……,b m) 定理 2. 偏序集的有向图中没有长度大于 1 的圈。哈斯图 Hasse Diagram parital order , digraph and the matrix ofD 6? 从关系图到哈斯图 D eleting all the self-circles D eleting all the edges which can be induced by transive property R eplacing vertices by dots Make sure the greater elements are located at higher place. 2 431 12 例 12 的哈斯图? 例 = {a,b,c}, A=P(S). 问题( ) 给定偏序关系 R ,哈斯图是否唯一? 计算哈斯图的算法? 传递闭包逆运算? 拓扑排序(A,≤) 是偏序集, 构造一个线性序(A, ≤’)使 a<b a<’b, 算法原理: 1. 选择一个没有前驱的顶点输出, 2. 去掉这个顶点以及从这点出发的所有边。重复 . 直到所有顶点都输出完毕时间复杂性? O(n 3) 同构 Isomorphic 定义 0 f :(A,≤)→(A’, ≤’) f 是A →A’的一一对应, a ≤b iff f(a) ≤’ f(b) 。例 15.(Z,≤)→( 2Z ,≤)f:(Z,≤)→( 2Z ,≤)是同构。 f(a)=2a a≤b iff 2a≤ 2b 定理 : (A, ≤) (A’,≤’)。则 A, A’对应的性质都相同。序同构与哈斯图的关系 1 . 如果 f 是同构,则A 的哈斯图中所有标记a 换成对应