Hasse图详解 Hasse图|离散数学

本文概述

最小上限（最高）
最大下界（INFIMUM）

这是一个有用的工具, 它完全描述了相关的偏序。因此, 它也称为订购图。将集合A上的有向图转换为等效的Hasse图非常容易。因此, 在绘制Hasse图时, 必须记住以下几点。

Hasse图中的顶点由点而不是圆表示。
由于偏序是自反的, 因此A的每个顶点都必须与其自身相关, 因此从顶点到其自身的边在Hasse图中被删除。
由于偏序是可传递的, 因此无论何时aRb, bRc, 我们都有aRc。消除Hasse图中传递属性所隐含的所有边缘, 即从a到c删除边缘, 但保留其他两个边缘。
如果顶点’ a’ 通过边缘即aRb连接到顶点’ b’ , 则顶点’ b’ 出现在顶点’ a’ 上方。因此, 在Hasse图的边缘可能会省略箭头。

哈斯图比偏序有向图简单得多。
示例：考虑集合A = {4, 5, 6, 7}。令R为A上的关系≤。绘制R的有向图和Hasse图。
解决方案：集合A上的关系≤由下式给出：
【Hasse图详解】R = {{4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}, {4, 4}, {5, 5} , {6, 6}, {7, 7}}
关系R的有向图如图所示：

要绘制偏序的Hasse图, 请应用以下几点：

删除反射性属性（即（4, 4）, （5, 5）, （6, 6）, （7, 7）
删除传递属性隐含的所有边, 即（4, 7）, （5, 7）, （4, 6）
用点替换表示顶点的圆。
省略箭头。

哈斯图如图所示：

上限：将B视为部分有序集A的子集。如果每个y∈B的y≤x, 则元素x∈A称为B的上限。
下界：假设B是部分有序集A的子集。如果z≤x对于每个x∈B, 元素z∈A称为B的下界。
示例：考虑图A所示的位姿A = {a, b, c, d, e, f, g}。还令B = {c, d, e}。确定B的上限和下限。

解决方案：B的上限是e, f和g, 因为B的每个元素都是’ ≤’ e, f和g。
B的下限是a和b, 因为a和b是B的每个元素“≤”。
最小上限（最高）令A为部分有序集S的子集。如果M接替A的每个元素, 即S中的元素x等于M, 则S中的元素M称为A的上限。
如果A的上限在A的所有其他上限之前, 则称为A的上限, 并用Sup（A）表示
最大下界（INFIMUM）如果m在A的每个元素之前, 即如果对于A中的每个y, 我们有m < = y, 则表示集S中的元素m被称为S子集A的下界
如果A的下界在A的其他下界之后, 则称为A的下界, 并用Inf（A）表示
示例：确定其Hasse图如图所示的位姿B = {a, b, c}的最小上限和最大下限（如果存在）：

解决方案：最小上限为c。
最大下限是k。