Skip to content

Latest commit

 

History

History
88 lines (44 loc) · 3.72 KB

哈赛图.md

File metadata and controls

88 lines (44 loc) · 3.72 KB

哈赛图

先说啥叫哈赛图,就是简化了一些东西的图,而因为一个叫做哈赛的人很喜欢用这种图,所以叫做哈赛图。

哈赛图制作过程。

假设集合A为:{1,2,3,4},关系为a<=b,所以一般的图为:(4,4),(4,3),(4,2),(4,2)......

但是因为关系是自反的,所以我们可以把类似(4,4),(3,3),(2,2),(1,1)的线去掉:

接下来因为关系是传递的,所以我们把类似(4,3),(4,2),(4,1),(3,2),(3,1),(2,1)之类的线去掉:

image-20210206215925950

最后我们再把箭头去掉,得到的就是哈赛图了:

这个哈赛图很简单,换个复杂一点的哈赛图:

集合A=(1,2,3,4,6,8,12)

关系R:{(a,b)|b能被a整除}

原本的图:

化简后的图:

极大元与极小元

这个很简单,极小元就是该偏序集中不大于任何一个其他元素,比如上面的1,极大元则是该偏序集中不存在比该元素大的元素,比如上面的第二个例子中的12和8。

比如下面这2个哈赛图:

哈赛图1

的极小元是a,没有极大元,如果有疑问,那么请问你,b,c,d哪个比较大?如果其中一个比另外两个大的话,那么它们3个元素之间就应该有一条线。

哈赛图2

这个哈赛图中既没有极大元,也没有极小元。

上界和下界

这个也很好理解,就是在一个偏序集中,如果存在一个元素,假设为a,其小于该偏序集中某些元素组成的子子集A,那么该元素就称为集合A的下界,上界是类似的道理。

比如上面的哈赛图1,在a就是子集合(c,e)的上界。或者哈赛图2中,元素a就是子集合(b,c,d)的下界。

根据上面的定义,我们知道了对于一个偏序集合中的子集合来说,上界和下界的值不一定是固定的,比如下面这个哈赛图:

对于子集合(b,d)来说,f可以作为其上界,g也可以作为其上界,而这些上界中的最小值,叫做最小上界,同理,下界也很多,比如h和i,那么其中最大的值,叫做最大上界

这个定义就很厉害了:

“如果一个偏序集中,除了极大元和极小元,任何两个元素都有最小上界和最小下界,就称这个偏序集为格。”

(这里我修改了书上的定义,书上没有剔除极大元和极小元,但是如果不剔除,那么当定义中的任意两个元素包含极大元或极小元时,格就肯定不存在了)

啥意思呢?就是我们知道,一个格子,就是一个菱形,需要有4个点,任意两个元素就是中间的两个点,最小上界,最大下界分别就是菱形上面的点和下面的点。

比如下面这个哈赛图:

就是格,我们不考虑极大元和极小元,其中任何两个元素的组合,我们都可以找到最大下界和最小上界。

但是对于下面这种哈赛图,就没有格了。

因为元素c和元素d没有最小上界。