Question

离散数学哈斯图

设偏序集<A,R>的哈斯图如下图所示，B为A的子集，其中B={a,b,c},试（1）写出R的关系表达式；（2）画出关系R的关系图；（3）求出B的最大元素、极小元素、上界。

Answer 1

（1）R={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<a,c>,<b,d>,<c,d>}
（2）跟题目中的哈斯图差不多，节点处画闭环（带箭头），图中线段上端点添加箭头即可。
（3）B的最大元不存在，极小元为a，上界为d

Answer 2

向上的路径的终点是极大值，向下的路径的终点是极小值，若所有的路径汇合到一点，此为最大值，若向下所有的路径汇于一点，此为最小值。上确界（下确界）就是所有的上界（或下界）组成的子图中的最大值（或最小值），做法类似。

例如下面左图，24和36都是极大值，2和3都是极小值，没有最大值也没有最小值。右图，24是最大值，1是最小值