&易 偏序集(poset)与哈斯图 1. 偏序集 定义： 集合A和A上的偏序关系<一起叫做偏序集，记作(A,≤)】 实例： 整数集合Z和数的小于或等于关系≤构成偏序集(Z,≤) 集合A的幂集P(4)和包含关系R构成偏序集(P(4),R)》 2.哈斯图 利用偏序关系的自反、反对称、传递性进行简化的关系图 特点： 。每个结点没有环 两个连通的结点之间的序关系通过结点位置的高低表示，位置 低的元素的顺序在前 具有覆盖关系的两个结点之间连边 偏序集与哈斯图 6
偏序集(poset)与哈斯图 偏序集与哈斯图 6 ： ( ) ( ) ( )
& 偏序集 例：证明(P(A),S)为全序当且仅当|A≤1 证明： (1)“←”： Case1:A=0,P(A)={0},(P(A),)为全序 Case2:A=1,设A={a},P(A={0,{a},(P(A),)为全序 “→”：只需证A≥2时，(P(A),)非全序 A≥2.可取a,b∈A,a≠b {a{b}不可比∴.(P(A),)非全序 偏序集 7
偏序集 偏序集 7 {a} {b}不可比
& 偏序集（续） 例：字典序(lexicographic order)与偏序集 0 给定两个偏序集(A,≤4)与(B,≤B),在A×B 上定义新关系“≤”： (a,b)≤(c,d)台a<cV(a=c∧b≤d) ■ 另证，4×B,)是-个偏序集。A 偏序集 8
偏序集（续） 例：字典序(lexicographic order)与偏序集 给定两个偏序集 𝐴, ≼𝐴 与 (𝐵, ≼𝐵) ，在 𝐴 × 𝐵 上定义新关系“≼”： 𝑎, 𝑏 ≼ 𝑐, 𝑑 ⇔ 𝑎 ≺ 𝑐 ∨ (𝑎 = 𝑐 ∧ 𝑏 ≼ 𝑑) 易证， (𝐴 × 𝐵, ≼) 是一个偏序集。 偏序集 8
&原 偏序集（续） 例：在字典中“part”和“park”两个单词 的顺序如何？ Dictionary Thesaurus 定义全序集（英文字母表）S={a,b,c,…,z: 元素满足线序关系Q≤b,b≤C,…,y≤z,令 S4=S×S×S×S,易见，(p,a,r,t)∈S4, (p,a,T,k)∈S4;根据字典序，park≤part 偏序集 9
偏序集（续） 偏序集 9
&是 哈斯图(Hasse Diagrams) 将偏序关系简化为哈斯图： ·省略所有顶点上的环 ·省略所有因传递关系而引出的边 ·根据箭头的方向自下而上重排 列所有顶点，而后将所有的有 向边替换为无向边
哈斯图（Hasse Diagrams） 将偏序关系简化为哈斯图： • 省略所有顶点上的环 • 省略所有因传递关系而引出的边 • 根据箭头的方向自下而上重排 列所有顶点，而后将所有的有 向边替换为无向边