第工科离散数学课件 四章 4_6_序关系(2) - 哈斯图.pptx

4.6.2 哈斯图4.6 偏序关系-哈斯图——使用“哈斯图”简化偏序关系的关系图。[盖住] 在偏序集<A, ? >中，对?x，y ? A，如果x?y，且A中不存在z满足x?z， z?y 则称y盖住了x。Try it：怎么理解y盖住了x？——“y盖住了x”是指x ? y且二者中间不能插入其他元素。[盖住集] 由所有具有盖住关系的序偶组成的集合： COV(A) = {<x, y> | x，y ? A ∧ y盖住x}321——COV({1, 2, 3}) = {<1, 2>, <2, 3>} 4.6 偏序关系-哈斯图示例：图示为集合A = {1, 2, 3}上偏序关系?= {<1,1>, <2,2>, <3,3>, <1,3>, <1,2>, <3,2>}的关系图。——3盖住1，2盖住3，但2不能盖住1，因为1?3，3?2。例4-29：设A是整数12的正因子集合，求A上整除关系?的盖住集COV(A)。解： A = {1, 2, 3, 4, 6, 12}，有 | = {<1,2>, <1,3>, <1,4>, <1,6>, <1,12>, <2,4>, <2,6>, <2,12>, <3,6>, <3,12>, <4,12>, <6,12>}于是，有 COV(A) = {<1,2>, <1,3>, <2,4>, <2,6>, <3,6>, <4,12>, <6,12>}231 4.6 偏序关系-哈斯图哈斯图的画法：(1) 用小圆圈表示元素；(2) 如果a?b，则元素b置于元素a的上方；(3) 若<x, y> ?COV(A) ，在a和b之间连线。示例：绘制例4-25的整除关系的哈斯图。普通关系图12462311246231哈斯图问：一个偏序关系与其盖住集之间有什么关联 ？答：偏序关系是盖住集的自反和传递闭包。 在根据哈斯图写出偏序关系时，一定要注意自反性和传递性。——隐含了由下至上的连线方向 4.6 偏序关系-哈斯图解：?(A1) = {?, {a}, {b}, A} ?(A2) = {?, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}例4-30：设A1= {a, b}， A2= {a, b, c}，画出?(A1)和?(A2)上集合包含关系?的哈斯图。有： COV(A1) = {<?, {a}>, <?, {b}>, <{a}, A>, <{b}, A} COV(A2) = {<?, {a}>, <?,{b}>, <?, {c}>, <{a}, {a,b}>, <{b}, {a,b}>, <{a}, {a,c}>, <{b}, {b,c}>, <{c}, {a,c}>, <{c}, {b,c}>, <{a,b}, A>, <{a,c}, A>, <{b,c}, A>} A1{a,b}{a}{b}?{a,b,c}{a,c}{b,c}{c}{a,b}{a}{b}?A2 4.6 偏序关系-哈斯图1. 偏序集<{1, 2, 3, 4, 6, 8}, | >中，哪些元素是不可比的？——2与3；3与4；3与8；4与6；6与8——<1, 2>, <1, 3>, <4, 1>2. 观察偏序关系图，哪些元素之间有盖住关系？14233. 偏序集<{1, 2, 3, 4}, ≤>与上图的偏序集的主要区别是？——<{1, 2, 3, 4}, ≤>中任意2个元素都可比