哈斯图的画法，以及利用哈斯图寻找极大元之类

50 阅读 0 评论 33 点赞

我是靠谱客的博主爱笑春天，最近开发中收集的这篇文章主要介绍哈斯图的画法，以及利用哈斯图寻找极大元之类，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

哈斯图的画法要确定层数。也就是谁在上，谁在下。我在看过这个文章偏序集的哈斯图的画法之后结合书上的一些定义进行总结：（恒等关系在哈斯图上体现不出来就不说了。）

1.先把没有出现在值域（<a,b>, 其中b为值域）的元素放在第一排。如有多个，一起放在第一排。比如在关系集合中，{<1,2> <1,3> <1,4> <1,5> <1,6> <2,4> <2,6> <3,6>}，我们发现只有1没有出现在值域中，所以就放在第一排。

2.再把在第一排元素所在的关系全部扔了。出现在值域的元素（扔掉的关系且不会出现在未扔掉关系里）和只出现在前域的元素（未扔掉的关系）放在第二排。此时扔掉的元素为{<1,2> <1,3> <1,4> <1,5> <1,6>}，未扔掉的元素为{ <2,4> <2,6> <3,6>}。扔掉的关系的值域为{2,3,4,5,6}, 未扔掉的关系的全部元素为{2,3,4,6}, 5出现在集合{2,3,4,5,6}中，而未出现在{2,3,4,6}，所以5放到第二排，所以5放到第二排。未扔掉的关系集合前域为2，3，只出现在前域的元素为2，3，所以这两个元素也放在第二排。

3.以此类推，直到元素全部有了自己的位置。

4.在两层数之间，只有上层盖住下层时才能相连。

为什么是这样？我们只有这样，才保证了这一层和上一层（下一层）有盖住关系。什么是盖住？比如在例题中关系的集合中的<1, 4>就不是盖住关系，因为存在<1, 2>，<2, 4>，盖住就是关系<a, b>，且<a, b>中不存在c，使得<a, c>, <c, b>。这里我举个我们学校自编教材书上的一个例子。题目是这样的：已知集合A={1，2，3，4，5，6}，B={2，3，5}，R是A上的整除关系，求R的哈斯图，并求B得最大元，最小元，极大元，极小元，上界，上确界，下届，下确界。利用刚刚总结的那几句话来画哈斯图。先写出我们关系的集合{<1,2> <1,3> <1,4> <1,5> <1,6> <2,4> <2,6> <3,6>}。这里不写恒等关系，在画哈斯图时用不到。

1.第一层：1；

2.第二层：2，5，3；

3.第三层：4，6；

确定盖住关系后，我们来画出哈斯图

OK，哈斯图画好了，我们要利用哈斯图去寻找极大元之类的了。我根据书上的定义做出如下总结：

最大元素就是在子集中(例题中指B={2，3，5}）处于最高层且每个元素通过图中路径都可以找到它且它的上面没有元素。

最小元素就是在子集中处于最低层且每个元素通过图中路径都可以找到它且它的下面没有元素。

极大元素就是在子集中它的上面没有元素。

极小元素就是在子集中它的下面没有元素。

（记住：这里如果是子集，应当将子集当成一个单独的整体，而不受全集的影响。）

上届：所有子集内的元素沿着路径向上都可以找到的元素（这里包括子集和子集以外的元素）。根据上面所说的话，我们可以断定上届也可以是子集内的元素。

下届：所有子集内的元素沿着路径向下都可以找到的元素（这里包括子集和子集以外的元素）。根据上面所说的话，我们可以断定下届也可以是子集内的元素。

上确界：这里我们可以将上届元素看成一个独立的整体，而上确界就是这个集合的最小元，我们称为最小上届。。根据上面所说的话，我们可以断定上届也可以是上确界。

下确界：这里我们可以将下届元素看成一个独立的整体，而下确界就是这个集合的最大元，我们称为最大下届。根据上面所说的话，我们可以断定下届也可以是下确界。

我们还拿上面的例子为例：先将子集看为一个整体，再找极大元，极小元，最大元，最小元。

我们发现：2，3，5上面和下面都没有元素，所以2，3，5是极大元，极小元。但是我们发现2，3，5之间压根没线，所以就没有最大元和最小元之说。2，3，5沿向上路径找不到一个元素，所以也没有上确界和上届。2，3，5向下找可以找到一个元素1，所以元素1为下界。下届元素也可以为下确界，自回路嘛，1自己找到自己，所以1也为下确界。

话说回来，那些复杂的概念要不要看，当然要看。这些只不过是我总结出来比概念更快的方法罢了，还是源于概念的。另外，我也刚刚学，做的题不多，上面的方法有可能错。