离散数学课件 第六章 序关系及结构.doc

第六章序关系和结构Order Relations and Structures §6.1 偏序集Partial Ordered Sets 关系 Relation 定义 A Relation R From A to B is a subset of A(B A relation on A is a subset of A(A 矩阵表示，图表示。 性质 自反 reflextive ((R 对称 symmetric, asymmetric, antisymmetric R-1=R, R-1(R((, R-1(R=( 传递 transive R2(R or R(=R 传递闭包 Wallshall算法O(n3) 等价关系 = 偏序关系Partial OrderDefinition 1. 自反 Reflexive (a(A, (a,a)(R 2．反对称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 R(S(xRy→xSy, R：A上全体等价关系， (R ，()构成偏序。 对偶偏序集： 如果R是A上偏序，则R－1也是A上偏序。（A，R－1）称为（A，R）的对偶偏序集。 （A，≥）是（A，≤）的对偶偏序。 全序关系，线性序关系linear order偏序1.2.3.＋4． (a,b(A,(a,b)(R∨(b,a)∈R. 字典序 ’,b’)(a≤a’(b≤b’ 偏序与严格序 设（A，≤）是偏序， 令ab(a≤b，a≠b， 称（A，）大于，小于都是严格线性序。）(A×B，≤)中，令(a,b)(a’,b’)(aa’or a=a’,bb’ 是字典序lexicographic (a1,a2,……,an)(b1,b2,……,bn) ( a1b1∨a1=b1∧a2b2∨…… ∨a1=b1∧……∧anbn 不等长 (a1,a2,……,an)(b1,b2,……,bm) If n=m If nm (a1,a2,……,an)((b1,b2,……,bn) If nm (a1,a2,……,am)(b1,b2,……,bm) 定理2. 偏序集的有向图中没有长度大于1的圈。哈斯图Hasse Diagram parital order，digraph and matrix of D6？ Deleting all the self-circles Deleting all the edges which can be induced by transive property Replacing vertices by dots Make sure the greater elements are located at higher place. 例11．D12 的哈斯图？ 例12．S＝{a,b,c}, A=P(S). 问题（6.1.1） 给定偏序关系R，哈斯图是否唯一？ 计算哈斯图的算法？ 传递闭包逆运算？ 拓扑排序 （A，≤）是偏序集，构造一个线性序（A，≤’）’b， 算法原理： 1. 选择一个没有前驱的顶点输出， 2. 去掉这个顶点以及从这点出发的所有边。 重复1.2.直到所有顶点都输出完毕 时间复杂性？ O(n3) 同构Isomorphic 定义 f：（A≤）→（A’, ≤’） ’的一一对应， a≤b iff f(a)≤’f(b)。 例15．（Z，≤）→（2Z，≤） f：（Z，≤）→（2Z，≤）是同构。 f(a)=2a a≤b iff 2a≤2b 定理3. 设f：(A,≤) ((A’,≤’)。则A, A’对应的性质都相同。 序同构与哈斯图的关系 如果f是同构，则A的哈斯图中所有标记a换成对应的标记f(a), 得到A’的哈斯图。 如果A的哈斯图中所有标记a换成对应的标记f(a), 得到A’的哈斯图，则f是同构。 例17．A＝{1,2,3,6}, A’=P({a,b})={ (,{a},{b},{a,b}}Extremal elements of Partial Ordered Sets 极大元maximal element： a∈A，((b∈A，ab.偏序集A中，至多有一个最大元，至多有一个最小元。 ’，a(a’. 下确界GLB greatest lower bound 偏序集A中，B(A，a是B的最大下界，即a是B的下界，对B的任意下界a’，aa’. 定理3. 偏序集A中，B(A，B至多一个上确界，至多一个下确界。 定理4. 设f：（A，≤）→（A’,≤’） 是偏序同构， a是A的极大（极小）元，则f(a)是A’的